Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2609.22669

Metric Self-Dual Completion and Optimal Additive Hardness for Quantum and Graph-State Distance

Rafail Ostrovsky

quant-phcs.CCcs.ITSubmitted Sep 19, 2026• Announced Sep 22, 2026• 0 citations
arXivHTMLPDF

Abstract

We prove that the quantum code distance is NP-hard to approximate within an additive error of $c N$, for some constant $c >0$, where $N$ is the number of qubits. Our reductions are deterministic. This improves the previous square-root additive gap to $Ω(N)$ and resolves the explicitly stated linear-gap question of Kapshikar and Kundu. Our result holds for CSS codes with identical $X$- and $Z$-check spaces, and with a constant rate and constant relative distance. For every fixed $λ>1$, there is a constant $c>0$ such that hardness still holds even when every nonidentity stabilizer has weight greater than $λ$ times the quantum distance. We also improve the hardness gap of graph state distance on $N$ vertices of Grigorescu, Jha, and Samperton from cube-root to $Ω(N)$, resolving their explicitly stated open question. Both hardness results are asymptotically optimal since both distances are at most $N$. Our graph state distance hardness result holds for balanced bipartite graphs with a binary adjacency matrix that is its own inverse (mod 2). Our main technique for both hardness bounds above is classical: we show how to convert any code $C$ of length $m$ into a self-dual code $A(C)$ of length $N=Θ(m)$ while exactly doubling the original coset metric. The conversion is deterministic and efficient. We call it the metric self-dual completion of $C$. It comes with a linear embedding $τ: \mathbb F_2^m \hookrightarrow \mathbb F_2^N$. The embedding doubles all Hamming distances between vectors in $\mathbb F_2^m$ and all pairwise distances between corresponding cosets. The embedding also guarantees that all codewords of $A(C)$ of weight at most $2m$ are exactly $τ(C)$.

Related papers

Hardness of Approximating Quantum Code Distance Beyond $\sqrt{N}$

Upendra Kapshikar

We study the computational complexity of approximating the minimum distance of a stabilizer code. Classically, the minimum distance problem is NP-hard to approximate even to within an additive gap linear in the block length. For quantum codes, however, the reductions of Kapshikar and Kundu and of Grigorescu, Jha and Samperton reach only an additive $O(\sqrt{N})$ gap in the block length $N$. We close this gap and, in a separate direction, initiate the fine-grained study of the problem. We show that no randomized algorithm approximates the distance to within an additive $αN$, for a constant $α> 0$, unless $\mathsf{NP} \subseteq \mathsf{coRP}$. In the fine-grained setting, for every $\varepsilon > 0$, no randomized $2^{(1-\varepsilon)κ}\,\mathrm{poly}(N)$-time algorithm computes the distance of a code with $κ$ logical qubits unless SETH falls; and no randomized $2^{o(N)}$-time algorithm approximates the distance to within a linear additive gap, on instances where block length, number of logical qubits, and gap are simultaneously linear, unless non-uniform Gap-ETH falls.

quant-pharXiv:2609.33956•Sep 29, 2026•0 citations

On the Hardness of Approximating Distances of Quantum Codes

Elena Grigorescu, Jha, Vatsal, Eric Samperton

The problem of computing distances of error-correcting codes is fundamental in both the classical and quantum settings. While hardness for the classical version of these problems has been known for some time (in both the exact and approximate settings), it was only recently that Kapshikar and Kundu showed the hardness of these problems for non-degenerate quantum codes. As our first main result, 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. In particular, our proof uses arguably simpler constructions based on hypergraph product codes. Our second set of results considers the distance of a graph state, which is a key parameter for quantum codes obtained via the codeword stabilized formalism. We show that it is NP-hard to compute/approximate the distance of a graph state, which is a degenerate quantum code, when the adjacency matrix of the graph is the input. This establishes hardness for even degenerate quantum codes, which was not known before. Furthermore, we show this is true even if we only consider X-type errors of a graph state. Our techniques, moreover, imply an interesting classical consequence: the hardness of computing or approximating the distance of classical codes with rate equal to 1/2. One of the main motivations of the present work is a question raised by Kapshikar and Kundu concerning the NP-hardness of approximation when there is an additive error proportional to a quantum code's length. We show that no such hardness can hold for hypergraph product codes. These observations suggest the possibility of a new kind of square root barrier.

arXiv:2509.21469•Leibniz international proceedings in informatics•Jan 1, 2025•0 citations

