论文标题
关于量子代码最小距离问题的硬度
On the Hardness of the Minimum Distance Problem of Quantum Codes
论文作者
论文摘要
我们研究找到量子误差校正代码距离的问题的硬度。即使以近似形式，也已知经典代码的类似问题是NP-HARD。对于量子代码，已知与解码相关的各种问题是NP-固定的，但是距离问题的硬度尚未研究。在这项工作中，我们表明，找到稳定器量子代码的最小距离或大约是NP-HARD。通过使用CWS框架将经典的最小距离问题减少到量子码，该量子代码通过将经典的最小距离问题减少到量子问题，该量子代码可以通过将经典的最小距离问题减少到量子代码，该量子代码使用经典代码和图形构建量子代码，从而获得了此结果。用于我们结果的主要技术工具是在4周期无图形的所谓图形状态距离上的下限。特别是，我们表明，对于4周免费图$ g $，其图形状态距离为$δ$或$δ+1 $，其中$δ$是$ g $的最低顶点度。由于已知从稳定器代码到CSS代码的众所周知的降低，我们的结果也表明，找到CSS代码的最小距离也是NP-HARD。
We study the hardness of the problem of finding the distance of quantum error-correcting codes. The analogous problem for classical codes is known to be NP-hard, even in approximate form. For quantum codes, various problems related to decoding are known to be NP-hard, but the hardness of the distance problem has not been studied before. In this work, we show that finding the minimum distance of stabilizer quantum codes exactly or approximately is NP-hard. This result is obtained by reducing the classical minimum distance problem to the quantum problem, using the CWS framework for quantum codes, which constructs a quantum code using a classical code and a graph. A main technical tool used for our result is a lower bound on the so-called graph state distance of 4-cycle free graphs. In particular, we show that for a 4-cycle free graph $G$, its graph state distance is either $δ$ or $δ+1$, where $δ$ is the minimum vertex degree of $G$. Due to a well-known reduction from stabilizer codes to CSS codes, our results also imply that finding the minimum distance of CSS codes is also NP-hard.
