An exact quantum polynomial-time algorithm for Simon's problem
- 14 April 1997
- proceedings article
- Published by Institute of Electrical and Electronics Engineers (IEEE)
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 11 references indexed in Scilit:
- The quantum challenge to structural complexity theoryPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2003
- Algorithms for quantum computation: discrete logarithms and factoringPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- On the power of quantum computationPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- Quantum Complexity TheorySIAM Journal on Computing, 1997
- A fast quantum mechanical algorithm for database searchPublished by Association for Computing Machinery (ACM) ,1996
- Elementary gates for quantum computationPhysical Review A, 1995
- A quantum jump in computer sciencePublished by Springer Nature ,1995
- 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