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:2404.16129 · Quantum Information and Computation

Efficiently constructing a quantum uniform superposition over bit strings near a binary linear code

Edward Farhi, Stephen P. Jordan

Published Dec 1, 2024• 1 citation
arXivHTMLPDF

Abstract

We demonstrate that a high fidelity approximation to $\ket{\Psi_b}$, the quantum superposition over all bit strings within Hamming distance $b$ of the codewords of a dimension-$k$ linear code over $\mathbb{Z}_2^n$, can be efficiently constructed by a quantum circuit for large values of $n$, $b$ and $k$ which we characterize. We do numerical experiments at $n=1000$ which back up our claims. The achievable radius $b$ is much larger than the distance out to which known classical algorithms can efficiently find the nearest codeword. Hence, these states cannot be prepared by quantum constuctions that require uncomputing to find the codeword nearest a string. Unlike the analogous states for lattices in $\mathbb{R}^n$, $\ket{\Psi_b}$ is not a useful resource for bounded distance decoding because the relevant overlap falls off too quickly with distance and known classical algorithms do better. Furthermore the overlap calculation can be dequantized. Perhaps these states could be used to solve other code problems. The technique used to construct these states is of interest and hopefully will have applications beyond codes.

DOI
10.26421/qic24.15-16-4

Related papers

An Efficient Quantum Decoder for Prime-Power Fields

Lior Eldar

We consider a version of the nearest-codeword problem on finite fields $\mathbb{F}_q$ using the Manhattan distance, an analog of the Hamming metric for non-binary alphabets. Similarly to other lattice related problems, this problem is NP-hard even up to constant factor approximation. We show, however, that for $q = p^m$ where $p$ is small relative to the code block-size $n$, there is a quantum algorithm that solves the problem in time ${\rm poly}(n)$, for approximation factor $1/n^2$, for any $p$. On the other hand, to the best of our knowledge, classical algorithms can efficiently solve the problem only for much smaller inverse polynomial factors. Hence, the decoder provides an exponential improvement over classical algorithms, and places limitations on the cryptographic security of large-alphabet extensions of code-based cryptosystems like Classic McEliece.

arXiv:2210.11552•Oct 20, 2022•0 citations

The Quantum Decoding Problem

André Chailloux, Jean–Pierre Tillich

One of the founding results of lattice based cryptography is a quantum reduction from the Short Integer Solution problem to the Learning with Errors problem introduced by Regev. It has recently been pointed out by Chen, Liu and Zhandry that this reduction can be made more powerful by replacing the learning with errors problem with a quantum equivalent, where the errors are given in quantum superposition. In the context of codes, this can be adapted to a reduction from finding short codewords to a quantum decoding problem for random linear codes. We therefore consider in this paper the quantum decoding problem, where we are given a superposition of noisy versions of a codeword and we want to recover the corresponding codeword. When we measure the superposition, we get back the usual classical decoding problem for which the best known algorithms are in the constant rate and error-rate regime exponential in the codelength. However, we will show here that when the noise rate is small enough, then the quantum decoding problem can be solved in quantum polynomial time. Moreover, we also show that the problem can in principle be solved quantumly (albeit not efficiently) for noise rates for which the associated classical decoding problem cannot be solved at all for information theoretic reasons. We then revisit Regev's reduction in the context of codes. We show that using our algorithms for the quantum decoding problem in Regev's reduction matches the best known quantum algorithms for the short codeword problem. This shows in some sense the tightness of Regev's reduction when considering the quantum decoding problem and also paves the way for new quantum algorithms for the short codeword problem.

arXiv:2310.20651•Leibniz international proceedings in informatics•Oct 31, 2023•1 citation

Designing quantum circuits for decoding binary linear codes

Hyungkee Yoo, Whan-Hyuk Choi, Yoonjin Lee

Abstract In the coding theory, it is one of the most important research problems to find an efficient algorithm for the decoding process. A quantum computer is an innovative computing device that performs calculations using the principles of quantum mechanics. In this paper, we find a decoding algorithm for binary linear codes using quantum circuits; this is the first time that quantum circuits are used as a main tool for decoding binary linear codes. Our decoding algorithm is mainly based on Grover’s search algorithm. In detail, we study the process of implementing the exhaustive search using quantum circuits for decoding binary linear codes. For our purpose, we design a modified Grover’s algorithm (algorithm 1) using three tools: the matrix multiplier, the Hamming weight counter, and the state indicator. We present algorithm 2, which is a quantum decoding algorithm for binary linear codes. We illustrate algorithm 1 using the [7, 4, 3] Hamming code, and algorithm 2 is implemented by IBM Quantum Composer.

Journal of Physics A Mathematical and Theoretical•Nov 21, 2024•3 citations

Quantum Channel Decoding

Shahab Hamidi-Rad, John Kaewell