Phantom Codes: Hardness, Rate Optimal qLDPC Constructions, and Distance Limits

Rui Mao, Weixiao Sun, Shengyu Zhang

An $[[n,k,d]]$ stabilizer code is phantom if every in-block logical CNOT gate can be realized by a permutation of its physical qubits. This eliminates the large and complicated physical overhead normally required for logical entangling gates. Yet this symmetry is highly restrictive: phantom codes are rare, the number of logical qubits is limited to $k=O(\log n)$, and no phantom qLDPC family with growing logical dimension was previously known. We make three contributions. 1. We prove that recognizing phantomness of a given stabilizer code is at least as hard as Graph Isomorphism, even for CSS codes encoding only $k=2$ logical qubits. 2. We propose the first rate optimal phantom qLDPC families: for every fixed $D$, our CSS families achieve the maximal logical scaling $k=Θ(\log n)$ and distance $d\geq D$. 3. We prove a distance no-go theorem: every phantom code family with $k=ω(\sqrt{\log n})$ and check weight $w=O(1)$ satisfies $d\leq w$ for sufficiently large $n$. Thus our fixed-distance qLDPC families are distance-scaling optimal at the maximal logical scaling $k=Θ(\log n)$.

quant-pharXiv:2609.16542•Sep 16, 2026•0 citations

Hermitian Hulls of Cyclic Codes and Exact Dual Distances of Extended Linear Codes

Liangdong Lu, Ruipan Yang, Yang Liu +2 more

Let $\mathcal{C}$ be an $[n,k,d]$ linear code over $\F_{q^2}$ with parity-check matrix $H$. The rank $r=\Rank(HH^{\dagger})$ measures how far the Hermitian dual $\mathcal{C}^{\perp_h}$ is from being Hermitian self-orthogonal, and it is the least number of coordinates that must be adjoined to $\mathcal{C}^{\perp_h}$ to make it Hermitian self-orthogonal; equivalently, the Hermitian hull $\mathcal{C}\cap\mathcal{C}^{\perp_h}$ has dimension $(n-k)-r$. In this paper, we develop a structure theory of the Hermitian hull of a cyclic code and apply it to the construction of quantum stabilizer codes. For a cyclic code with defining set $T\subseteq\mathbb{Z}_n$, we show that $r$ is additive over the orbits of the involution $τ(ν)=-qν$ on the $q^2$-cyclotomic cosets and satisfies a parity constraint. A parameter dictionary exhibits $r$ as a gauge trading one-for-one against the code length, and a complementation duality shows that the complement of $T$ realises the logical-qubit count of the quantum code. The extreme values of $r$ are settled by closed subset-sum criteria, and the $τ$-invariant defining sets are shown to be the unique locus on which the Hermitian dual is again cyclic. On the distance side, we determine the Hermitian dual distance of an $r$-fold extension of an arbitrary linear code exactly, and we prove that the admissible extension vectors lie in the image of $HH^{\dagger}$, which reduces the search space from $q^{2(n-k)}$ to $q^{2r}$. Applied to cyclic, quasi-cyclic and BCH codes, the construction improves $23$ best-known parameters in Grassl's code tables, one of them provably optimal.

cs.ITCross-listedarXiv:2607.12242•Jul 15, 2026•0 citations

On the Hardness of the Minimum Distance Problem of Quantum Codes

Upendra Kapshikar, Srijita Kundu

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.

arXiv:2203.04262•IEEE Transactions on Information Theory•Jun 16, 2023•11 citations

Quantum codes from classical annealing

Michael A. Perlin, Matthew Steinberg, Ben Criger

We introduce an adaptive simulated annealing algorithm to search for moderately-sized quantum error-correcting codes with high encoding rates and large distances. Our search targets two classes of stabilizer codes: (1) CSS codes, and (2) a subclass of CSS codes that we call ``self-dual with equivalent logicals'' (SWEL) codes, the latter of which which admit transversal implementations of logical Hadamard and phase gates that can be leveraged to construct fault-tolerant gate sets. The search is guided by an energy function that acts as a surrogate for the logical error rate in a code-capacity noise model, combining code distance with a count of minimum-weight logical operators to resolve the discrete plateaux that impede naïve distance optimization. For block lengths of up to $50$ physical qubits, our search finds state-of-the-art CSS and SWEL codes whose distances frequently meet or exceed the variants of the quantum Gilbert-Varshamov bound. In addition to providing favorable seed codes for fault-tolerant architectures based on code concatenation, the codes found in this work are promising candidates for high-rate code demonstrations on near-term quantum computing hardware.

