Average-case quantum advantage with shallow circuits
Average-case quantum advantage with shallow circuits
复制标题
DOI：
10.4230/lipics.ccc.2019.21
复制
发表时间：
2018-10
期刊：
影响因子：
--
通讯作者：
F. Gall
中科院分区：
文献类型：
--
作者：
F. Gall
最近，Bravyi，Gosset和König（Science 2018）证明了小深度量子电路和经典电路的计算能力之间的无条件分离。在本文中，我们在平均情况下展示了类似的分离，这为小深度量子计算的优越性提供了更有力的证据：我们构造了一个计算任务，可以通过具有有界扇入门的恒定深度的量子电路在所有输入上求解。（一个“浅”量子电路），并表明，任何经典电路与有界扇入门解决这个问题的非-可以忽略的一部分输入必须具有对数深度。我们的研究结果是通过引入一种技术，通过我们称之为扩展图的构造，从任何图中创建表现出全局量子相关性的量子态。Coudron，Stark和Vidick（arXiv：1810.04233）以及贝内Watts，Kothari，Schaeffer和Tal（STOC 2019）最近（独立）获得了类似的结果。
Recently Bravyi, Gosset and König (Science 2018) proved an unconditional separation between the computational powers of small-depth quantum and classical circuits for a relation. In this paper we show a similar separation in the average-case setting that gives stronger evidence of the superiority of small-depth quantum computation: we construct a computational task that can be solved on all inputs by a quantum circuit of constant depth with bounded-fanin gates (a "shallow" quantum circuit) and show that any classical circuit with bounded-fanin gates solving this problem on a non-negligible fraction of the inputs must have logarithmic depth. Our results are obtained by introducing a technique to create quantum states exhibiting global quantum correlations from any graph, via a construction that we call the extended graph. Similar results have been very recently (and independently) obtained by Coudron, Stark and Vidick (arXiv:1810.04233), and Bene Watts, Kothari, Schaeffer and Tal (STOC 2019).