Good approximate quantum LDPC codes from spacetime circuit Hamiltonians
Good approximate quantum LDPC codes from spacetime circuit Hamiltonians
复制标题
来自时空电路哈密顿量的良好近似量子 LDPC 码
DOI：
--
复制
发表时间：
2018
期刊：
影响因子：
--
通讯作者：
H. Yuen
中科院分区：
文献类型：
--
作者：
Thomas C. Bohdanowicz;E. Crosson;Chinmay Nirkhe;H. Yuen
我们研究近似量子低密度奇偶校验（QLDPC）码，它们是指定为无挫败局部哈密顿量的地面空间的近似量子纠错码，其项不一定可交换。此类代码概括了稳定器 QLDPC 代码，这是具有稀疏、低权重稳定器生成器的精确量子纠错码（即每个稳定器生成器作用于几个量子位，并且每个量子位参与几个稳定器生成器）。我们的研究源于哈密顿复杂性和量子编码理论中的一个重要问题：是否存在具有恒定速率、线性距离和恒定重量稳定器的稳定器 QLDPC 码？我们证明，如果我们超越稳定器代码，获得这种最佳参数缩放（模多对数校正）是可能的：我们证明了一系列 [[N,k,d,ε]] 近似 QLDPC 代码的存在，这些代码将 k = Ω(N) 逻辑量子位编码为距离 d = Ω(N) 和近似不保真度 ε = 1/(N) 的 N 个物理量子位。代码空间由一组 10 个本地非交换投影仪稳定，每个物理量子位仅参与 N 个投影仪。我们证明了有效编码图的存在，并表明代码哈密顿量的谱间隙为 Ω(N−3.09)。我们还表明，任意泡利误差可以通过多对数深度的电路局部检测到。我们的近似 QLDPC 代码系列基于应用电路哈密顿量和近似量子代码之间的最新联系（Nirkhe 等人，ICALP 2018），其结果表明多对数深度的随机 Clifford 电路产生渐近良好的量子代码（Brown 和 Fawzi，ISIT 2013）。然后，为了获得具有稀疏检查和强大的局部错误检测能力的代码，我们使用时空电路到哈密尔顿结构，以利用 Brown-Fawzi 电路的并行性。因此，我们将我们的代码称为时空代码。代码哈密顿量的谱间隙分析是这项工作的主要技术贡献。我们证明，对于 n 个量子位上的任何深度 D 量子电路，都存在一个相关的时空电路到哈密尔顿结构，其光谱间隙为 Ω(n−3.09 D−2 log−6(n))。为了降低这个差距，我们使用马尔可夫链分解方法将部分完成的电路配置的状态空间划分为与深度 logn 的均匀电路段相对应的重叠子集，这些子集基于双音排序电路。我们使用这些电路配置的组合属性来显示子集之间的快速混合，并且在子集中，我们在双调电路配置上的本地更新马尔可夫链和等面积二元平铺上的边缘翻转马尔可夫链之间开发了一种新颖的同构，其混合时间最近被证明是多项式的（Cannon、Levin和Stauffer，RANDOM 2017）。先前关于时空电路哈密顿量谱间隙的下界都基于与精确可解的量子自旋链的连接，并且仅应用于具有至少线性深度的 1+1 维最近邻量子电路。
We study approximate quantum low-density parity-check (QLDPC) codes, which are approximate quantum error-correcting codes specified as the ground space of a frustration-free local Hamiltonian, whose terms do not necessarily commute. Such codes generalize stabilizer QLDPC codes, which are exact quantum error-correcting codes with sparse, low-weight stabilizer generators (i.e. each stabilizer generator acts on a few qubits, and each qubit participates in a few stabilizer generators). Our investigation is motivated by an important question in Hamiltonian complexity and quantum coding theory: do stabilizer QLDPC codes with constant rate, linear distance, and constant-weight stabilizers exist? We show that obtaining such optimal scaling of parameters (modulo polylogarithmic corrections) is possible if we go beyond stabilizer codes: we prove the existence of a family of [[N,k,d,ε]] approximate QLDPC codes that encode k = Ω(N) logical qubits into N physical qubits with distance d = Ω(N) and approximation infidelity ε = 1/(N). The code space is stabilized by a set of 10-local noncommuting projectors, with each physical qubit only participating in N projectors. We prove the existence of an efficient encoding map and show that the spectral gap of the code Hamiltonian scales as Ω(N−3.09). We also show that arbitrary Pauli errors can be locally detected by circuits of polylogarithmic depth. Our family of approximate QLDPC codes is based on applying a recent connection between circuit Hamiltonians and approximate quantum codes (Nirkhe, et al., ICALP 2018) to a result showing that random Clifford circuits of polylogarithmic depth yield asymptotically good quantum codes (Brown and Fawzi, ISIT 2013). Then, in order to obtain a code with sparse checks and strong detection of local errors, we use a spacetime circuit-to-Hamiltonian construction in order to take advantage of the parallelism of the Brown-Fawzi circuits. Because of this, we call our codes spacetime codes. The analysis of the spectral gap of the code Hamiltonian is the main technical contribution of this work. We show that for any depth D quantum circuit on n qubits there is an associated spacetime circuit-to-Hamiltonian construction with spectral gap Ω(n−3.09 D−2 log−6(n)). To lower bound this gap we use a Markov chain decomposition method to divide the state space of partially completed circuit configurations into overlapping subsets corresponding to uniform circuit segments of depth logn, which are based on bitonic sorting circuits. We use the combinatorial properties of these circuit configurations to show rapid mixing between the subsets, and within the subsets we develop a novel isomorphism between the local update Markov chain on bitonic circuit configurations and the edge-flip Markov chain on equal-area dyadic tilings, whose mixing time was recently shown to be polynomial (Cannon, Levin, and Stauffer, RANDOM 2017). Previous lower bounds on the spectral gap of spacetime circuit Hamiltonians have all been based on a connection to exactly solvable quantum spin chains and applied only to 1+1 dimensional nearest-neighbor quantum circuits with at least linear depth.
无偏二元平铺的边翻转马尔可夫链的多项式混合
DOI：
--
发表时间：
2017
期刊：
--
影响因子：
--
作者：
Cannon S
通讯作者：
Cannon S