Recent works by Bravyi, Gosset and K\"onig (Science 2018), Bene Watts et al. (STOC 2019), Coudron, Stark and Vidick (QIP 2019) and Le Gall (CCC 2019) have shown unconditional separations between the computational powers of shallow (i.e., small-depth) quantum and classical circuits: quantum circuits can solve in constant depth computational problems that require logarithmic depth to solve with classical circuits. Using quantum error correction, Bravyi, Gosset, K\"onig and Tomamichel (Nature Physics 2020) further proved that a similar separation still persists even if quantum circuits are subject to local stochastic noise. We prove that this quantum advantage persists even if the quantum circuits can be subject to arbitrary corruption: in this paper we assume that any constant fraction of the qubits (for instance, huge blocks of qubits) may be arbitrarily corrupted at the end of the computation. We show that even in this model, quantum circuits can still solve in constant depth computational problems that require logarithmic depth to solve with bounded fan-in classical circuits. This gives another compelling evidence of the computational power of quantum shallow circuits. In order to show our result, we consider the Graph State Sampling problem (which was also used in prior works) on expander graphs. We exploit the "robustness" of expander graphs against vertex corruption to show that a subproblem hard for small-depth classical circuits can still be extracted from the output of the corrupted quantum circuit.
翻译:Bravyi、Gosset和K\"onig(Science 2018)、Bene Watts等人(STOC 2019)、Caudron、Stark和Vidick(QIP 2019)和Le Gall(CCC 2019)的近期著作显示,浅(即小深度)量子和古典电路的计算能力之间有无条件的分离:量子电路可以在不断的深度计算问题中解决,需要对古典电路进行对数深的计算。使用量子错误校正、Bravyi、Gosset、K\'onig和Tomamichel(自然物理 2020)进一步证明,即使量子电路受到当地蒸汽的声音影响,也仍然存在着类似的数据分离。我们证明,即使量子电路电路的计算能力也存在任意的计算能力:量子电路的固定比例在计算结束时可能被任意腐蚀。我们可以看到,即使在这种模型中,量电路面电路的硬电路仍然可以在不断的深度中解解。