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:1608.05089 · Leibniz international proceedings in informatics

Quantum Codes from High-Dimensional Manifolds

Matthew B. Hastings

Published Aug 17, 2016• 27 citations
arXivHTMLPDF

Abstract

We construct toric codes on various high-dimensional manifolds. Assuming a conjecture in geometry we find families of quantum CSS stabilizer codes on $N$ qubits with logarithmic weight stabilizers and distance $N^{1-ε}$ for any $ε>0$. The conjecture is that there is a constant $C>0$ such that for any $n$-dimensional torus ${\mathbb T}^n={\mathbb R}^n/Λ$, where $Λ$ is a lattice, the least volume unoriented $n/2$-dimensional surface (using the Euclidean metric) representing nontrivial homology has volume at least $C^n$ times the volume of the least volume $n/2$-dimensional hyperplane representing nontrivial homology; in fact, it would suffice to have this result for $Λ$ an integral lattice with the surface restricted to faces of a cubulation by unit hypercubes. The main technical result is an estimate of Rankin invariants\cite{rankin} for certain random lattices, showing that in a certain sense they are optimal. Additionally, we construct codes with square-root distance, logarithmic weight stabilizers, and inverse polylogarithmic soundness factor (considered as quantum locally testable codes\cite{qltc}). We also provide an short, alternative proof that the shortest vector in the exterior power of a lattice may be non-split\cite{coulangeon}.

DOI
10.4230/lipics.itcs.2017.25

Related papers

Weight reduction for quantum codes

Mathew B. Hastings

We present an algorithm that takes a CSS stabilizer code as input, and outputs another CSS stabilizer code such that the stabilizer generators all have weights O(1) and such that O(1) generators act on any given qubit. The number of logical qubits is unchanged by the procedure, while we give bounds on the increase in number of physical qubits and in the effect on distance and other code parameters, such as soundness (as a locally testable code) and “cosoundness” (defined later). Applications are discussed, including to codes from high-dimensional manifolds which have logarithmic weight stabilizers. Assuming a conjecture in geometry[11], this allows the construction of CSS stabilizer codes with generator weight O(1) and almost linear distance. Another application of the construction is to increasing the distance to X or Z errors, whichever is smaller, so that the two distances are equal.

arXiv:1611.03790•Quantum Information and Computation•Dec 1, 2017•30 citations

PhD thesis: Homological Quantum Codes Beyond the Toric Code

Nikolas P. Breuckmann

PhD thesis investigating homological quantum codes derived from curved and higher dimensional geometries. In the first part we will consider closed surfaces with constant negative curvature. We show how such surfaces can be constructed and enumerate all quantum codes derived from them which have less than 10.000 physical qubits. For codes that are extremal in a certain sense we perform numerical simulations to determine the value of their threshold. Furthermore, we give evidence that these codes can be used for more overhead efficient storage as compared to the surface code by orders of magnitude. We also show how to read and write the encoded qubits while keeping their connectivity low. In the second part we consider codes in which qubits are layed-out according to a four- dimensional geometry. Such codes allow for much simpler decoding schemes compared to codes which are two-dimensional. In particular, measurements do not necessarily have to be repeated to obtain reliable information about the error and the classical hardware performing the error correction is greatly simplified. We perform numerical simulations to analyze the performance of these codes using decoders based on local updates. We also introduce a novel decoder based on techniques from machine learning and image recognition to decode four-dimensional codes.

arXiv:1802.01520•Feb 5, 2018•5 citations

Homological Product Codes

Sergey B. Bravyi, Matthew B. Hastings

Quantum codes with low-weight stabilizers known as LDPC codes have been actively studied recently due to their simple syndrome readout circuits and potential applications in fault-tolerant quantum computing. However, all families of quantum LDPC codes known to this date suffer from a poor distance scaling limited by the square-root of the code length. This is in a sharp contrast with the classical case where good families of LDPC codes are known that combine constant encoding rate and linear distance. Here we propose the first family of good quantum codes with low-weight stabilizers. The new codes have a constant encoding rate, linear distance, and stabilizers acting on at most $\sqrt{n}$ qubits, where $n$ is the code length. For comparison, all previously known families of good quantum codes have stabilizers of linear weight. Our proof combines two techniques: randomized constructions of good quantum codes and the homological product operation from algebraic topology. We conjecture that similar methods can produce good stabilizer codes with stabilizer weight $n^a$ for any $a>0$. Finally, we apply the homological product to construct new small codes with low-weight stabilizers.

arXiv:1311.0885•Nov 4, 2013•10 citations

Homological product codes

Sergey B. Bravyi, Matthew B. Hastings

Quantum codes with low-weight stabilizers known as LDPC codes have been actively studied recently due to their potential applications in fault-tolerant quantum computing. However, all families of quantum LDPC codes known to this date suffer from a poor distance scaling limited by the square-root of the code length. This is in a sharp contrast with the classical case where good families of LDPC codes are known that combine constant encoding rate and linear distance. Here we propose the first family of good quantum codes with low-weight stabilizers. The new codes have a constant encoding rate, linear distance, and stabilizers acting on at most O(√n) qubits, where n is the code length. For comparison, all previously known families of good quantum codes have stabilizers of linear weight. Our proof combines two techniques: randomized constructions of good quantum codes and the homological product operation from algebraic topology. We conjecture that similar methods can produce good stabilizer codes with stabilizer weight O(nα) for any α > 0.

