An exact quantum polynomial-time algorithm for Simon's problem
Authors:
- G. BrassardGBG. Brassard
- P. HoyerPHP. Hoyer
- 14 April 1997
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 12-23
Abstract
We investigate the power of quantum computers when they are required to return an answer that is guaranteed to be correct after a time that is upper-bounded by a polynomial in the worst case. We show that a natural generalization of Simon's problem can be solved in this way, whereas previous algorithms required quantum polynomial time in the expected sense only, without upper bounds on the worst-case running time. This is achieved by generalizing both Simon's and Grover's algorithms and combining them in a novel way. It follows that there is a decision problem that can be solved in exact quantum polynomial time, which would require expected exponential time on any classical bounded-error probabilistic computer if the data is supplied as a black box.Comment: 12 pages, LaTeX2e, no figures. To appear in Proceedings of the Fifth Israeli Symposium on Theory of Computing and Systems (ISTCS'97Keywords
All Related Versions
This publication has 8 references indexed in Scilit:
- Quantum Complexity TheorySIAM Journal on Computing, 1997
- Quantum physics and computersContemporary Physics, 1996
- A fast quantum mechanical algorithm for database search1996
- Elementary gates for quantum computationPhysical Review A, 1995
- A quantum jump in computer science1995
- Oracle Quantum ComputingJournal of Modern Optics, 1994
- Rapid solution of problems by quantum computationProceedings of the Royal Society of London. Series A: Mathematical and Physical Sciences, 1992
- Logical Reversibility of ComputationIBM Journal of Research and Development, 1973