PaperlayerView exact revision on arXiv

Source-linked AI summary

On the hardness of approximating minimum distances of quantum codes

Elena Grigorescu, Vatsal Jha, Eric Samperton

arXiv:2509.21469v2quant-phcs.ITmath.IT

TL;DR

The paper addresses the hardness of computing quantum-code distances, following known classical results and recent quantum-code hardness results. It uses hypergraph-product constructions for direct CSS-code reductions and reports hardness for CSS minimum distance, with additive approximation exhibiting a square-root term.

  • Problem

    Classical minimum-distance hardness is known, but hardness for quantum minimum distance was established only recently, motivating further study of the quantum setting.

    Source: §1 · p. 1

  • Method

    The paper uses hypergraph products to construct CSS codes directly from pairs of classical linear codes and reduce classical minimum-distance hardness to CSS minimum distance.

    Source: §1.1 · p. 2, §3 · p. 11

  • Results

    The reduction establishes hardness of CSS minimum distance for non-degenerate hypergraph product codes, while the additive approximation constructions yield a square-root error term.

    Source: §3 · p. 11, §5.2 · p. 16

  • Takeaways & Limitations

    The same square-root additive term appears in the paper's construction and in [KK23], suggesting a possible square-root barrier.

    Source: §5.2 · p. 16

    The reductions apply only to non-degenerate quantum codes; extending them is constrained by the lack of a closed-form relation between constituent classical-code distances and the resulting quantum-code distance.

    Source: §5.6 · p. 17

Abstract

from arXiv · show

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 these problems are also hard in the quantum setting. As our first main result, we reprove this using arguably simpler arguments based on hypergraph product codes. 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. 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 when the adjacency matrix of the graph is the input. In fact, 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.

1 Introduction

The paper addresses the hardness of quantum-code distances, building on known classical hardness and recent quantum results. It uses hypergraph products for direct CSS-code reductions and also studies graph-state distances and their classical coding-theory connections.

1 Introduction

  • Classical minimum-distance hardness was known in exact and approximate settings, while quantum minimum-distance hardness had been established more recently by Kapshikar and Kundu [KK23].The introduction frames scalable fault-tolerant quantum computation as a fundamental challenge.Source: §1 · p. 1, §1.1 · p. 2

1.1 The Setup

  • Hypergraph products provide a direct construction of CSS codes from arbitrary pairs of classical linear codes, avoiding an additional reduction from stabilizer codes to CSS codes.The authors use this framework for their quantum minimum-distance hardness proof.Source: §1.1 · p. 2
  • The paper studies graph-state distance and reports NP-completeness for computing it, including constant-factor multiplicative and cube-root additive approximation hardness.The graph-state distance is considered in the codeword-stabilized framework.Source: §1.1 · pp. 2–3
  • The MinDistDualDist problem also yields hardness for computing the distance of classical codes with rate 1/2.The introduction presents this as a classical consequence of the graph-state results.Source: §1.1 · p. 3
  • The authors also report NP-completeness for graph-state X-distance, including constant-factor multiplicative approximation and additive approximation up to a linear term.They motivate X-distance by bit-flip-channel settings, where errors are X-type.Source: §1.1 · p. 3

1.2 Subsequent Work

  • The introduction notes subsequent manuscripts claiming NP-hardness for linear-term additive approximation of quantum-code distance, and for graph-state distance in one of them.The cited manuscripts are [Ost26] and [Kap26].Source: §1.2 · p. 3

1.3 Organization

  • The paper places its background in Section 2, proves Theorem 1 in Section 3 and Theorems 2 and 3 in Subsections 4.1 and 4.2, then discusses hardness questions in Section 5.The roadmap specifically highlights discussion of AddGapCSSDistτ,ϵ for ϵ > 1.Source: §1.3 · p. 3

2 Preliminaries

This section establishes the classical and quantum code frameworks, defines the distance problems, and reviews CSS, hypergraph product, and graph-state constructions, including the connections from parity-check data and adjacency matrices to the respective definitions. It also characterizes graph states as degenerate stabilizer codes encoding zero logical qubits.

2.1 Classical codes and their distance problems

  • Classical-code preliminaries introduce generator and parity-check matrix representations and frame distance computation as MinDist with multiplicative- and additive-gap decision variants.They also define dual codes and note that a generator matrix for a code is a parity-check matrix for its dual.Source: §2.1 · p. 4

