Superpolynomial Speedups Based on Almost Any Quantum Circuit

2008/01/01 by Sean Hallgren, Aram W. Harrow
Computer Science · Mathematics · Physics and Astronomy · #Algorithm #Computer science #Discrete mathematics #Electronic circuit #Hadamard transform #Mathematics #Parallel computing #Physics #Polynomial #Quantum #Quantum Computing Algorithms and Architecture #Quantum Fourier transform #Quantum Information and Cryptography #Quantum algorithm #Quantum circuit #Quantum computer #Quantum error correction #Quantum mechanics #Quantum phase estimation algorithm #Quantum walk #Quantum-Dot Cellular Automata #Random oracle #Speedup #Time complexity #Unitary state #quant-ph

paper · pdf · doi:10.1007/978-3-540-70575-8_64

published as Proc. of the 35th International Colloquium on Automata, Languages and Programming (ICALP 2008), LNCS 5125, pp. 782-795 · 16 pages, 1 figure, to appear in ICALP '08. v2 includes references and acknowledgments

openalex publication_date 2008/01/01 · arxiv created 2008/05/02 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/05

Abstract

The first separation between quantum polynomial time and classical bounded-error polynomial time was due to Bernstein and Vazirani in 1993. They first showed a O(1) vs. Omega(n) quantum-classical oracle separation based on the quantum Hadamard transform, and then showed how to amplify this into a n^O(1) time quantum algorithm and a n^{Omega(log n)} classical query lower bound. We generalize both aspects of this speedup. We show that a wide class of unitary circuits (which we call dispersing circuits) can be used in place of Hadamards to obtain a O(1) vs. Omega(n) separation. The class of dispersing circuits includes all quantum Fourier transforms (including over nonabelian groups) as well as nearly all sufficiently long random circuits. Second, we give a general method for amplifying quantum-classical separations that allows us to achieve a n^O(1) vs. n^{Omega(log n)} separation from any dispersing circuit.

Citations

• Quantum complexity theory
• Quantum Complexity Theory
• On the impossibility of a quantum sieve algorithm for graph isomorphism
• Logarithmic Sobolev inequalities for finite Markov chains
• Polynomial-time quantum algorithms for Pell's equation and the principal ideal problem
• On the Power of Quantum Computation
• From optimal measurement to efficient quantum algorithms for the hidden subgroup problem over semidirect product groups
• Cryptographic Distinguishability Measures for Quantum Mechanical States
• Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer