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:2510.07298

Fine-Grained Unambiguous Measurements

Quentin Buzet, André Chailloux

Published Oct 8, 2025• 0 citations
arXivHTMLPDF

Abstract

Unambiguous measurements play an important role in quantum information, with applications ranging from quantum key distribution to quantum state reconstruction. Recently, such measurements have also been used in quantum algorithms based on Regev's reduction. The key problem for these algorithms is the S-$|LWE>$ problem in the lattice setting and the Quantum Decoding Problem in the code setting. A key idea for addressing this problem is to use unambiguous measurements to recover $k$ coordinates of a code (or lattice) element $x$ from a quantum state $|ψ_x\rangle$, which corresponds to a noisy word $x$ with errors in quantum superposition. However, a general theoretical framework to analyze this approach has been lacking. In this work, we introduce the notion of fine-grained unambiguous measurements. Given a family of states $\{\,|ψ_x\rangle\,\}_{x\in\{0,1\}^n}$, we ask whether there exist measurements that can return, with certainty, $k$ bits of information about $x$. We study this question in the setting of symmetric states, which naturally arises in the Quantum Decoding Problem. We show that determining the maximal number of parities that a measurement can output can be formulated as a linear program, and we use its dual formulation to derive several upper bounds. In particular, we establish necessary and sufficient conditions for the existence of fine-grained unambiguous measurements and prove impossibility results showing, in particular, that such measurements cannot improve upon the approach of arXiv:2310.20651. Finally, we discuss the implications of these findings for the Quantum Decoding Problem.

DOI
10.48550/arxiv.2510.07298

Related papers

The Quantum Decoding Problem: Tight Achievability Bounds and Application to Regev's Reduction

Agathe Blanvillain, André Chailloux, Jean–Pierre Tillich

We consider the quantum decoding problem. It consists in recovering a codeword given a superposition of noisy versions of this codeword. By measuring the superposition, we get back to the classical decoding problem. It appears for the first time in Chen, Liu and Zhandry’s work showing a quantum advantage for the Short Integer Solution (SIS) problem for thel∞norm. In a recent paper, Chailloux and Tillich proved that when we have a noise following a Bernoulli distribution, the quantum decoding problem can be solved in polynomial time and is therefore easier than classical decoding for which the best known algorithms have an exponential complexity. They also give an information theoretic limit for the code rate at which this problem can be solved which turns out to be above the Shannon limit. In this paper, we generalize the last result to all memoryless noise models. We also show similar results in the rank metric case which corresponds to a noise model which is not memoryless. We analyze the Pretty Good Measurement, from which we derive an information theoretic limit for this problem. By using the algorithm for the quantum decoding problem together with Regev’s reduction, we derive a quantum algorithm sampling codewords from the dual code according to a probability distribution which is the dual of the original noise. It turns out that at the information theoretic limit, we get the most likely nonzero codeword of the dual code. When the distribution is a decreasing function of the weight, we find minimal nonzero codewords. Note that Regev’s reduction used together with classical decoding is much less satisfying since it is not able to output those minimum weight codewords.

arXiv:2509.24796•IEEE Transactions on Information Theory•May 5, 2026•0 citations

Affine Filtering Measurements and Their Applications to Quantum Decoding

Avijit Mandal, Noah Shutty, Henry D. Pfister +1 more

Unambiguous state discrimination (USD) measurements are attractive because outcomes are either marked as conclusive (i.e., error free) or inconclusive (i.e., erased). We study affine filtering measurements, a structured variant of USD for decoding classical linear codes over pure-state classical-quantum channels, where a conclusive outcome identifies an affine subspace containing the transmitted codeword and an inconclusive outcome is treated as an erasure. For a group-covariant indexing of pure-state codewords, we show that the optimal design of affine filtering measurements is a semidefinite program that can be reduced to a linear program via character-based diagonalization. We use the resulting measurement to build a quantum decoding framework for local codes, and we demonstrate (via simulations on regular LDPC codes from Gallager ensembles using single parity check local constraints) that affine filtering based decoding can outperform symbol-wise USD and symbol-wise pretty good measurement based decoding methods on i.i.d. pure-state channels. In an independent and concurrent work, Buzet and Chailloux study similar fine-grained USD measurements for symmetric families of states. Their focus is on the code-agnostic setting whereas our focus is on code-aware constructions and decoding.

quant-pharXiv:2606.07852•Jun 9, 2026•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

Retrodiction of generalized measurement outcomes

Anthony Chefles, Masahide Sasaki

