On the Hardness of the Minimum Distance Problem of Quantum Codes
- URL: http://arxiv.org/abs/2203.04262v2
- Date: Mon, 6 Nov 2023 13:42:05 GMT
- Title: On the Hardness of the Minimum Distance Problem of Quantum Codes
- Authors: Upendra Kapshikar and Srijita Kundu
- Abstract summary: We show that finding the minimum distance of stabilizer quantum codes exactly or approximately is NP-hard.
A main technical tool used for our result is a lower bound on the so-called graph state distance of 4-cycle free graphs.
- Score: 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: 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 $\delta$ or
$\delta+1$, where $\delta$ 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.
Related papers
- Near-Asymptotically-Good Quantum Codes with Transversal CCZ Gates and Sublinear-Weight Parity-Checks [18.20811830109862]
We construct the first known quantum codes with linear dimension and distance supporting non-Clifford gates.<n>We design an efficient decoding algorithm for these codes.<n>Our results can be viewed as a new generalization of Prony's method for reconstructing a function from partial access to its transform.
arXiv Detail & Related papers (2025-10-08T09:27:41Z) - On the hardness of approximating minimum distances of quantum codes [2.8636943749206423]
The problem of computing distances of error-correcting codes is fundamental in both the classical and quantum settings.<n>In particular, we get a direct reduction to CSS codes, the most commonly used type of quantum code, from the minimum distance problem for classical linear codes.<n>We show that it is NP-hard to compute/approximate the distance of a graph state when the adjacency matrix of the graph is the input.
arXiv Detail & Related papers (2025-09-25T19:35:49Z) - Creating entangled logical qubits in the heavy-hex lattice with topological codes [0.0]
In this work we show how this bug can be turned into a feature.
We demonstrate entanglement between logical qubits with code distance up to $d = 4$.
We verify the violation of Bell's inequality for both the $d=2$ case with post selection featuring a fidelity of $94%$.
arXiv Detail & Related papers (2024-04-24T17:02:35Z) - Quantum computation on a 19-qubit wide 2d nearest neighbour qubit array [59.24209911146749]
This paper explores the relationship between the width of a qubit lattice constrained in one dimension and physical thresholds.
We engineer an error bias at the lowest level of encoding using the surface code.
We then address this bias at a higher level of encoding using a lattice-surgery surface code bus.
arXiv Detail & Related papers (2022-12-03T06:16:07Z) - A lower bound on the space overhead of fault-tolerant quantum computation [51.723084600243716]
The threshold theorem is a fundamental result in the theory of fault-tolerant quantum computation.
We prove an exponential upper bound on the maximal length of fault-tolerant quantum computation with amplitude noise.
arXiv Detail & Related papers (2022-01-31T22:19:49Z) - Benchmarking Small-Scale Quantum Devices on Computing Graph Edit
Distance [52.77024349608834]
Graph Edit Distance (GED) measures the degree of (dis)similarity between two graphs in terms of the operations needed to make them identical.
In this paper we present a comparative study of two quantum approaches to computing GED.
arXiv Detail & Related papers (2021-11-19T12:35:26Z) - Quantifying nonlocality: how outperforming local quantum codes is
expensive [0.06091702876917279]
Quantum low-density parity-check (LDPC) codes are a promising avenue to reduce the cost of constructing scalable quantum circuits.
We show that quantum LDPC codes implemented through local interactions obey restrictions on their dimension $k$ and distance $d$.
In particular, in 2D we show that a quantum LDPC with distance $n1/2 + epsilon$ code requires $Omega(n1/2 + epsilon)$ interactions of length $widetildeOmega(nepsilon)$.
arXiv Detail & Related papers (2021-09-22T18:55:45Z) - Finding the disjointness of stabilizer codes is NP-complete [77.34726150561087]
We show that the problem of calculating the $c-disjointness, or even approximating it to within a constant multiplicative factor, is NP-complete.
We provide bounds on the disjointness for various code families, including the CSS codes,$d codes and hypergraph codes.
Our results indicate that finding fault-tolerant logical gates for generic quantum error-correcting codes is a computationally challenging task.
arXiv Detail & Related papers (2021-08-10T15:00:20Z) - The Diagonal Distance of CWS Codes [0.0]
The diagonal distance of a quantum code is an important parameter that characterizes if the quantum code is degenerate or not.
We show that most of the CWS codes without a cycle of length four attain the upper bound of diagonal distance d+1.
We show that any degenerate CWS code with graph $G$ and classical code C will either have a short cycle in the graph $G$ or will be such that the classical code C has one of the coordinates trivially zero for all codewords.
arXiv Detail & Related papers (2021-07-23T14:59:29Z) - On Applying the Lackadaisical Quantum Walk Algorithm to Search for
Multiple Solutions on Grids [63.75363908696257]
The lackadaisical quantum walk is an algorithm developed to search graph structures whose vertices have a self-loop of weight $l$.
This paper addresses several issues related to applying the lackadaisical quantum walk to search for multiple solutions on grids successfully.
arXiv Detail & Related papers (2021-06-11T09:43:09Z) - Connectivity constrains quantum codes [0.06091702876917279]
We study the limitations of quantum LDPC codes associated with local graphs in $D$-dimensional hyperbolic space.
We find that unless the connectivity graph contains an expander, the code is severely limited.
As an application, we present novel bounds on quantum LDPC codes associated with local graphs in $D$-dimensional hyperbolic space.
arXiv Detail & Related papers (2021-06-01T20:03:16Z) - Describing quantum metrology with erasure errors using weight
distributions of classical codes [9.391375268580806]
We consider using quantum probe states with a structure that corresponds to classical $[n,k,d]$ binary block codes of minimum distance.
We obtain bounds on the ultimate precision that these probe states can give for estimating the unknown magnitude of a classical field.
arXiv Detail & Related papers (2020-07-06T16:22:40Z) - Quantum Gram-Schmidt Processes and Their Application to Efficient State
Read-out for Quantum Algorithms [87.04438831673063]
We present an efficient read-out protocol that yields the classical vector form of the generated state.
Our protocol suits the case that the output state lies in the row space of the input matrix.
One of our technical tools is an efficient quantum algorithm for performing the Gram-Schmidt orthonormal procedure.
arXiv Detail & Related papers (2020-04-14T11:05:26Z)
This list is automatically generated from the titles and abstracts of the papers in this site.
This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.