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

Quantum List Decoding from Quantumly Corrupted Codewords for Classical Block Codes of Polynomially Small Rate

Tomoyuki Yamakami

Published Oct 23, 2006• 0 citations
OpenAlex

Abstract

Our task of quantum list decoding for a classical block code is to recover from a given quantumly corrupted codeword a short list containing all messages whose codewords have high "presence" in this quantumly corrupted codeword. All known families of efficiently quantum list decodable codes, nonetheless, have exponentially-small message rate. We show that certain generalized Reed-Solomon codes concatenated with Hadamard codes of polynomially-small rate and constant codeword alphabet size have efficient quantum list decoding algorithms, provided that target codewords should have relatively high presence in a given quantumly corrupted codeword.

Related papers

Quantum List Decoding of Classical Block Codes of Polynomially Small Rate from Quantumly Corrupted Codewords

Tomoyuki Yamakami

Given a classical error-correcting block code, the task of quantum list decoding is to produce from any quantumly corrupted codeword a short list containing all messages whose codewords exhibit high "presence" in the quantumly corrupted codeword.Efficient quantum list decoders have been used to prove a quantum hardcore property of classical codes.However, the code rates of all known families of efficiently quantum list-decodable codes are, unfortunately, too small for other practical applications.To improve those known code rates, we prove that a specific code family of polynomially small code rate over a fixed code alphabet, obtained by concatenating generalized Reed-Solomon codes as outer codes with Hadamard codes as inner codes, has an efficient quantum list-decoding algorithm if its codewords have relatively high codeword presence in a given quantumly corrupted codeword.As an immediate application, we use the quantum list decodability of this code family to solve a certain form of quantum search problems in polynomial time.When the codeword presence becomes smaller, in contrast, we show that the quantum list decodability of generalized Reed-Solomon codes with high confidence is closely related to the efficient solvability of the following two problems: the noisy polynomial interpolation problem and the bounded distance vector problem.Moreover, assuming that NP BQP, we also prove that no efficient quantum list decoder exists for the generalized Reed-Solomon codes.

Baltic Journal of Modern Computing•Dec 19, 2016•1 citation

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•17 citations

Explicit Capacity-Achieving Quantum LDPC Codes List Decodable in Near-linear Time

William Gay, Fernando Granha Jeronimo, Abhi Shukul

In classical coding theory, the quest for explicit codes achieving list decoding capacity has been an important driving force. While random codes are easily shown to achieve capacity, an explicit construction was only discovered decades later in the seminal work [Guruswami and Rudra, STOC 2006]. In quantum coding theory, it is highly desirable that a code family be LDPC. While good quantum codes were known for decades, obtaining the additional LDPC property was elusive. In fact, only very recently that good quantum LDPC codes were discovered in a breakthrough work [Panteleev and Kalachev, STOC 2022]. In this context, a natural question is to ask for an explicit family of quantum codes achieving list decoding capacity while also possessing the important LDPC property. In this work, we provide (to the best of our knowledge) the first explicit constructions of quantum LDPC codes achieving list decoding capacity, namely, with a list decoding radius approaching the quantum Singleton bound with constant list sizes. Furthermore, we provide near-linear time (in the block-length) list decoding algorithms approaching capacity. Our explicit code construction are based on expander graphs via the quantum analogue of Alon-Edmonds-Luby (AEL) amplification [Bergamaschi, Golowich and Gunn, STOC 2024], and this enables the important LDPC property. Our efficient list decoding algorithms are obtained by generalizing the classical expander-based weak-regularity list decoding algorithms [Srivastava and Tulsiani, FOCS 2025] [Jeronimo and Singh, 2025] to suitable instantiations of quantum AEL.

quant-pharXiv:2609.40313•Oct 1, 2026•1 citation

Noisy Decoding by Shallow Circuits with Parities: Classical and Quantum (Extended Abstract)

Jop Briët, Harry Buhrman, Davi Castro-Silva +1 more

We consider the problem of decoding corrupted error correcting codes with NC$^0[\oplus]$ circuits in the classical and quantum settings. We show that any such 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. Previously this was known only for linear codes with large dual distance, whereas our result applies to any code. By contrast, we give a simple quantum circuit that correctly decodes the Hadamard code with probability $Ω(\varepsilon^2)$ even if a $(1/2 - \varepsilon)$-fraction of a codeword is adversarially corrupted. Our classical hardness result is based on an equidistribution phenomenon for multivariate polynomials over a finite field under biased input-distributions. This is proved using a structure-versus-randomness strategy based on a new notion of rank for high-dimensional polynomial maps that may be of independent interest. Our quantum circuit is inspired by a non-local version of the Bernstein-Vazirani problem, a technique to generate ``poor man's cat states'' by Watts et al., and a constant-depth quantum circuit for the OR function by Takahashi and Tani.

arXiv:2302.02870•Leibniz international proceedings in informatics•Feb 6, 2023•9 citations

Quantum error correction in adversarial regimes

Anonymous, Nikhil Bansal, Dax Enshan Koh +2 more

