Approximate Low-Weight Check Codes and Circuit Lower Bounds for Noisy Ground States
Approximate Low-Weight Check Codes and Circuit Lower Bounds for Noisy Ground States
复制标题
噪声接地状态的近似低权重校验码和电路下界
DOI：
--
复制
发表时间：
2018
期刊：
影响因子：
--
通讯作者：
H. Yuen
中科院分区：
文献类型：
--
作者：
Chinmay Nirkhe;U. Vazirani;H. Yuen
弗里德曼和黑斯廷斯（量子信息与计算，2014）的无低能平凡态猜想（NLTS）断言存在局部哈密顿子，其低能态不能由恒定深度的量子电路产生，确定了解决量子PCP猜想的根本障碍。Eldar和Harrow（2017年计算机科学基础）在NLTS猜想方面取得了进展，他们证明了一个密切相关的定理，称为无低误差平凡态（NLETS）。在本文中，我们给出了一个更简单的NLETS定理的证明，并使用相同的技术建立了局部哈密顿子的噪声基态的超多项式电路大小下界（假设$\mathsf{QCMA} \neq \mathsf{QMA}$），解决了Eldar和Harrow的一个开放问题。我们讨论了我们的研究结果对NLTS和nlet之间关系的新见解。
最后，我们的技术意味着$\textit{approximate quantum low-weight check (qLWC) codes}$具有线性速率、线性距离和恒定权重检查的存在。这些码类似于量子LDPC码，除了(1)每个粒子可能参与大量的检查，(2)错误只需要纠正到保真度$1 - 1/\mathsf{poly}(n)$。这与Freedman， Meyer和Luo最著名的稳定剂LDPC代码形成鲜明对比，后者实现了$O(\sqrt{n \log n})$的距离。
在我们的结果中使用的主要技术是利用费曼-基塔耶夫时钟结构来近似嵌入由电路定义的状态的子空间，作为局部哈密顿量的地空间。
The No Low-Energy Trivial States (NLTS) conjecture of Freedman and Hastings (Quantum Information and Computation 2014), which asserts the existence of local Hamiltonians whose low energy states cannot be generated by constant depth quantum circuits, identifies a fundamental obstacle to resolving the quantum PCP conjecture. Progress towards the NLTS conjecture was made by Eldar and Harrow (Foundations of Computer Science 2017), who proved a closely related theorem called No Low-Error Trivial States (NLETS). In this paper, we give a much simpler proof of the NLETS theorem, and use the same technique to establish superpolynomial circuit size lower bounds for noisy ground states of local Hamiltonians (assuming $\mathsf{QCMA} \neq \mathsf{QMA}$), resolving an open question of Eldar and Harrow. We discuss the new light our results cast on the relationship between NLTS and NLETS.
Finally, our techniques imply the existence of $\textit{approximate quantum low-weight check (qLWC) codes}$ with linear rate, linear distance, and constant weight checks. These codes are similar to quantum LDPC codes except (1) each particle may participate in a large number of checks, and (2) errors only need to be corrected up to fidelity $1 - 1/\mathsf{poly}(n)$. This stands in contrast to the best-known stabilizer LDPC codes due to Freedman, Meyer, and Luo which achieve a distance of $O(\sqrt{n \log n})$.
The principal technique used in our results is to leverage the Feynman-Kitaev clock construction to approximately embed a subspace of states defined by a circuit as the ground space of a local Hamiltonian.