Simon's algorithm

From Wikipedia, the free encyclopedia

Simon's algorithm is one of the first Quantum algorithms discovered which outperforms any known classical algorithm. Let be such that for some we have for all

f(y) = f(z) if and only if y = z or .

Although the problem itself is of little practical value it provides an exponential improvement in time over any known classical algorithm. To find x using a classical randomized algorithm Ω(2^{n / 2}) queries of f would be required. Using Simon's algorithm we are able to find a solution with high probability using O(n) queries of f. It was also the inspiration for Shor's algorithm

v • d • e Quantum computing General Qubit • Quantum computer • Quantum information • Quantum programming • Quantum virtual machine • Timeline of quantum computing Quantum communication Quantum channel • Quantum cryptography • Quantum teleportation • LOCC • Entanglement distillation Quantum algorithms Universal quantum simulator • Deutsch-Jozsa algorithm • Grover's search • Shor's factorization • Simon's Algorithm • (BQP) Quantum computing models Quantum circuit (quantum gate) • One-way quantum computer (cluster state) • Adiabatic quantum computation Decoherence prevention Quantum error correction • Topological quantum computer Physical implementations Quantum optics Linear optics QC • Cavity QED Ultracold atoms Trapped ion quantum computer • Optical lattice Spin-based Nuclear magnetic resonance (NMR) quantum computing • Kane QC • Loss-DiVincenzo (quantum dot) QC Other Superconducting quantum computing (Charge qubit • Flux qubit) • Nitrogen-vacancy center