TY - GEN
T1 - Superpolynomial speedups based on almost any quantum circuit
AU - Hallgren, Sean
AU - Harrow, Aram W.
PY - 2008
Y1 - 2008
N2 - 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. Ω(n) quantum-classical oracle separation based on the quantum Hadamard transform, and then showed how to amplify this into a nO(1) time quantum algorithm and a nΩ(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. Ω(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 nO(1) vs. nΩ(log n) separation from any dispersing circuit.
AB - 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. Ω(n) quantum-classical oracle separation based on the quantum Hadamard transform, and then showed how to amplify this into a nO(1) time quantum algorithm and a nΩ(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. Ω(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 nO(1) vs. nΩ(log n) separation from any dispersing circuit.
UR - http://www.scopus.com/inward/record.url?scp=49049105178&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=49049105178&partnerID=8YFLogxK
U2 - 10.1007/978-3-540-70575-8_64
DO - 10.1007/978-3-540-70575-8_64
M3 - Conference contribution
AN - SCOPUS:49049105178
SN - 3540705740
SN - 9783540705741
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 782
EP - 795
BT - Automata, Languages and Programming - 35th International Colloquium, ICALP 2008, Proceedings
T2 - 35th International Colloquium on Automata, Languages and Programming, ICALP 2008
Y2 - 7 July 2008 through 11 July 2008
ER -