Simon’s Algorithm

A guided research project in Quantum Computing.

← Quantum Computing projects

Experience Research Quantum Computing

Question

How can a quantum algorithm reveal a hidden XOR period?

Each measurement gives one linear restriction on the secret, and enough restrictions determine it.
Each measurement gives one linear restriction on the secret, and enough restrictions determine it.

Goals

  • Implement Simon's circuit and collect its measurement equations.
  • Recover the hidden string with linear algebra over \(\mathbb F_2\).

Method

Use interference to sample vectors perpendicular to the unknown period.

  • Construct an oracle satisfying \(f(x)=f(x\oplus s)\).
  • Run the circuit repeatedly and record the measured bit strings.
  • Solve the resulting binary linear system and verify the recovered period.