1997/04/14 by Gilles Brassard, Peter Høyer, Peter Hoyer · 4 citations
Computer Science · Mathematics · Physics and Astronomy · #Algorithm #Computer science #Mathematics #Physics #Polynomial #Quantum #Quantum Computing Algorithms and Architecture #Quantum Information and Cryptography #Quantum Mechanics and Applications #Quantum computer #Quantum mechanics #quant-ph
paper · pdf · doi:10.1109/istcs.1997.595153
published as Fifth Israeli Symposium on Theory of Computing and Systems (ISTCS'97), pp. 12-23, June 1997 · 12 pages, LaTeX2e, no figures. To appear in Proceedings of the Fifth Israeli Symposium on Theory of Computing and Systems (ISTCS'97)
arxiv created 1997/04/14 · openalex publication_date 2002/11/22 · arxiv updated 2017/01/04 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/05
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.