Superpolynomial speedups based on almost any quantum circuit

Sean Hallgren, Aram W. Harrow

Research output: Chapter in Book/Report/Conference proceedingConference contribution

7 Scopus citations


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.

Original languageEnglish (US)
Title of host publicationAutomata, Languages and Programming - 35th International Colloquium, ICALP 2008, Proceedings
Number of pages14
EditionPART 1
StatePublished - 2008
Event35th International Colloquium on Automata, Languages and Programming, ICALP 2008 - Reykjavik, Iceland
Duration: Jul 7 2008Jul 11 2008

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
NumberPART 1
Volume5125 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Other35th International Colloquium on Automata, Languages and Programming, ICALP 2008

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • General Computer Science


Dive into the research topics of 'Superpolynomial speedups based on almost any quantum circuit'. Together they form a unique fingerprint.

Cite this