期刊
32ND COMPUTATIONAL COMPLEXITY CONFERENCE (CCC 2017)
卷 79, 期 -, 页码 -出版社
SCHLOSS DAGSTUHL, LEIBNIZ CENTER INFORMATICS
DOI: 10.4230/LIPIcs.CCC.2017.22
关键词
computational complexity; quantum computing; quantum supremacy
资金
- Vannevar Bush Faculty Fellowship from the US Department of Defense
- Simons Foundation It from Qubit Collaboration
- National Basic Research Program of China [2011CBA00300, 2011CBA00301]
- National Natural Science Foundation of China [61361136003]
In the near future, there will likely be special-purpose quantum computers with 40-50 high-quality 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 Church-Turing 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 the Quantum AI group at Google. We show that there's a natural average-case hardness assumption, which has nothing to do with sampling, yet implies that no polynomial-time 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 depth d in polynomial space and d(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 non-relativizing. This sharply contrasts with the situation for exact sampling. Fourth, refuting a conjecture by Aaronson and Ambainis, we show that there is a sampling task, namely Fourier Sampling, with a 1 versus linear separation between its quantum and classical query complexities. Fifth, in search of a happy medium between black-box and non-black-box arguments, we study quantum supremacy relative to oracles in P/poly. Previous work implies that, if one-way 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 subset of BPP, then quantum supremacy is impossible relative to oracles with small circuits.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据