Superpolynomial speedups based on almost any quantum circuit

Simple item page
dc.creatorHallgren, Sean
dc.creatorHarrow, Aram W.
dc.date2008-04-30
dc.date2008-05-02
dc.date.accessioned2026-07-07T09:48:21Z
dc.date.available2026-07-07T09:48:21Z
dc.descriptionThe 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.
dc.description16 pages, 1 figure, to appear in ICALP '08. v2 includes references and acknowledgments
dc.identifierhttps://arxiv.org/abs/0805.0007
dc.identifierhttp://arxiv.org/abs/0805.0007
dc.identifierProc. of the 35th International Colloquium on Automata, Languages and Programming (ICALP 2008), LNCS 5125, pp. 782-795
dc.identifierdoi:10.1007/978-3-540-70575-8_64
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/164185
dc.subjectQuantum Physics
dc.titleSuperpolynomial speedups based on almost any quantum circuit
dc.typetext

Files

Collections

arXiv