论文标题
易于故障量子计算的空间上的下限
A lower bound on the space overhead of fault-tolerant quantum computation
论文作者
论文摘要
阈值定理是易于断层量子计算理论的基本结果，表明可以使用噪声水平低于恒定水平，可以使用多组轴向的开销进行任意长的量子计算。 Fawzi，Grospellier和Leverrier（FOCS 2018）的最新作品基于Gottesman（QIC 2013）的结果，表明，在宽度中，宽度在宽度上由多一体式的长度界定的电路，可以渐近地缩小到与电路的恒定相关的空间。在这项工作中，使用最小模型来实现量子容错，我们建立了达到容错所需的空间上的一般下限。 对于任何非统一量子信道$ \ MATHCAL {n} $和任何量子容量公差方案，针对$ \ mathrm {i.i.d。} $由$ \ mathcal {n} $建模的噪声，我们证明$ \ max \ left \ {\ mathrm {q}（\ mathcal {n}）^{ - 1} n，α_\ Mathcal {n} \ log t \ log t \ right \} $，用于长度$ t $ t $ and width $ n $的电路。在这里，$ \ mathrm {q}（\ Mathcal {n}）$表示$ \ Mathcal {n} $和$α_\ Mathcal {n}> 0 $的量子容量仅取决于通道$ \ Mathcal {n} $。在我们的模型中，我们允许在电路执行过程中将Qubits取代，并允许经典计算是免费和完美的。这改善了假定经典计算也受噪声影响的结果，有时不允许添加新鲜量子。一路上，我们证明了在易于断层量子计算的最大长度上的指数上限，并通过Ben-Or，Gottesman和Hassidim（2013）解决了振幅阻尼噪声。
The threshold theorem is a fundamental result in the theory of fault-tolerant quantum computation stating that arbitrarily long quantum computations can be performed with a polylogarithmic overhead provided the noise level is below a constant level. A recent work by Fawzi, Grospellier and Leverrier (FOCS 2018) building on a result by Gottesman (QIC 2013) has shown that the space overhead can be asymptotically reduced to a constant independent of the circuit provided we only consider circuits with a length bounded by a polynomial in the width. In this work, using a minimal model for quantum fault tolerance, we establish a general lower bound on the space overhead required to achieve fault tolerance. For any non-unitary qubit channel $\mathcal{N}$ and any quantum fault tolerance schemes against $\mathrm{i.i.d.}$ noise modeled by $\mathcal{N}$, we prove a lower bound of $\max\left\{\mathrm{Q}(\mathcal{N})^{-1}n,α_\mathcal{N} \log T\right\}$ on the number of physical qubits, for circuits of length $T$ and width $n$. Here, $\mathrm{Q}(\mathcal{N})$ denotes the quantum capacity of $\mathcal{N}$ and $α_\mathcal{N}>0$ is a constant only depending on the channel $\mathcal{N}$. In our model, we allow for qubits to be replaced by fresh ones during the execution of the circuit and we allow classical computation to be free and perfect. This improves upon results that assumed classical computations to be also affected by noise, and that sometimes did not allow for fresh qubits to be added. Along the way, we prove an exponential upper bound on the maximal length of fault-tolerant quantum computation with amplitude damping noise resolving a conjecture by Ben-Or, Gottesman, and Hassidim (2013).