2.2 Quantum codes and their distance problems

  • Quantum-code preliminaries focus on stabilizer codes, whose distance is the least weight of an error violating detectability and determines their error-correction capability.A stabilizer code is the common +1 eigenspace of an abelian Pauli subgroup that excludes −I.Source: §2.2 · pp. 6–7

2.3 CSS codes

  • CSS codes arise from classical binary linear-code pairs satisfying C2⊥ ⊆ C1, with quantum parity-check matrices constrained by H1H2^T = O.For input codes with dimensions k1 and k2, the CSS code encodes k1 + k2 − n logical qubits.Source: §2.3 · p. 7

2.3.1 Hypergraph product codes

  • Hypergraph products combine two classical linear codes into a non-degenerate CSS code, with parameters [[n1n2 + (n1 − k1)(n2 − k2), k1k2, min{d1, d2}]].The construction uses full-rank classical parity-check matrices.Source: §2.3.1 · p. 8

2.4 Graph States

  • Adjacency matrices specify one-dimensional graph states; their distance problems include exact and gap variants, while CWS-code distance is at most the minimum of the classical-code and graph-state distances.Graph-state distance is defined by minimizing wtH(x ∨ z) over nonzero pairs satisfying AGxT = zT.Source: §2.4 · pp. 8–9
  • A graph state on n vertices is a degenerate stabilizer code encoding zero logical qubits.Its stabilizer generators are K_i = X(e_i)Z(u_i), where u_i is the i-th row of the adjacency matrix.Source: §2.4 · p. 9

3 Proof of Theorem 1

The proof reduces classical minimum-distance hardness to CSS codes using hypergraph product codes. It establishes hardness for exact, multiplicative, and additive distance problems, including under a non-degeneracy promise.

3 Proof of Theorem 1

  • For every ϵ ∈ (0, 1], some τ ∈ (0, 1) makes AddGapDistτ,ϵ NP-hard, via a tensor-code reduction.The tensor-code construction keeps the relevant minimum distance at d while setting its length to N = n · ⌈n^(1/ϵ−1)⌉.Source: §3 · p. 10
  • AddGapCSSDist is NP-hard for each 0 < ϵ ≤ 1/2 and some τ > 0, even for non-degenerate CSS codes.The hardness statement is under Karp reductions.Source: §3 · p. 10
  • The hypergraph product reduction preserves the classical code's minimum distance, proving CSSMinDist hardness and hardness of constant-multiplicative approximation.The constructed hypergraph product codes are non-degenerate.Source: §3 · p. 11
  • The additive-gap reduction maps AddGapDistτ,ϵ to AddGapCSSDistτ′,ϵ′ using a repetition code and a hypergraph product, with τ′ = τ/2^(ϵ/(1+ϵ)) and ϵ′ = ϵ/(1+ϵ).The constructed code has length n′ with n^(1+ϵ) ≤ n′ ≤ 2n^(1+ϵ); the source establishes the CSS hardness from the ϵ-parameterized classical problem.Source: §3 · p. 11

4 Hardness for distances of graph states

The paper reduces classical minimum-distance problems to graph-state distance problems, establishing hardness for graph-state distance and for X-type errors. The reductions also yield hardness results for constant-rate classical codes.

4.1 Proof of Theorem 2

  • The reduction gives hardness for constant-multiplicative and n^(1/3)-additive approximations of MinDistDualDist.MinDistDualDist is also NP-hard to compute exactly.Source: §4.1 · p. 11
  • An auxiliary code family is constructed so the minimum of its code and dual-code distances supports the reduction; increasing its length can preserve distance.The paper notes the parity-check matrices can be built efficiently and gives another construction in the appendix.Source: §4.1 · p. 12
  • AddGapGraphDistτ,ϵ is NP-hard for each 0 < ϵ ≤ 1/3 and some τ > 0, under Karp reductions.The reduction also establishes hardness for MultGapGraphDist and AddGapGraphDist.Source: §4.1 · pp. 12–13
  • The graph-distance reduction converts a MinDistDualDist instance into a graph using a symmetric matrix as its adjacency matrix.The intermediate problem concerns the minimum of a code's distance and its dual distance.Source: §4.1 · pp. 11–12
  • The graph-distance construction yields NP-hardness for computing the distance of classical linear codes with rate 1/2.The paper extends this to exact computation and constant-factor and n^(1/3)-additive approximations for constant rates in (0, 1/2].Source: §4.1 · p. 13

4.2 Proof of Theorem 3

  • The map π sends a length-n classical code of distance d to a self-orthogonal length-2n code of distance 2d, yielding hardness for GraphMinDistX and its gap variants.The proof identifies the minimum-weight vector for the X-type graph-state problem with a nonzero vector in π(C).Source: §4.2 · pp. 13–15