quant-pharXiv:2607.19574•Jul 23, 2026•0 citations
We prove that the quantum code distance is NP-hard to approximate within an additive error of cNc NcN, for some constant c>0c >0c>0, where NNN is the number of qubits. Our reductions are deterministic. This improves the previous square-root additive gap to Ω(N)Ω(N)Ω(N) and resolves the explicitly stated linear-gap question of Kapshikar and Kundu. Our result holds for CSS codes with identical XXX- and ZZZ-check spaces, and with a constant rate and constant relative distance. For every fixed λ>1λ>1λ>1, there is a constant c>0c>0c>0 such that hardness still holds even when every nonidentity stabilizer has weight greater than λλλ times the quantum distance. We also improve the hardness gap of graph state distance on NNN vertices of Grigorescu, Jha, and Samperton from cube-root to Ω(N)Ω(N)Ω(N), resolving their explicitly stated open question. Both hardness results are asymptotically optimal since both distances are at most NNN. Our graph state distance hardness result holds for balanced bipartite graphs with a binary adjacency matrix that is its own inverse (mod 2).
Our main technique for both hardness bounds above is classical: we show how to convert any code CCC of length mmm into a self-dual code A(C)A(C)A(C) of length N=Θ(m)N=Θ(m)N=Θ(m) while exactly doubling the original coset metric. The conversion is deterministic and efficient. We call it the metric self-dual completion of CCC. It comes with a linear embedding τ:F2m↪F2Nτ: \mathbb F_2^m \hookrightarrow \mathbb F_2^Nτ:F2m​↪F2N​. The embedding doubles all Hamming distances between vectors in F2m\mathbb F_2^mF2m​ and all pairwise distances between corresponding cosets. The embedding also guarantees that all codewords of A(C)A(C)A(C) of weight at most 2m2m2m are exactly τ(C)τ(C)τ(C).
Hardness of Approximating Quantum Code Distance Beyond N\sqrt{N}N​
We study the computational complexity of approximating the minimum distance of a stabilizer code. Classically, the minimum distance problem is NP-hard to approximate even to within an additive gap linear in the block length. For quantum codes, however, the reductions of Kapshikar and Kundu and of Grigorescu, Jha and Samperton reach only an additive O(N)O(\sqrt{N})O(N​) gap in the block length NNN. We close this gap and, in a separate direction, initiate the fine-grained study of the problem. We show that no randomized algorithm approximates the distance to within an additive αNαNαN, for a constant α>0α> 0α>0, unless NP⊆coRP\mathsf{NP} \subseteq \mathsf{coRP}NP⊆coRP. In the fine-grained setting, for every ε>0\varepsilon > 0ε>0, no randomized 2(1−ε)κ poly(N)2^{(1-\varepsilon)κ}\,\mathrm{poly}(N)2(1−ε)κpoly(N)-time algorithm computes the distance of a code with κκκ logical qubits unless SETH falls; and no randomized 2o(N)2^{o(N)}2o(N)-time algorithm approximates the distance to within a linear additive gap, on instances where block length, number of logical qubits, and gap are simultaneously linear, unless non-uniform Gap-ETH falls.
The problem of computing distances of error-correcting codes is fundamental in both the classical and quantum settings. While hardness for the classical version of these problems has been known for some time (in both the exact and approximate settings), it was only recently that Kapshikar and Kundu showed the hardness of these problems for non-degenerate quantum codes. As our first main result, 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. In particular, our proof uses arguably simpler constructions based on hypergraph product codes. Our second set of results considers the distance of a graph state, which is a key parameter for quantum codes obtained via the codeword stabilized formalism. We show that it is NP-hard to compute/approximate the distance of a graph state, which is a degenerate quantum code, when the adjacency matrix of the graph is the input. This establishes hardness for even degenerate quantum codes, which was not known before. Furthermore, we show this is true even if we only consider X-type errors of a graph state. Our techniques, moreover, imply an interesting classical consequence: the hardness of computing or approximating the distance of classical codes with rate equal to 1/2. One of the main motivations of the present work is a question raised by Kapshikar and Kundu concerning the NP-hardness of approximation when there is an additive error proportional to a quantum code's length. We show that no such hardness can hold for hypergraph product codes. These observations suggest the possibility of a new kind of square root barrier.
An [[n,k,d]][[n,k,d]][[n,k,d]] stabilizer code is phantom if every in-block logical CNOT gate can be realized by a permutation of its physical qubits. This eliminates the large and complicated physical overhead normally required for logical entangling gates. Yet this symmetry is highly restrictive: phantom codes are rare, the number of logical qubits is limited to k=O(log⁡n)k=O(\log n)k=O(logn), and no phantom qLDPC family with growing logical dimension was previously known. We make three contributions. 1. We prove that recognizing phantomness of a given stabilizer code is at least as hard as Graph Isomorphism, even for CSS codes encoding only k=2k=2k=2 logical qubits. 2. We propose the first rate optimal phantom qLDPC families: for every fixed DDD, our CSS families achieve the maximal logical scaling k=Θ(log⁡n)k=Θ(\log n)k=Θ(logn) and distance d≥Dd\geq Dd≥D. 3. We prove a distance no-go theorem: every phantom code family with k=ω(log⁡n)k=ω(\sqrt{\log n})k=ω(logn​) and check weight w=O(1)w=O(1)w=O(1) satisfies d≤wd\leq wd≤w for sufficiently large nnn. Thus our fixed-distance qLDPC families are distance-scaling optimal at the maximal logical scaling k=Θ(log⁡n)k=Θ(\log n)k=Θ(logn).
Let C\mathcal{C}C be an [n,k,d][n,k,d][n,k,d] linear code over $\F_{q^2}$ with parity-check matrix HHH. The rank $r=\Rank(HH^{\dagger})$ measures how far the Hermitian dual C⊥h\mathcal{C}^{\perp_h}C⊥h​ is from being Hermitian self-orthogonal, and it is the least number of coordinates that must be adjoined to C⊥h\mathcal{C}^{\perp_h}C⊥h​ to make it Hermitian self-orthogonal; equivalently, the Hermitian hull C∩C⊥h\mathcal{C}\cap\mathcal{C}^{\perp_h}C∩C⊥h​ has dimension (n−k)−r(n-k)-r(n−k)−r. In this paper, we develop a structure theory of the Hermitian hull of a cyclic code and apply it to the construction of quantum stabilizer codes. For a cyclic code with defining set T⊆ZnT\subseteq\mathbb{Z}_nT⊆Zn​, we show that rrr is additive over the orbits of the involution τ(ν)=−qντ(ν)=-qντ(ν)=−qν on the q2q^2q2-cyclotomic cosets and satisfies a parity constraint. A parameter dictionary exhibits rrr as a gauge trading one-for-one against the code length, and a complementation duality shows that the complement of TTT realises the logical-qubit count of the quantum code. The extreme values of rrr are settled by closed subset-sum criteria, and the τττ-invariant defining sets are shown to be the unique locus on which the Hermitian dual is again cyclic. On the distance side, we determine the Hermitian dual distance of an rrr-fold extension of an arbitrary linear code exactly, and we prove that the admissible extension vectors lie in the image of HH†HH^{\dagger}HH†, which reduces the search space from q2(n−k)q^{2(n-k)}q2(n−k) to q2rq^{2r}q2r. Applied to cyclic, quasi-cyclic and BCH codes, the construction improves 232323 best-known parameters in Grassl's code tables, one of them provably optimal.
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 graphGGG, its graph state distance is either$\delta ororor\delta +1,where, where,where\delta istheminimumvertexdegreeofis the minimum vertex degree ofistheminimumvertexdegreeofG$. 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.
We introduce an adaptive simulated annealing algorithm to search for moderately-sized quantum error-correcting codes with high encoding rates and large distances. Our search targets two classes of stabilizer codes: (1) CSS codes, and (2) a subclass of CSS codes that we call ``self-dual with equivalent logicals'' (SWEL) codes, the latter of which which admit transversal implementations of logical Hadamard and phase gates that can be leveraged to construct fault-tolerant gate sets. The search is guided by an energy function that acts as a surrogate for the logical error rate in a code-capacity noise model, combining code distance with a count of minimum-weight logical operators to resolve the discrete plateaux that impede naïve distance optimization. For block lengths of up to 505050 physical qubits, our search finds state-of-the-art CSS and SWEL codes whose distances frequently meet or exceed the variants of the quantum Gilbert-Varshamov bound. In addition to providing favorable seed codes for fault-tolerant architectures based on code concatenation, the codes found in this work are promising candidates for high-rate code demonstrations on near-term quantum computing hardware.