A Caltech Library Service

Exponential Quantum Speed-ups are Generic

Brandão, Fernando G. S. L. and Horodecki, Michał (2013) Exponential Quantum Speed-ups are Generic. Quantum Information and Computation, 13 (11-12). pp. 901-924. ISSN 1533-7146.

[img] PDF - Submitted Version
See Usage Policy.


Use this Persistent URL to link to this item:


A central problem in quantum computation is to understand which quantum circuits are useful for exponential speed-ups over classical computation. We address this question in the setting of query complexity and show that for almost any sufficiently long quantum circuit one can construct a black-box problem which is solved by the circuit with a constant number of quantum queries, but which requires exponentially many classical queries, even if the classical machine has the ability to postselect. We prove the result in two steps. In the first, we show that almost any element of an approximate unitary 3-design is useful to solve a certain black-box problem efficiently. The problem is based on a recent oracle construction of Aaronson and gives an exponential separation between quantum and classical bounded-error with postselection query complexities. In the second step, which may be of independent interest, we prove that linear-sized random quantum circuits give an approximate unitary 3-design. The key ingredient in the proof is a technique from quantum many-body theory to lower bound the spectral gap of local quantum Hamiltonians.

Item Type:Article
Related URLs:
URLURL TypeDescription Paper
Brandão, Fernando G. S. L.0000-0003-3866-9378
Additional Information:© 2013 Rinton Press. Received August 9, 2012; Revised March 23, 2013. We would like to thank Salman Beigi for useful correspondence. FB is supported by a ”Conhecimento Novo” fellowship from the Brazilian agency Fundação de Amparo a Pesquisa do Estado de Minas Gerais (FAPEMIG). MH is supported by EU grant QESSENCE and by Polish Ministry of Science and Higher Education grant N N202 231937. FB would like to thank the hospitality of the National Quantum Information Center of Gdansk where part of this work was done. FB and MH thank the Intitute Mittag Leffler for their hospitality, where (another) part of this work was done.
Funding AgencyGrant Number
Fundação de Amparo a Pesquisa do Estado de Minas Gerais (FAPEMIG)UNSPECIFIED
Ministerstwo Nauki i Szkolnictwa Wyższego (MNiSW)N N202 231937
Subject Keywords:quantum query complexity, unitary t-designs
Issue or Number:11-12
Record Number:CaltechAUTHORS:20160608-075528573
Persistent URL:
Official Citation:Fernando G. S. L. Brandão and Michal Horodecki. 2013. Exponential quantum speed-ups are generic. Quantum Info. Comput. 13, 11-12 (November 2013), 901-924.
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:67758
Deposited By: Tony Diaz
Deposited On:08 Jun 2016 16:27
Last Modified:03 Oct 2019 10:08

Repository Staff Only: item control page