Channel Coding is the technique that enables reliable delivery of digital data over unreliable communication channels. For most high performance channel coding techniques, the existing classical algorithms are computationally expensive, making them impractical for throughput-demanding applications with large code sizes. Today’s Noisy Intermediate-Scale Quantum (NISQ) computers, although limited due to a modest number of qubits, short coherence time, and poor gate fidelity, are useful tools for exploring and experimenting with possible solutions to a wide variety of computational problems.In this paper we show how careful initialization of qubits combined with a simple quantum circuit, enables us to perform channel decoding for different linear block codes. We first explain our novel qubit initialization technique which we call "Quantum Soft Decision". We then show how to build a simple quantum circuit based on the Generator or Parity-check matrix using another technique called "Quantum Generator". Using these universal concepts, we implement Quantum Decoders for two different types of linear block codes, namely Hamming codes and Polar codes. Our simple quantum circuits achieve decoding performances comparable with best classical algorithms such as Maximum Likelihood (ML) for Hamming codes and Successive Cancellation (SC) and Successive Cancellation List (SCL) for Polar codes. Using Qiskit, we implemented and compared the decoding performance at different code sizes and noise levels on simulated (both ideal and noisy) quantum computers. Also using Amazon Braket, we verified the algorithm on real quantum computers.

IEEE International Conference on Quantum Computing and Engineering (QCE)•Sep 1, 2022•1 citation

Decoded Quantum Interferometry Beyond Hamming: Rank-Metric and Translation Association Schemes

Alexandre Krajenbrink, Colin Krawchuk, Ansis Rosmanis +1 more

Decoded Quantum Interferometry (DQI) uses coherent decoding and a quantum Fourier transform to find high-quality solutions of structured optimisation problems. Existing analyses are closely tied to Hamming space, which underlies the optimisation objective, Dicke state preparation and the decoding step of the algorithm. Here we extend the core DQI mechanism beyond Hamming space to finite geometries with translation symmetry, where points are grouped into shells by their distance from a basepoint. Mathematically, these geometries are translation association schemes. In this setting the algorithm can be analysed by tracking one amplitude per shell, and biasing the prepared state towards high-quality solutions becomes a finite tridiagonal eigenvalue problem. As a non-Hamming example, we develop an efficient DQI protocol for finding an m x n finite-field matrix with smallest rank difference to a target matrix. Initial states are uniform superpositions over fixed-rank matrices, and Gabidulin codes provide candidates for efficient low-rank decoding up to a cutoff l. For this objective, this finds solutions with an effective-rank proxy near min(m,n)-l, and the corresponding expected score can be converted into a constant-probability bound on the residual rank of a sample. For Gabidulin nearest-codeword instances, a covering-radius obstruction shows that this bound does not imply an additive guarantee for the true optimum, and we do not claim a quantum advantage for the rank-metric construction. The results instead identify the geometric and coding ingredients for DQI beyond Hamming space.

quant-pharXiv:2606.04843•Jun 4, 2026•0 citations

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

Louis Golowich, Venkatesan Guruswami

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 growing linearly in the block length, and have locality growing as the square root of the block length. We furthermore design an efficient decoding algorithm for these codes. The alphabet size of these codes grows as the square root of the block length, but it can be reduced to a constant (e.g. binary) while incurring a polylogarithmic loss in other parameters. We also show how to decrease the locality to the cube root of the block length, 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 linear dimension and distance and small polynomial locality.

