Simon's problem

In computational complexity theory and quantum computing, Simon's problem is a computational problem in the model of decision tree complexity or query complexity, conceived by Daniel Simon in 1994.^[1] Simon exhibited a quantum algorithm, usually called Simon's algorithm, that solves the problem exponentially faster than any (deterministic or probabilistic) classical algorithm.

Simon's algorithm uses queries to the black box, whereas the best classical probabilistic algorithm necessarily needs at least queries. It is also known that Simon's algorithm is optimal in the sense that any quantum algorithm to solve this problem requires queries.^[2][3] This problem yields an oracle separation between BPP and BQP, unlike the separation provided by the Deutsch-Jozsa algorithm, which separates P and EQP.

Although the problem itself is of little practical value it is interesting because it provides an exponential speedup over any classical algorithm (in a black box model).^[4] Moreover, it was also the inspiration for Shor's algorithm. Both problems are special cases of the abelian hidden subgroup problem, which is now known to have efficient quantum algorithms.

Problem description and algorithm

The input to the problem is a function (implemented by a black box) , promised to satisfy the property that for some we have for all , if and only if or . Note that the case of is allowed, and corresponds to being a permutation. The problem then is to find s.

The set of n-bit strings is a vector space under bitwise XOR. Given the promise, the preimage of f is either empty, or forms cosets with n-1 dimensions. Using quantum algorithms, we can, with arbitrarily high probability determine the basis vectors spanning this n-1 subspace since s is a vector orthogonal to all of the basis vectors.

Quantum subroutine in Simon's algorithm

Consider the Hilbert space consisting of the tensor product of the Hilbert space of input strings, and output strings. Using Hadamard operations, we can prepare the initial state

and then call the oracle to transform this state to

Hadamard transforms convert this state to

We perform a simultaneous measurement of both registers. If , we have destructive interference. So, only the subspace is picked out. Given enough samples of y, we can figure out the n-1 basis vectors, and compute s.

See also

• Deutsch-Jozsa algorithm

References

Quantum information science
General	Quantum computer Qubit Quantum information Quantum machine Quantum programming Timeline of quantum computing
Quantum communication	Quantum capacity Classical capacity Entanglement-assisted classical capacity Quantum channel Quantum network Quantum cryptography Quantum key distribution Quantum energy teleportation Quantum teleportation Superdense coding LOCC Entanglement distillation
Quantum algorithms	Universal quantum simulator Deutsch–Jozsa algorithm Grover's algorithm Quantum Fourier transform Shor's algorithm Simon's problem Quantum phase estimation algorithm Quantum annealing Algorithmic cooling
Quantum complexity theory	Quantum Turing machine EQP BQP QMA PostBQP
Quantum computing models	Quantum circuit Quantum gate One-way quantum computer cluster state Adiabatic quantum computation Topological quantum computer
Decoherence prevention	Quantum error correction Stabilizer codes Entanglement-Assisted Quantum Error Correction Quantum convolutional codes
Physical implementations	Quantum optics Cavity QED Circuit QED Linear optical quantum computing Ultracold atoms Trapped ion quantum computer Optical lattice Spin-based Nuclear magnetic resonance QC Kane QC Loss–DiVincenzo QC Nitrogen-vacancy center Superconducting quantum computing Charge qubit Flux qubit Phase qubit