Category: search  |  Difficulty: intermediate  |  Qubits: 4  |  Gates: 6  |  Depth: 4

Simon's algorithm finds the hidden period s of a 2-to-1 function f: {0,1}^n → {0,1}^n satisfying f(x) = f(x⊕s) in O(n) quantum queries, versus exponential classically. Each run of the circuit yields a random string y orthogonal to s (y·s = 0 mod 2). After O(n) runs, Gaussian elimination over GF(2) recovers s. This problem inspired Shor's factoring algorithm.

y such that y·s = 0 mod 2 for s='11'; run multiple times and apply GF(2) elimination

The OpenQASM 2.0 circuit is in circuit.qasm.

OPENQASM 2.0; include "qelib1.inc"; // Simon's algorithm: 2-bit function with period s="11" // f(00)=f(11)=10, f(01)=f(10)=01 // q[0..1]: input register, q[2..3]: output register qreg q[4]; creg c[2]; // Superpose input h q[0]; h q[1]; // Oracle for f with period s="11": // Copy q[0] -> q[2], q[1] -> q[3], q[0] XOR q[1] -> q[2] cx q[0],q[2]; cx q[1],q[2]; cx q[0],q[3]; // Apply Hadamard to input register h q[0]; h q[1]; // Measure input: gives y satisfying y.s = 0 mod 2 measure q[0] -> c[0]; measure q[1] -> c[1]; 

simons hidden-subgroup period-finding exponential-speedup

• Simon, D.R. (1997). On the Power of Quantum Computation. SIAM J. Comput. 26(5)

MIT — part of the OpenQC Algorithm Catalog.