5 Discussion and outlook

The discussion identifies limits on additive hardness for hypergraph product codes, considers a possible square-root barrier, and outlines open directions and rate trade-offs. It also notes that the presented reductions apply only to non-degenerate quantum codes.

5.1 Controlling ϵ in AddGapHGPDistτ,ϵ

  • For fixed ϵ > 1/2 and τ > 0, no Karp reduction from MinDist to AddGapHGPDistτ,ϵ exists unless P = NP.The proof considers bounded-size factors, which would permit brute-force decisions, and growing factors, where the distance bound contradicts d1 ≤ n1.Source: §5.1 · p. 15

5.2 A new square-root barrier?

  • Both the hypergraph-product reduction and the distinct reduction of [KK23] yield square-root additive error, suggesting a possible barrier rather than establishing one generally.Proposition 1 constrains improvements using hypergraph product codes; [KK23] has no analogous proposition, though its graphs appear essentially optimal.Source: §5.2 · p. 16

5.3 Can we get a linear approximation for minimum graph state distance and linear codes with rate 1/2?

  • A route to improving the cube-root additive approximation would be an efficiently computable infinite code family whose code and dual distances are both Ω(n); whether it exists remains open.Avoiding the need for such a family is also an open direction.Source: §5.3 · p. 16

5.4 Quantum “nearest codeword problem”

  • The quantum nearest-codeword question could concern projecting states onto the codespace or finding the closest logical Pauli error in Hamming or symplectic weight.The latter is a discrete variant about error operators, not codewords themselves.Source: §5.4 · p. 16

5.5 Rate trade-offs

  • For rate-1/2 classical codes, the HGP construction yields quantum codes of rate 1/5, versus rate 1/4 for the CWS construction in [KK23].The discussion also notes that HGP-code rates can approach 1 when the classical rate approaches 1, if hardness is established for those classical codes.Source: §5.5 · p. 17

5.6 Can the hardness of computing the minimum distance be established for degenerate quantum codes?

  • The reductions in this paper and [KK23] cover only non-degenerate quantum codes; extending them is obstructed by the lack of a closed-form relation between classical and resulting quantum-code distances.The discussion notes that most quantum error-correction codes implemented on hardware are degenerate.Source: §5.6 · p. 17

A.1 Useful facts and results

This appendix collects facts about tensor products of classical codes and introduces a family of binary codes.

A.1 Useful facts and results

  • The tensor product of codes with parameters [n1, k1, d1] and [n2, k2, d2] has parameters [n1n2, k1k2, d1d2].Its dual is described as C1⊥ ⊗ F2^n2 + F2^n1 ⊗ C2⊥, with parameters [n1n2, n1n2 − k1k2, min{d1, d2}].Source: §A.1 · p. 17
  • Lemma 4 cites a binary classical-code family Cm for odd m ≥ 5 with m ≡ 5 mod 6, but the supplied statement does not include its full parameters.The lemma is attributed to [LLD23].Source: §A.1 · p. 17

A.2 An alternative infinite family of codes

The appendix constructs classical codes from graph adjacency matrices and gives a lower bound on their distance and the distance of their duals. A K2,2-free graph with suitable degree supplies the bound, and an infinite efficiently constructible family is obtained.

A.2 An alternative infinite family of codes

  • Because AG is symmetric, the generator matrix [ATG : In] equals [AG : In], so the code defined by [In : AG] and its dual have equal distance.The discussion says the proof extends naturally to codes from K2,t-free graphs, with a lower bound involving vertex degrees and t.Source: §A.2 · p. 18
  • For every n ≥ 7, a K2,2-free graph can be chosen so that the code with parity-check matrix [In : AG] has distance Ω(√n).The stated lemma also gives an infinite family {Ck} with the minimum of code and dual distances Ω(√nk), constructible in polynomial time.Source: §A.2 · p. 18
  • For a graph G on n vertices with the stated degree condition, the code [I : AG] and its Euclidean dual both have parameters [2n, n, d ≥ δ/2].The proof first seeks a K2,2-free graph with large minimum degree.Source: §A.2 · p. 18
  • The graph construction cited for producing K2,2-free graphs applies when n = p2 + p + 1 for a prime p, and runs in polynomial time.It produces a graph whose vertices have degree p or p + 1.Source: §A.2 · p. 19
Loading 2509.21469v2…