ACM Symposium on Theory of Computing (STOC)•May 31, 2014•81 citations

Hardness of approximation for minimum-weight decoding of two-dimensional topological quantum codes

Louay Bazzi, Georges Khater

Efficient decoding is essential for the practical realization of fault-tolerant quantum computers. We study the computational complexity of minimum-weight decoding for topological quantum codes. For surface codes under the depolarizing channel, we consider Minimum-Weight decoding, which seeks a minimum-weight Pauli error consistent with both the $X$- and $Z$-syndromes. For color codes under independent $X$- and $Z$-error models, we consider Separate Minimum-Weight decoding. Assuming $P\neq NP$, we establish polynomial additive inapproximability gaps for these problems. Specifically, for the toric code and the $4.8.8$ color code on the torus, there exists a constant $c>0$ such that no polynomial-time algorithm can always produce a solution whose weight is within $cN^{1/14}$ of the optimum, where $N$ is the number of qubits, unless $P=NP$. For the planar surface code, we obtain an $Ω(N^{1/18})$ gap. Our inapproximability results use Håstad's hardness of approximation for MAX-3SAT. Our reduction develops a general, modular framework for embedding logical constraints into coupled primal--dual join problems on a lattice. A key ingredient is a localization argument that controls unintended interactions between different parts of the construction.

quant-pharXiv:2608.17109•Aug 19, 2026•0 citations

A four-dimensional toric code on the D4 lattice: [[16L^4, 6, 2L^2]] with weight-4 X-stabilizers

Raghu Kulkarni

We construct a four-dimensional toric code on the D4 lattice, the densest lattice packing in four dimensions, by placing qubits on the 16L^4 triangles of its Delaunay decomposition into regular 16-cells. Each X-stabilizer acts on the 4 triangles of a tetrahedron, the smallest weight such a check can have, and each Z-stabilizer on the 8 triangles meeting along an edge. We prove that the code is [[16L^4, 6, 2L^2]] for every even L >= 4. A logical operator must cast a shadow covering a two-dimensional cross-section of the torus, and a single triangle shadows an area of at most 1/2, so at least 2L^2 qubits are needed; a close-packed plane of the lattice attains this bound exactly. Because the distance is twice the hypercubic value at equal side length, the code reaches distance d with 4d^2 physical qubits against 6d^2 for the hypercubic four-dimensional toric code. A hook-error analysis shows that the weight-8 checks cost no more at circuit level than the weight-4 ones. Neither sector has point-like excitations, and the code's equal-time slices are the face-centred-cubic lattice. Flat four-space has three regular honeycombs, and this code completes the regular case. All results are verified by published scripts.

