Related papers: Near-Asymptotically-Good Quantum Codes with Transversal CCZ Gates and Sublinear-Weight Parity-Checks

Near-Asymptotically-Good Quantum Codes with Transversal CCZ Gates and Sublinear-Weight Parity-Checks

URL: http://arxiv.org/abs/2510.06798v1
Date: Wed, 08 Oct 2025 09:27:41 GMT
Title: Near-Asymptotically-Good Quantum Codes with Transversal CCZ Gates and Sublinear-Weight Parity-Checks
Authors: Louis Golowich, Venkatesan Guruswami,
Abstract summary: 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.
Score: 18.20811830109862
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: It is a major challenge to construct good quantum codes supporting fault-tolerant (e.g. transversal) non-Clifford gates with low-weight parity-check measurements. In this paper, we construct the first known quantum codes with linear dimension and distance supporting transversal non-Clifford gates that have sublinear locality (i.e. parity-check weight). Specifically, we construct codes with transversal $CCZ$ gates that have dimension and distance $\Theta(N)$ and locality $O(\sqrt{N})$, where $N$ denotes the block length. We furthermore design an efficient decoding algorithm for these codes. The alphabet size of these codes is $q=\Theta(\sqrt{N})$, but it can be reduced to a constant (e.g. $q=2$) while incurring a polylogarithmic loss in other parameters. We also show how to decrease the locality to $O(N^{1/3})$, albeit with a larger alphabet size and slightly lower distance. We construct these codes as products of classical codes with appropriate algebraic structure. While our quantum codes are subsystem codes with non-commuting gauge operators, we show they nevertheless permit error correction from noisy syndrome measurements. As byproducts, we prove multiple technical results of independent interest. In particular, our efficient decoder can be viewed as a new multivariate generalization of Prony's method for reconstructing a function from partial access to its Fourier transform. Meanwhile, our distance analysis involves new connections to the classical study of maximally recoverable codes. Our results on product codes also resolve a conjecture of Bravyi & Hastings (2014) in the large-alphabet regime, by providing a new construction of quantum codes with dimension and distance $\Theta(N)$ and locality $N^\epsilon$ for arbitrary $\epsilon>0$.

Related papers

Quantum error correction beyond $SU(2)$: spin, bosonic, and permutation-invariant codes from convex geometry [48.254879700836376]
We develop a framework for constructing quantum error-correcting codes and logical gates for three types of spaces.<n>We prove that many codes and their gates in $SU(q)$ can be inter-converted between the three state spaces.<n>We present explicit constructions of codes with shorter length or lower total spin/excitation than known codes with similar parameters.
arXiv Detail & Related papers (2025-09-24T20:21:30Z)
Parallel Logical Measurements via Quantum Code Surgery [42.95092131256421]
Quantum code surgery is a flexible and low overhead technique for performing logical measurements on quantum error-correcting codes.<n>We present a code surgery scheme, applicable to any qubit stabiliser low-density parity check (LDPC) code, that fault-tolerantly measures many logical Pauli operators in parallel.
arXiv Detail & Related papers (2025-03-06T22:05:52Z)
List Decodable Quantum LDPC Codes [49.2205789216734]
We give a construction of Quantum Low-Density Parity Check (QLDPC) codes with near-optimal rate-distance tradeoff. We get efficiently list decodable QLDPC codes with unique decoders.
arXiv Detail & Related papers (2024-11-06T23:08:55Z)
Quantum LDPC Codes with Transversal Non-Clifford Gates via Products of Algebraic Codes [0.9208007322096533]
We construct an explicit infinite family of quantum LDPC codes supporting a $Cr-1Z$ gate with length $N$, dimension $Kgeq N1-epsilon$, distance $Dgeq N1/r/namepoly(log N)$, and stabilizer weight $wleqoperatorname(log N)$.
arXiv Detail & Related papers (2024-10-18T17:52:59Z)
Asymptotically Good Quantum Codes with Transversal Non-Clifford Gates [23.22566380210149]
We construct quantum codes that support $CCZ$ gates over qudits of arbitrary prime power dimension $q$. The only previously known construction with such linear dimension and distance required a growing alphabet size $q$.
arXiv Detail & Related papers (2024-08-17T16:54:51Z)
SSIP: automated surgery with quantum LDPC codes [55.2480439325792]
We present Safe Surgery by Identifying Pushouts (SSIP), an open-source lightweight Python package for automating surgery between qubit CSS codes. Under the hood, it performs linear algebra over $mathbbF$ governed by universal constructions in the category of chain complexes. We show that various logical measurements can be performed cheaply by surgery without sacrificing the high code distance.
arXiv Detail & Related papers (2024-07-12T16:50:01Z)
Efficiently constructing a quantum uniform superposition over bit strings near a binary linear code [0.0]
We demonstrate that a high fidelity approximation to $| Psi_b rangle$ can be efficiently constructed by a quantum circuit. The technique used to construct these states is of interest and hopefully will have applications beyond codes.
arXiv Detail & Related papers (2024-04-24T18:37:15Z)
Geometrically Local Quantum and Classical Codes from Subdivision [10.357542321841887]
A geometrically local quantum code is an error correcting code situated within $mathbbRD$, where the checks only act on qubits within a fixed spatial distance. Recently, Portnoy made a significant breakthrough with codes achieving optimal dimension and distance up to polylogs. This paper bypasses this step and streamlines the construction by noticing that a family of good quantum low-density parity-check codes, balanced product codes, naturally carries a two-dimensional structure.
arXiv Detail & Related papers (2023-09-28T02:12:38Z)
Quantum Lego Expansion Pack: Enumerators from Tensor Networks [1.489619600985197]
We provide the first tensor network method for computing quantum weight enumerators in the most general form. For non-(Pauli)-stabilizer codes, this constitutes the current best algorithm for computing the code distance. We show that these enumerators can be used to compute logical error rates exactly and thus construct decoders for any i.i.d. single qubit or qudit error channels.
arXiv Detail & Related papers (2023-08-09T18:00:02Z)
Noisy decoding by shallow circuits with parities: classical and quantum [0.0]
We show that any classical circuit can correctly recover only a vanishingly small fraction of messages, if the codewords are sent over a noisy channel with positive error rate. We give a simple quantum circuit that correctly decodes the Hadamard code with probability $Omega(varepsilon2)$ even if a $(1/2 - varepsilon)$-fraction of a codeword is adversarially corrupted.
arXiv Detail & Related papers (2023-02-06T15:37:32Z)
Morphing quantum codes [77.34726150561087]
We morph the 15-qubit Reed-Muller code to obtain the smallest known stabilizer code with a fault-tolerant logical $T$ gate. We construct a family of hybrid color-toric codes by morphing the color code.
arXiv Detail & Related papers (2021-12-02T17:43:00Z)
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)

This list is automatically generated from the titles and abstracts of the papers in this site.