Abstract
In the near future, there will likely be specialpurpose quantum computers with 4050 highquality qubits. This paper lays general theoretical foundations for how to use such devices to demonstrate "quantum supremacy": that is, a clear quantum speedup for some task, motivated by the goal of overturning the Extended ChurchTuring Thesis as confidently as possible.
First, we study the hardness of sampling the output distribution of a random quantum circuit, along the lines of a recent proposal by by the Quantum AI group at Google. We show that there's a natural averagecase hardness assumption, which has nothing to do with sampling, yet implies that no polynomialtime classical algorithm can pass a statistical test that the quantum sampling procedure's outputs do pass. Compared to previous work  for example, on BosonSampling and IQP  the central advantage is that we can now talk directly about the observed outputs, rather than about the distribution being sampled.
Second, in an attempt to refute our hardness assumption, we give a new algorithm, inspired by Savitch's Theorem, for simulating a general quantum circuit with n qubits and m gates in polynomial space and m^O(n) time. We then discuss why this and other known algorithms fail to refute our assumption.
Third, resolving an open problem of Aaronson and Arkhipov, we show that any strong quantum supremacy theorem  of the form "if approximate quantum sampling is classically easy, then the polynomial hierarchy collapses"  must be nonrelativizing. This sharply contrasts with the situation for exact sampling.
Fourth, refuting a conjecture by Aaronson and Ambainis, we show that the Fourier Sampling problem achieves a constant versus linear separation between quantum and randomized query complexities.
Fifth, in search of a "happy medium" between blackbox and nonblackbox arguments, we study quantum supremacy relative to oracles in P/poly. Previous work implies that, if oneway functions exist, then quantum supremacy is possible relative to such oracles. We show, conversely, that some computational assumption is needed: if SampBPP=SampBQP and NP is in BPP, then quantum supremacy is impossible relative to oracles with small circuits.
BibTeX  Entry
@InProceedings{aaronson_et_al:LIPIcs:2017:7527,
author = {Scott Aaronson and Lijie Chen},
title = {{ComplexityTheoretic Foundations of Quantum Supremacy Experiments}},
booktitle = {32nd Computational Complexity Conference (CCC 2017)},
pages = {22:122:67},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770408},
ISSN = {18688969},
year = {2017},
volume = {79},
editor = {Ryan O'Donnell},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2017/7527},
URN = {urn:nbn:de:0030drops75274},
doi = {10.4230/LIPIcs.CCC.2017.22},
annote = {Keywords: computational complexity, quantum computing, quantum supremacy}
}
Keywords: 

computational complexity, quantum computing, quantum supremacy 
Seminar: 

32nd Computational Complexity Conference (CCC 2017) 
Issue Date: 

2017 
Date of publication: 

21.07.2017 