If a generalized measurement is performed on a quantum system and we do not know the outcome, are we able to retrodict it with a second measurement? We obtain a necessary and sufficient condition for perfect retrodiction of the outcome of a known generalized measurement, given the final state, for an arbitrary initial state. From this, we deduce that, when the input and output Hilbert spaces have equal (finite) dimension, it is impossible to perfectly retrodict the outcome of any fine-grained measurement [where each positive, operator-valued measure (POVM) element corresponds to a single Kraus operator] for all initial states unless the measurement is unitarily equivalent to a projective measurement. It also enables us to show that every POVM can be realized in such a way that perfect outcome retrodiction is possible for an arbitrary initial state when the number of outcomes does not exceed the output Hilbert space dimension. We then consider the situation where the initial state is not arbitrary, though it may be entangled, and describe the conditions under which unambiguous outcome retrodiction is possible for a fine-grained generalized measurement. We find that this is possible for some state if the Kraus operators are linearly independent. This condition is also necessary when the Kraus operators are nonsingular. From this, we deduce that every trace-preserving quantum operation is associated with a generalized measurement whose outcome is unambiguously retrodictable for some initial state, and also that a set of unitary operators can be unambiguously discriminated iff they are linearly independent. We then examine the issue of unambiguous outcome retrodiction without entanglement. This has important connections with the theory of locally linearly dependent and locally linearly independent operators.

arXiv:quant-ph/0205091•Physical Review A•Mar 28, 2003•26 citations

OPI x Soft Decoders

André Chailloux

In recent years, a particularly interesting line of research has focused on designing quantum algorithms for code and lattice problems inspired by Regev's reduction. The core idea is to use a decoder for a given code to find short codewords in its dual. For example, Jordan et al. demonstrated how structured codes can be used in this framework to exhibit some quantum advantage. In particular, they showed how the classical decodability of Reed-Solomon codes can be leveraged to solve the Optimal Polynomial Intersection (OPI) problem quantumly. This approach was further improved by Chailloux and Tillich using stronger soft decoders, though their analysis was restricted to a specific setting of OPI. In this work, we reconcile these two approaches. We build on a recent formulation of the reduction by Chailloux and Hermouet in the lattice-based setting, which we rewrite in the language of codes. With this reduction, we show that the results of Jordan et al. can be recovered under Bernoulli noise models, simplifying the analysis. This characterization then allows us to integrate the stronger soft decoders of Chailloux and Tillich into the OPI framework, yielding improved algorithms.

quant-pharXiv:2511.22691•Nov 28, 2025•0 citations

Unambiguous unitary quantum channels

Shengjun Wu, X.-M. Chen

Unambiguous unitary maps and unambiguous unitary quantum channels are introduced and some of their properties are derived. These properties ensures certain simple form for the measurements involved in realizing an unambiguous unitary quantum channel. Error correction and unambiguous error correction with nonzero probability are discussed in terms of unambiguous unitary quantum channels. We not only re-derive the well-known condition for a set of errors to be correctable with certainty, but also obtain a necessary and sufficient condition for the errors caused by a noisy channel to be correctable with any nonzero probability. Dense coding with a partially entangled state can also be viewed as an unambiguous unitary quantum channel when all messages are required to be transmitted with equal probability of success, the maximal achievable probability of success is derived and the optimum protocol is also obtained.