In adversarial settings, where attackers can deliberately and strategically corrupt quantum data, standard quantum error correction reaches its limits. It can only correct up to half the code distance and must output a unique answer. Quantum list decoding offers a promising alternative. By allowing the decoder to output a short list of possible errors, it becomes possible to tolerate far more errors, even under worst-case noise. But two fundamental questions remain: which quantum codes support list decoding, and can we design decoding schemes that are secure against efficient, computationally bounded adversaries? In this work, we answer both. To identify which codes are list-decodable, we provide a generalized version of the Knill-Laflamme conditions. Then, using tools from quantum cryptography, we build an unambiguous list decoding protocol based on pseudorandom unitaries. Our scheme is secure against any quantum polynomial-time adversary, even across multiple decoding attempts, in contrast to previous schemes. Our approach connects coding theory with complexity-based quantum cryptography, paving the way for secure quantum information processing in adversarial settings.

arXiv:2509.08943•Physical Review A•Aug 4, 2026•2 citations

Quantum Generalized Reed-Solomon codes concatenated with random rate one inner stabilizer codes asymptotically attain the Quantum Gilbert-Varshamov bound

Yingkai Ouyang

AbstractA good quantum code corrects for a linear number of errors. It has been shownthat random codes attains the QGVB with a relative distance H −1q 2 ((1−R)/2) wherethe code is q-ary and R is the rate of the code (number of encoded systems / blocklength). However,randomcodeshavelittlestructure. Inthispaper,westudyafamilyofconcatenatedq-arystabilizercodes. Eachoftheinnercodesisarandomrate1q-arystabilizer code of block length n. The outer code is a quantum MDS code with blocklengthq n andalphabetsizeq n ,anarbitraryrateR≤1,anddistanceN(1−R)/2+1thatmeets the Quantum Singleton bound. Fixing the outer code rate and letting n grow,the concatenated stabilizer code has a distance that almost surely attains the QGVB.This partially generalizes Thommesen’s result, where heshowed thatthedistanceof aconcatenated code with a Reed-Solomon outer code and random inner linear codes ofarbitraryrateattainstheGilbert-Varshamovboundalmostsurely. 1 Introduction A family of q-ary quantum codes of increasing block length is defined to be good if the ratioof its distance to its block length approaches a non-zero constant. Designing good quantumcodes is highly nontrivial, just as it is in the classical case. The quantum Gilbert-Varshamovbound (QGVB) is a lower bound on an achievable relative distance of a quantum code ofa fixed rate. Explicit constructions of good quantum codes for q ≤ 7 have been studied[1, 2, 3], but they all fail to satisfy the QGVB. The QGVB bound is attainable for the familyof all random quantum codes [4], the family of random stabilizer codes [5], and the familyof random nondegenerate stabilizer codes [6], and the family of random degenerate stabilizercodes [6]. We show that concatenated quantum codes, with a quantum outer code havinga known structure and being efficiently decodable, and randomly chosen independent innerquantum codes also attains the QGVB. Thus our family of random quantum codes has morestructure than previously studied examples.In this paper, we generalize a special case of Thommesen’s result [7] to the quantumcase. He showed that a code from the family of binary concatenated codes made with a1

