Simon's algorithm

Simon's algorithm, conceived by Daniel Simon in 1994,^[1] is a quantum algorithm which solves a black-box problem exponentially faster than any classical algorithm, including probabilistic algorithms. The algorithm uses $O(n)$ queries to the black box, whereas the best classical randomized algorithm necessarily needs at least $\Omega(2^{n/2})$ queries. It is also known that Simon's algorithm is optimal in the sense that any quantum algorithm to solve this problem requires $\Omega(n)$ queries.^[2]^[3]

We have a random oracle relative to which BPP and BQP are separated. This is an improvement over the Deutsch-Jozsa algorithm separating P from EQP. The oracle needs to be quantum and nondecohering.

The input to the problem is a function (implemented by a black box) $f:\{0,1\}^n\rightarrow \{0,1\}^n$ , promised to satisfy the property that for some $s\in \{0,1\}^n$ we have for all $y,z\in\{0,1\}^n$ , $f(y)=f(z)$ if and only if $y=z$ or $y \oplus z =s$ . Note that the case of $s=0^n$ is allowed, and corresponds to $f$ being a permutation. The problem then is to find s.

The set of n-bit strings is a $\mathbb{Z}_2$ 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.

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

$\sum_x \left| x \right\rangle \left| 0 \right\rangle$

and then call the oracle to transform this state to

$\sum_x \left| x \right\rangle \left| f(x) \right\rangle$

Hadamard transforms convert this state to

$\sum_y \sum_x (-1)^{x.y} \left| y \right\rangle \left| f(x) \right\rangle$

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

Although the problem itself is of little practical value it is interesting because it provides an exponential speedup over any classical algorithm. 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.

References

^ Simon, D.R. (1994), "On the power of quantum computation", Foundations of Computer Science, 1994 Proceedings., 35th Annual Symposium on: 116–123, http://citeseer.ist.psu.edu/viewdoc/download;jsessionid=0D01FC6F66C81F349B409BAE3F515CAC?doi=10.1.1.51.5477&rep=rep1&type=pdf, retrieved 2011-06-06
^ Koiran, P.; Nesme, V.; Portier, N. (2007), "The quantum query complexity of the abelian hidden subgroup problem", Theoretical Computer Science 380 (1-2): 115–126, doi:10.1016/j.tcs.2007.02.057, http://perso.ens-lyon.fr/pascal.koiran/Publis/lip.05-17.ps, retrieved 2011-06-06
^ Koiran, P.; Nesme, V.; Portier, N. (2005), "A quantum lower bound for the query complexity of Simon's Problem", Proc. ICALP 3580: 1287–1298, arXiv:quant-ph/0501060, http://perso.ens-lyon.fr/pascal.koiran/Publis/icalp05.ps, retrieved 2011-06-06

Quantum information science

General	Quantum computer • Qubit • Quantum information • Quantum programming • Timeline of quantum computing

Quantum communication	Quantum capacity • Quantum channel • Quantum cryptography (Quantum key distribution) • Quantum teleportation • Superdense coding • LOCC • Entanglement distillation

Quantum algorithms	Universal quantum simulator • Deutsch–Jozsa algorithm • Grover's search • quantum Fourier transform • Shor's factorization • Simon's Algorithm • Quantum phase estimation algorithm • Quantum annealing

Quantum complexity theory	Quantum Turing machine • 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

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

Simon's algorithm

See also

References