•Jul 31, 2026•0 citations
We construct toric codes on various high-dimensional manifolds. Assuming a conjecture in geometry we find families of quantum CSS stabilizer codes on NNN qubits with logarithmic weight stabilizers and distance N1−εN^{1-ε}N1−ε for any ε>0ε>0ε>0. The conjecture is that there is a constant C>0C>0C>0 such that for any nnn-dimensional torus Tn=Rn/Λ{\mathbb T}^n={\mathbb R}^n/ΛTn=Rn/Λ, where ΛΛΛ is a lattice, the least volume unoriented n/2n/2n/2-dimensional surface (using the Euclidean metric) representing nontrivial homology has volume at least CnC^nCn times the volume of the least volume n/2n/2n/2-dimensional hyperplane representing nontrivial homology; in fact, it would suffice to have this result for ΛΛΛ an integral lattice with the surface restricted to faces of a cubulation by unit hypercubes. The main technical result is an estimate of Rankin invariants\cite{rankin} for certain random lattices, showing that in a certain sense they are optimal. Additionally, we construct codes with square-root distance, logarithmic weight stabilizers, and inverse polylogarithmic soundness factor (considered as quantum locally testable codes\cite{qltc}). We also provide an short, alternative proof that the shortest vector in the exterior power of a lattice may be non-split\cite{coulangeon}.
We present an algorithm that takes a CSS stabilizer code as input, and outputs another CSS stabilizer code such that the stabilizer generators all have weights O(1) and such that O(1) generators act on any given qubit. The number of logical qubits is unchanged by the procedure, while we give bounds on the increase in number of physical qubits and in the effect on distance and other code parameters, such as soundness (as a locally testable code) and “cosoundness” (defined later). Applications are discussed, including to codes from high-dimensional manifolds which have logarithmic weight stabilizers. Assuming a conjecture in geometry[11], this allows the construction of CSS stabilizer codes with generator weight O(1) and almost linear distance. Another application of the construction is to increasing the distance to X or Z errors, whichever is smaller, so that the two distances are equal.
PhD thesis investigating homological quantum codes derived from curved and higher dimensional geometries. In the first part we will consider closed surfaces with constant negative curvature. We show how such surfaces can be constructed and enumerate all quantum codes derived from them which have less than 10.000 physical qubits. For codes that are extremal in a certain sense we perform numerical simulations to determine the value of their threshold. Furthermore, we give evidence that these codes can be used for more overhead efficient storage as compared to the surface code by orders of magnitude. We also show how to read and write the encoded qubits while keeping their connectivity low. In the second part we consider codes in which qubits are layed-out according to a four- dimensional geometry. Such codes allow for much simpler decoding schemes compared to codes which are two-dimensional. In particular, measurements do not necessarily have to be repeated to obtain reliable information about the error and the classical hardware performing the error correction is greatly simplified. We perform numerical simulations to analyze the performance of these codes using decoders based on local updates. We also introduce a novel decoder based on techniques from machine learning and image recognition to decode four-dimensional codes.
Quantum codes with low-weight stabilizers known as LDPC codes have been actively studied recently due to their simple syndrome readout circuits and potential applications in fault-tolerant quantum computing. However, all families of quantum LDPC codes known to this date suffer from a poor distance scaling limited by the square-root of the code length. This is in a sharp contrast with the classical case where good families of LDPC codes are known that combine constant encoding rate and linear distance. Here we propose the first family of good quantum codes with low-weight stabilizers. The new codes have a constant encoding rate, linear distance, and stabilizers acting on at most n\sqrt{n}n​ qubits, where nnn is the code length. For comparison, all previously known families of good quantum codes have stabilizers of linear weight. Our proof combines two techniques: randomized constructions of good quantum codes and the homological product operation from algebraic topology. We conjecture that similar methods can produce good stabilizer codes with stabilizer weight nan^ana for any a>0a>0a>0. Finally, we apply the homological product to construct new small codes with low-weight stabilizers.
Quantum codes with low-weight stabilizers known as LDPC codes have been actively studied recently due to their potential applications in fault-tolerant quantum computing. However, all families of quantum LDPC codes known to this date suffer from a poor distance scaling limited by the square-root of the code length. This is in a sharp contrast with the classical case where good families of LDPC codes are known that combine constant encoding rate and linear distance. Here we propose the first family of good quantum codes with low-weight stabilizers. The new codes have a constant encoding rate, linear distance, and stabilizers acting on at most O(√n) qubits, where n is the code length. For comparison, all previously known families of good quantum codes have stabilizers of linear weight. Our proof combines two techniques: randomized constructions of good quantum codes and the homological product operation from algebraic topology. We conjecture that similar methods can produce good stabilizer codes with stabilizer weight O(nα) for any α > 0.
Efficient decoding is essential for the practical realization of fault-tolerant quantum computers. We study the computational complexity of minimum-weight decoding for topological quantum codes. For surface codes under the depolarizing channel, we consider Minimum-Weight decoding, which seeks a minimum-weight Pauli error consistent with both the XXX- and ZZZ-syndromes. For color codes under independent XXX- and ZZZ-error models, we consider Separate Minimum-Weight decoding. Assuming P≠NPP\neq NPP=NP, we establish polynomial additive inapproximability gaps for these problems. Specifically, for the toric code and the 4.8.84.8.84.8.8 color code on the torus, there exists a constant c>0c>0c>0 such that no polynomial-time algorithm can always produce a solution whose weight is within cN1/14cN^{1/14}cN1/14 of the optimum, where NNN is the number of qubits, unless P=NPP=NPP=NP. For the planar surface code, we obtain an Ω(N1/18)Ω(N^{1/18})Ω(N1/18) gap. Our inapproximability results use Håstad's hardness of approximation for MAX-3SAT. Our reduction develops a general, modular framework for embedding logical constraints into coupled primal--dual join problems on a lattice. A key ingredient is a localization argument that controls unintended interactions between different parts of the construction.
We construct a four-dimensional toric code on the D4 lattice, the densest lattice packing in four dimensions, by placing qubits on the 16L^4 triangles of its Delaunay decomposition into regular 16-cells. Each X-stabilizer acts on the 4 triangles of a tetrahedron, the smallest weight such a check can have, and each Z-stabilizer on the 8 triangles meeting along an edge. We prove that the code is [[16L^4, 6, 2L^2]] for every even L >= 4. A logical operator must cast a shadow covering a two-dimensional cross-section of the torus, and a single triangle shadows an area of at most 1/2, so at least 2L^2 qubits are needed; a close-packed plane of the lattice attains this bound exactly. Because the distance is twice the hypercubic value at equal side length, the code reaches distance d with 4d^2 physical qubits against 6d^2 for the hypercubic four-dimensional toric code. A hook-error analysis shows that the weight-8 checks cost no more at circuit level than the weight-4 ones. Neither sector has point-like excitations, and the code's equal-time slices are the face-centred-cubic lattice. Flat four-space has three regular honeycombs, and this code completes the regular case. All results are verified by published scripts.