Superpolynomial speedups based on almost any quantum circuit
arXiv:0805.0007 · doi:10.1007/978-3-540-70575-8_64
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.
16 pages, 1 figure, to appear in ICALP '08. v2 includes references and acknowledgments
References in corpus (9)
- Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer
- The foundations of statistical mechanics from entanglement: Individual states vs. averages
- Random Quantum Circuits are Approximate 2-designs
- From optimal measurement to efficient quantum algorithms for the hidden subgroup problem over semidirect product groups
- Emergence of typical entanglement in two-party random processes
- On the impossibility of a quantum sieve algorithm for graph isomorphism: unconditional results
- Cryptographic Distinguishability Measures for Quantum Mechanical States
- Superpolynomial speedups based on almost any quantum circuit
- Limitations of Quantum Coset States for Graph Isomorphism
Cited by in corpus (6)
- Random Quantum Circuits are Approximate 2-designs
- Mixing properties of stochastic quantum Hamiltonians
- Super-Polynomial Quantum Speed-ups for Boolean Evaluation Trees with Hidden Structure
- Superpolynomial speedups based on almost any quantum circuit
- Quantum algorithms for highly non-linear Boolean functions
- Polynomial-Time Classical Simulation of Hidden Shift Circuits via Confluent Rewriting of Symbolic Sums