arXiv:quant-ph/0509212•Quantum Information and Computation•Nov 1, 2007•0 citations
Unambiguous measurements play an important role in quantum information, with applications ranging from quantum key distribution to quantum state reconstruction. Recently, such measurements have also been used in quantum algorithms based on Regev's reduction. The key problem for these algorithms is the S-∣LWE>|LWE>∣LWE> problem in the lattice setting and the Quantum Decoding Problem in the code setting. A key idea for addressing this problem is to use unambiguous measurements to recover kkk coordinates of a code (or lattice) element xxx from a quantum state ∣ψx⟩|ψ_x\rangle∣ψx​⟩, which corresponds to a noisy word xxx with errors in quantum superposition. However, a general theoretical framework to analyze this approach has been lacking. In this work, we introduce the notion of fine-grained unambiguous measurements. Given a family of states { ∣ψx⟩ }x∈{0,1}n\{\,|ψ_x\rangle\,\}_{x\in\{0,1\}^n}{∣ψx​⟩}x∈{0,1}n​, we ask whether there exist measurements that can return, with certainty, kkk bits of information about xxx. We study this question in the setting of symmetric states, which naturally arises in the Quantum Decoding Problem. We show that determining the maximal number of parities that a measurement can output can be formulated as a linear program, and we use its dual formulation to derive several upper bounds. In particular, we establish necessary and sufficient conditions for the existence of fine-grained unambiguous measurements and prove impossibility results showing, in particular, that such measurements cannot improve upon the approach of arXiv:2310.20651. Finally, we discuss the implications of these findings for the Quantum Decoding Problem.
We consider the quantum decoding problem. It consists in recovering a codeword given a superposition of noisy versions of this codeword. By measuring the superposition, we get back to the classical decoding problem. It appears for the first time in Chen, Liu and Zhandry’s work showing a quantum advantage for the Short Integer Solution (SIS) problem for thel∞norm. In a recent paper, Chailloux and Tillich proved that when we have a noise following a Bernoulli distribution, the quantum decoding problem can be solved in polynomial time and is therefore easier than classical decoding for which the best known algorithms have an exponential complexity. They also give an information theoretic limit for the code rate at which this problem can be solved which turns out to be above the Shannon limit. In this paper, we generalize the last result to all memoryless noise models. We also show similar results in the rank metric case which corresponds to a noise model which is not memoryless. We analyze the Pretty Good Measurement, from which we derive an information theoretic limit for this problem. By using the algorithm for the quantum decoding problem together with Regev’s reduction, we derive a quantum algorithm sampling codewords from the dual code according to a probability distribution which is the dual of the original noise. It turns out that at the information theoretic limit, we get the most likely nonzero codeword of the dual code. When the distribution is a decreasing function of the weight, we find minimal nonzero codewords. Note that Regev’s reduction used together with classical decoding is much less satisfying since it is not able to output those minimum weight codewords.
Unambiguous state discrimination (USD) measurements are attractive because outcomes are either marked as conclusive (i.e., error free) or inconclusive (i.e., erased). We study affine filtering measurements, a structured variant of USD for decoding classical linear codes over pure-state classical-quantum channels, where a conclusive outcome identifies an affine subspace containing the transmitted codeword and an inconclusive outcome is treated as an erasure. For a group-covariant indexing of pure-state codewords, we show that the optimal design of affine filtering measurements is a semidefinite program that can be reduced to a linear program via character-based diagonalization. We use the resulting measurement to build a quantum decoding framework for local codes, and we demonstrate (via simulations on regular LDPC codes from Gallager ensembles using single parity check local constraints) that affine filtering based decoding can outperform symbol-wise USD and symbol-wise pretty good measurement based decoding methods on i.i.d. pure-state channels. In an independent and concurrent work, Buzet and Chailloux study similar fine-grained USD measurements for symmetric families of states. Their focus is on the code-agnostic setting whereas our focus is on code-aware constructions and decoding.
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.
If a generalized measurement is performed on a quantum system and we do not know the outcome, are we able to retrodict it with a second measurement? We obtain a necessary and sufficient condition for perfect retrodiction of the outcome of a known generalized measurement, given the final state, for an arbitrary initial state. From this, we deduce that, when the input and output Hilbert spaces have equal (finite) dimension, it is impossible to perfectly retrodict the outcome of any fine-grained measurement [where each positive, operator-valued measure (POVM) element corresponds to a single Kraus operator] for all initial states unless the measurement is unitarily equivalent to a projective measurement. It also enables us to show that every POVM can be realized in such a way that perfect outcome retrodiction is possible for an arbitrary initial state when the number of outcomes does not exceed the output Hilbert space dimension. We then consider the situation where the initial state is not arbitrary, though it may be entangled, and describe the conditions under which unambiguous outcome retrodiction is possible for a fine-grained generalized measurement. We find that this is possible for some state if the Kraus operators are linearly independent. This condition is also necessary when the Kraus operators are nonsingular. From this, we deduce that every trace-preserving quantum operation is associated with a generalized measurement whose outcome is unambiguously retrodictable for some initial state, and also that a set of unitary operators can be unambiguously discriminated iff they are linearly independent. We then examine the issue of unambiguous outcome retrodiction without entanglement. This has important connections with the theory of locally linearly dependent and locally linearly independent operators.
In recent years, a particularly interesting line of research has focused on designing quantum algorithms for code and lattice problems inspired by Regev's reduction. The core idea is to use a decoder for a given code to find short codewords in its dual. For example, Jordan et al. demonstrated how structured codes can be used in this framework to exhibit some quantum advantage. In particular, they showed how the classical decodability of Reed-Solomon codes can be leveraged to solve the Optimal Polynomial Intersection (OPI) problem quantumly. This approach was further improved by Chailloux and Tillich using stronger soft decoders, though their analysis was restricted to a specific setting of OPI. In this work, we reconcile these two approaches. We build on a recent formulation of the reduction by Chailloux and Hermouet in the lattice-based setting, which we rewrite in the language of codes. With this reduction, we show that the results of Jordan et al. can be recovered under Bernoulli noise models, simplifying the analysis. This characterization then allows us to integrate the stronger soft decoders of Chailloux and Tillich into the OPI framework, yielding improved algorithms.
Unambiguous unitary maps and unambiguous unitary quantum channels are introduced and some of their properties are derived. These properties ensures certain simple form for the measurements involved in realizing an unambiguous unitary quantum channel. Error correction and unambiguous error correction with nonzero probability are discussed in terms of unambiguous unitary quantum channels. We not only re-derive the well-known condition for a set of errors to be correctable with certainty, but also obtain a necessary and sufficient condition for the errors caused by a noisy channel to be correctable with any nonzero probability. Dense coding with a partially entangled state can also be viewed as an unambiguous unitary quantum channel when all messages are required to be transmitted with equal probability of success, the maximal achievable probability of success is derived and the optimum protocol is also obtained.