arXiv:2510.06798•Annual Symposium on Foundations of Computer Science•Dec 14, 2025•0 citations
We demonstrate that a high fidelity approximation to ∣Ψb⟩\ket{\Psi_b}∣Ψb​⟩, the quantum superposition over all bit strings within Hamming distance bbb of the codewords of a dimension-kkk linear code over Z2n\mathbb{Z}_2^nZ2n​, can be efficiently constructed by a quantum circuit for large values of nnn, bbb and kkk which we characterize. We do numerical experiments at n=1000n=1000n=1000 which back up our claims. The achievable radius bbb is much larger than the distance out to which known classical algorithms can efficiently find the nearest codeword. Hence, these states cannot be prepared by quantum constuctions that require uncomputing to find the codeword nearest a string. Unlike the analogous states for lattices in Rn\mathbb{R}^nRn, ∣Ψb⟩\ket{\Psi_b}∣Ψb​⟩ is not a useful resource for bounded distance decoding because the relevant overlap falls off too quickly with distance and known classical algorithms do better. Furthermore the overlap calculation can be dequantized. Perhaps these states could be used to solve other code problems. The technique used to construct these states is of interest and hopefully will have applications beyond codes.
We consider a version of the nearest-codeword problem on finite fields Fq\mathbb{F}_qFq​ using the Manhattan distance, an analog of the Hamming metric for non-binary alphabets. Similarly to other lattice related problems, this problem is NP-hard even up to constant factor approximation. We show, however, that for q=pmq = p^mq=pm where ppp is small relative to the code block-size nnn, there is a quantum algorithm that solves the problem in time poly(n){\rm poly}(n)poly(n), for approximation factor 1/n21/n^21/n2, for any ppp. On the other hand, to the best of our knowledge, classical algorithms can efficiently solve the problem only for much smaller inverse polynomial factors. Hence, the decoder provides an exponential improvement over classical algorithms, and places limitations on the cryptographic security of large-alphabet extensions of code-based cryptosystems like Classic McEliece.
One of the founding results of lattice based cryptography is a quantum reduction from the Short Integer Solution problem to the Learning with Errors problem introduced by Regev. It has recently been pointed out by Chen, Liu and Zhandry that this reduction can be made more powerful by replacing the learning with errors problem with a quantum equivalent, where the errors are given in quantum superposition. In the context of codes, this can be adapted to a reduction from finding short codewords to a quantum decoding problem for random linear codes. We therefore consider in this paper the quantum decoding problem, where we are given a superposition of noisy versions of a codeword and we want to recover the corresponding codeword. When we measure the superposition, we get back the usual classical decoding problem for which the best known algorithms are in the constant rate and error-rate regime exponential in the codelength. However, we will show here that when the noise rate is small enough, then the quantum decoding problem can be solved in quantum polynomial time. Moreover, we also show that the problem can in principle be solved quantumly (albeit not efficiently) for noise rates for which the associated classical decoding problem cannot be solved at all for information theoretic reasons. We then revisit Regev's reduction in the context of codes. We show that using our algorithms for the quantum decoding problem in Regev's reduction matches the best known quantum algorithms for the short codeword problem. This shows in some sense the tightness of Regev's reduction when considering the quantum decoding problem and also paves the way for new quantum algorithms for the short codeword problem.
Abstract In the coding theory, it is one of the most important research problems to find an efficient algorithm for the decoding process. A quantum computer is an innovative computing device that performs calculations using the principles of quantum mechanics. In this paper, we find a decoding algorithm for binary linear codes using quantum circuits; this is the first time that quantum circuits are used as a main tool for decoding binary linear codes. Our decoding algorithm is mainly based on Grover’s search algorithm. In detail, we study the process of implementing the exhaustive search using quantum circuits for decoding binary linear codes. For our purpose, we design a modified Grover’s algorithm (algorithm 1) using three tools: the matrix multiplier, the Hamming weight counter, and the state indicator. We present algorithm 2, which is a quantum decoding algorithm for binary linear codes. We illustrate algorithm 1 using the [7, 4, 3] Hamming code, and algorithm 2 is implemented by IBM Quantum Composer.
Channel Coding is the technique that enables reliable delivery of digital data over unreliable communication channels. For most high performance channel coding techniques, the existing classical algorithms are computationally expensive, making them impractical for throughput-demanding applications with large code sizes. Today’s Noisy Intermediate-Scale Quantum (NISQ) computers, although limited due to a modest number of qubits, short coherence time, and poor gate fidelity, are useful tools for exploring and experimenting with possible solutions to a wide variety of computational problems.In this paper we show how careful initialization of qubits combined with a simple quantum circuit, enables us to perform channel decoding for different linear block codes. We first explain our novel qubit initialization technique which we call "Quantum Soft Decision". We then show how to build a simple quantum circuit based on the Generator or Parity-check matrix using another technique called "Quantum Generator". Using these universal concepts, we implement Quantum Decoders for two different types of linear block codes, namely Hamming codes and Polar codes. Our simple quantum circuits achieve decoding performances comparable with best classical algorithms such as Maximum Likelihood (ML) for Hamming codes and Successive Cancellation (SC) and Successive Cancellation List (SCL) for Polar codes. Using Qiskit, we implemented and compared the decoding performance at different code sizes and noise levels on simulated (both ideal and noisy) quantum computers. Also using Amazon Braket, we verified the algorithm on real quantum computers.
Decoded Quantum Interferometry (DQI) uses coherent decoding and a quantum Fourier transform to find high-quality solutions of structured optimisation problems. Existing analyses are closely tied to Hamming space, which underlies the optimisation objective, Dicke state preparation and the decoding step of the algorithm. Here we extend the core DQI mechanism beyond Hamming space to finite geometries with translation symmetry, where points are grouped into shells by their distance from a basepoint. Mathematically, these geometries are translation association schemes. In this setting the algorithm can be analysed by tracking one amplitude per shell, and biasing the prepared state towards high-quality solutions becomes a finite tridiagonal eigenvalue problem. As a non-Hamming example, we develop an efficient DQI protocol for finding an m x n finite-field matrix with smallest rank difference to a target matrix. Initial states are uniform superpositions over fixed-rank matrices, and Gabidulin codes provide candidates for efficient low-rank decoding up to a cutoff l. For this objective, this finds solutions with an effective-rank proxy near min(m,n)-l, and the corresponding expected score can be converted into a constant-probability bound on the residual rank of a sample. For Gabidulin nearest-codeword instances, a covering-radius obstruction shows that this bound does not imply an additive guarantee for the true optimum, and we do not claim a quantum advantage for the rank-metric construction. The results instead identify the geometric and coding ingredients for DQI beyond Hamming space.
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 growing linearly in the block length, and have locality growing as the square root of the block length. We furthermore design an efficient decoding algorithm for these codes. The alphabet size of these codes grows as the square root of the block length, but it can be reduced to a constant (e.g. binary) while incurring a polylogarithmic loss in other parameters. We also show how to decrease the locality to the cube root of the block length, 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 linear dimension and distance and small polynomial locality.