Physics – Quantum Physics
Scientific paper
2008-04-30
Proc. of the 35th International Colloquium on Automata, Languages and Programming (ICALP 2008), LNCS 5125, pp. 782-795
Physics
Quantum Physics
16 pages, 1 figure, to appear in ICALP '08. v2 includes references and acknowledgments
Scientific paper
10.1007/978-3-540-70575-8_64
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.
Hallgren Sean
Harrow Aram W.
No associations
LandOfFree
Superpolynomial speedups based on almost any quantum circuit does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Superpolynomial speedups based on almost any quantum circuit, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Superpolynomial speedups based on almost any quantum circuit will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-40694