•Apr 7, 2010•0 citations
Our task of quantum list decoding for a classical block code is to recover from a given quantumly corrupted codeword a short list containing all messages whose codewords have high "presence" in this quantumly corrupted codeword. All known families of efficiently quantum list decodable codes, nonetheless, have exponentially-small message rate. We show that certain generalized Reed-Solomon codes concatenated with Hadamard codes of polynomially-small rate and constant codeword alphabet size have efficient quantum list decoding algorithms, provided that target codewords should have relatively high presence in a given quantumly corrupted codeword.
Given a classical error-correcting block code, the task of quantum list decoding is to produce from any quantumly corrupted codeword a short list containing all messages whose codewords exhibit high "presence" in the quantumly corrupted codeword.Efficient quantum list decoders have been used to prove a quantum hardcore property of classical codes.However, the code rates of all known families of efficiently quantum list-decodable codes are, unfortunately, too small for other practical applications.To improve those known code rates, we prove that a specific code family of polynomially small code rate over a fixed code alphabet, obtained by concatenating generalized Reed-Solomon codes as outer codes with Hadamard codes as inner codes, has an efficient quantum list-decoding algorithm if its codewords have relatively high codeword presence in a given quantumly corrupted codeword.As an immediate application, we use the quantum list decodability of this code family to solve a certain form of quantum search problems in polynomial time.When the codeword presence becomes smaller, in contrast, we show that the quantum list decodability of generalized Reed-Solomon codes with high confidence is closely related to the efficient solvability of the following two problems: the noisy polynomial interpolation problem and the bounded distance vector problem.Moreover, assuming that NP BQP, we also prove that no efficient quantum list decoder exists for the generalized Reed-Solomon codes.
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.
In classical coding theory, the quest for explicit codes achieving list decoding capacity has been an important driving force. While random codes are easily shown to achieve capacity, an explicit construction was only discovered decades later in the seminal work [Guruswami and Rudra, STOC 2006]. In quantum coding theory, it is highly desirable that a code family be LDPC. While good quantum codes were known for decades, obtaining the additional LDPC property was elusive. In fact, only very recently that good quantum LDPC codes were discovered in a breakthrough work [Panteleev and Kalachev, STOC 2022]. In this context, a natural question is to ask for an explicit family of quantum codes achieving list decoding capacity while also possessing the important LDPC property. In this work, we provide (to the best of our knowledge) the first explicit constructions of quantum LDPC codes achieving list decoding capacity, namely, with a list decoding radius approaching the quantum Singleton bound with constant list sizes. Furthermore, we provide near-linear time (in the block-length) list decoding algorithms approaching capacity. Our explicit code construction are based on expander graphs via the quantum analogue of Alon-Edmonds-Luby (AEL) amplification [Bergamaschi, Golowich and Gunn, STOC 2024], and this enables the important LDPC property. Our efficient list decoding algorithms are obtained by generalizing the classical expander-based weak-regularity list decoding algorithms [Srivastava and Tulsiani, FOCS 2025] [Jeronimo and Singh, 2025] to suitable instantiations of quantum AEL.
We consider the problem of decoding corrupted error correcting codes with NC0[⊕]^0[\oplus]0[⊕] circuits in the classical and quantum settings. We show that any such 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. Previously this was known only for linear codes with large dual distance, whereas our result applies to any code. By contrast, we give a simple quantum circuit that correctly decodes the Hadamard code with probability Ω(ε2)Ω(\varepsilon^2)Ω(ε2) even if a (1/2−ε)(1/2 - \varepsilon)(1/2−ε)-fraction of a codeword is adversarially corrupted. Our classical hardness result is based on an equidistribution phenomenon for multivariate polynomials over a finite field under biased input-distributions. This is proved using a structure-versus-randomness strategy based on a new notion of rank for high-dimensional polynomial maps that may be of independent interest. Our quantum circuit is inspired by a non-local version of the Bernstein-Vazirani problem, a technique to generate ``poor man's cat states'' by Watts et al., and a constant-depth quantum circuit for the OR function by Takahashi and Tani.
In adversarial settings, where attackers can deliberately and strategically corrupt quantum data, standard quantum error correction reaches its limits. It can only correct up to half the code distance and must output a unique answer. Quantum list decoding offers a promising alternative. By allowing the decoder to output a short list of possible errors, it becomes possible to tolerate far more errors, even under worst-case noise. But two fundamental questions remain: which quantum codes support list decoding, and can we design decoding schemes that are secure against efficient, computationally bounded adversaries? In this work, we answer both. To identify which codes are list-decodable, we provide a generalized version of the Knill-Laflamme conditions. Then, using tools from quantum cryptography, we build an unambiguous list decoding protocol based on pseudorandom unitaries. Our scheme is secure against any quantum polynomial-time adversary, even across multiple decoding attempts, in contrast to previous schemes. Our approach connects coding theory with complexity-based quantum cryptography, paving the way for secure quantum information processing in adversarial settings.
AbstractA good quantum code corrects for a linear number of errors. It has been shownthat random codes attains the QGVB with a relative distance H −1q 2 ((1−R)/2) wherethe code is q-ary and R is the rate of the code (number of encoded systems / blocklength). However,randomcodeshavelittlestructure. Inthispaper,westudyafamilyofconcatenatedq-arystabilizercodes. Eachoftheinnercodesisarandomrate1q-arystabilizer code of block length n. The outer code is a quantum MDS code with blocklengthq n andalphabetsizeq n ,anarbitraryrateR≤1,anddistanceN(1−R)/2+1thatmeets the Quantum Singleton bound. Fixing the outer code rate and letting n grow,the concatenated stabilizer code has a distance that almost surely attains the QGVB.This partially generalizes Thommesen’s result, where heshowed thatthedistanceof aconcatenated code with a Reed-Solomon outer code and random inner linear codes ofarbitraryrateattainstheGilbert-Varshamovboundalmostsurely. 1 Introduction A family of q-ary quantum codes of increasing block length is defined to be good if the ratioof its distance to its block length approaches a non-zero constant. Designing good quantumcodes is highly nontrivial, just as it is in the classical case. The quantum Gilbert-Varshamovbound (QGVB) is a lower bound on an achievable relative distance of a quantum code ofa fixed rate. Explicit constructions of good quantum codes for q ≤ 7 have been studied[1, 2, 3], but they all fail to satisfy the QGVB. The QGVB bound is attainable for the familyof all random quantum codes [4], the family of random stabilizer codes [5], and the familyof random nondegenerate stabilizer codes [6], and the family of random degenerate stabilizercodes [6]. We show that concatenated quantum codes, with a quantum outer code havinga known structure and being efficiently decodable, and randomly chosen independent innerquantum codes also attains the QGVB. Thus our family of random quantum codes has morestructure than previously studied examples.In this paper, we generalize a special case of Thommesen’s result [7] to the quantumcase. He showed that a code from the family of binary concatenated codes made with a1