Affine Filtering Measurements and Their Applications to Quantum Decoding
Pith reviewed 2026-06-27 21:27 UTC · model grok-4.3
The pith
For group-covariant pure-state codeword indexing, optimal affine filtering measurements reduce to a linear program and outperform symbol-wise decoding on LDPC codes.
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
Core claim
For a group-covariant indexing of pure-state codewords, the optimal design of affine filtering measurements is a semidefinite program that can be reduced to a linear program via character-based diagonalization. The resulting measurement builds a quantum decoding framework for local codes that outperforms symbol-wise USD and symbol-wise pretty good measurement based decoding on i.i.d. pure-state channels in simulations on regular LDPC codes from Gallager ensembles.
What carries the argument
Affine filtering measurements that return an affine subspace containing the codeword on conclusive outcomes, with optimal design obtained by reducing the semidefinite program to a linear program through character-based diagonalization when the indexing is group-covariant.
If this is right
- The linear program yields efficient computation of measurements for decoding local codes such as those with single parity-check constraints.
- Performance gains appear on i.i.d. pure-state channels for the tested LDPC ensembles.
- The construction is code-aware and produces fine-grained USD measurements tailored to the linear code structure.
- The framework applies directly to decoding classical linear codes transmitted over pure-state channels.
Where Pith is reading between the lines
- The diagonalization technique could be adapted to other symmetric families of states if analogous group structures exist.
- Combining affine filtering with classical message-passing algorithms on the same LDPC graph might produce hybrid decoders.
- Performance on non-i.i.d. or non-pure-state channels remains untested and could limit or extend the observed gains.
- The subspace-identification property may connect to erasure decoding techniques already used in classical coding theory.
Load-bearing premise
The indexing of the pure-state codewords must be group-covariant to permit character-based diagonalization that reduces the semidefinite program to a linear program.
What would settle it
A simulation on regular LDPC codes from Gallager ensembles in which affine filtering decoding shows no performance gain over symbol-wise USD and pretty good measurement methods on i.i.d. pure-state channels, or a group-covariant indexing where the character diagonalization fails to solve the optimal design problem.
Figures
read the original abstract
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.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper introduces affine filtering measurements, a structured form of unambiguous state discrimination (USD) tailored to decoding classical linear codes transmitted over pure-state classical-quantum channels. Under the assumption of group-covariant indexing of the pure-state codewords, the optimal design of these measurements is formulated as a semidefinite program (SDP) that reduces to a linear program (LP) via character-based diagonalization. The resulting measurements are used to construct a quantum decoding framework for local codes. Simulations on regular LDPC codes drawn from Gallager ensembles with single-parity-check constraints are reported to show that this affine-filtering decoder outperforms both symbol-wise USD and symbol-wise pretty-good-measurement decoding on i.i.d. pure-state channels. The work is positioned as code-aware, in contrast to concurrent code-agnostic work by Buzet and Chailloux.
Significance. If the SDP-to-LP reduction is valid and the simulation results are statistically robust, the paper supplies a computationally tractable, code-aware method for designing fine-grained USD measurements that can improve decoding of linear codes on quantum channels. The explicit reduction via character theory is a concrete technical contribution that turns an otherwise general SDP into an efficiently solvable LP, which is a strength when the group-covariant indexing condition can be met.
major comments (3)
- [Abstract, optimal design paragraph; derivation section] Abstract (paragraph on optimal design) and the section deriving the measurement: The central claim that the optimal affine filtering measurement reduces from an SDP to an LP rests entirely on the group-covariant indexing assumption. No explicit construction or proof is supplied showing that a group-covariant indexing of the codewords can always be chosen for arbitrary local codes (or for the specific Gallager LDPC ensembles used in the simulations) without altering the underlying channel or code structure. This assumption is load-bearing for both the efficient construction and the subsequent performance claims.
- [Simulations section] Simulations section (results on Gallager LDPC ensembles): The reported outperformance over symbol-wise USD and PGM lacks error bars, the number of Monte-Carlo trials, dataset size, or any correction for multiple testing. Without these, it is impossible to assess whether the observed gains are statistically significant or reproducible, directly undermining the empirical support for the decoding framework.
- [SDP formulation and reduction section] Section stating the SDP formulation and its reduction: The character-based diagonalization step that converts the SDP into an LP is asserted but the explicit algebraic steps, the relevant representation theory, or a self-contained proof are not provided in sufficient detail to allow independent verification of the reduction.
minor comments (1)
- [Abstract and introduction] The abstract and introduction should state the group-covariant indexing assumption more prominently and earlier, so that readers immediately understand the scope of the claimed LP reduction.
Simulated Author's Rebuttal
We thank the referee for the careful reading and constructive comments. We address each major comment below.
read point-by-point responses
-
Referee: [Abstract, optimal design paragraph; derivation section] Abstract (paragraph on optimal design) and the section deriving the measurement: The central claim that the optimal affine filtering measurement reduces from an SDP to an LP rests entirely on the group-covariant indexing assumption. No explicit construction or proof is supplied showing that a group-covariant indexing of the codewords can always be chosen for arbitrary local codes (or for the specific Gallager LDPC ensembles used in the simulations) without altering the underlying channel or code structure. This assumption is load-bearing for both the efficient construction and the subsequent performance claims.
Authors: The manuscript presents the SDP-to-LP reduction explicitly under the assumption of group-covariant indexing and does not claim or prove that such an indexing can always be chosen for arbitrary local codes. For the Gallager LDPC ensembles in the simulations, the single-parity-check structure permits the required indexing. We will revise the text to clarify the scope of the assumption and the conditions under which the method applies. revision: partial
-
Referee: [Simulations section] Simulations section (results on Gallager LDPC ensembles): The reported outperformance over symbol-wise USD and PGM lacks error bars, the number of Monte-Carlo trials, dataset size, or any correction for multiple testing. Without these, it is impossible to assess whether the observed gains are statistically significant or reproducible, directly undermining the empirical support for the decoding framework.
Authors: We agree that the simulations require additional statistical details for proper evaluation. The revised manuscript will report the number of Monte-Carlo trials, include error bars on the performance curves, specify dataset sizes, and address any relevant statistical considerations. revision: yes
-
Referee: [SDP formulation and reduction section] Section stating the SDP formulation and its reduction: The character-based diagonalization step that converts the SDP into an LP is asserted but the explicit algebraic steps, the relevant representation theory, or a self-contained proof are not provided in sufficient detail to allow independent verification of the reduction.
Authors: We will expand the derivation to include the explicit algebraic steps and a self-contained outline of the representation-theoretic argument underlying the character-based diagonalization, either in the main text or an appendix. revision: yes
Circularity Check
No significant circularity; derivation is self-contained under explicit assumption
full rationale
The paper formulates affine filtering measurements as an optimization problem (SDP) whose reduction to LP is derived from the group-covariant indexing assumption via character-based diagonalization; this is stated as a conditional result rather than a self-definition or fitted prediction. Simulations on Gallager LDPC ensembles evaluate the resulting decoder but do not feed back into the optimization or rely on self-citations. No load-bearing step reduces by construction to its own inputs, and the concurrent independent work is cited without overlap. The central claims remain independent of the evaluation data.
Axiom & Free-Parameter Ledger
Reference graph
Works this paper leans on
-
[1]
arXiv preprint arXiv:2411.12553 , year=
Quantum advantage from soft decoders , author=. arXiv preprint arXiv:2411.12553 , year=
-
[2]
Jordan, Stephen P. and Shutty, Noah and Wootters, Mary and Zalcman, Adam and Schmidhuber, Alexander and King, Robbie and Isakov, Sergei V. and Khattar, Tanuj and Babbush, Ryan , date =. Optimization by decoded quantum interferometry , url =. Nature , number =. 2025 , bdsk-url-1 =. doi:10.1038/s41586-025-09527-5 , id =
-
[3]
IEEE Transactions on Information Theory , volume=
Information and quantum measurement , author=. IEEE Transactions on Information Theory , volume=. 1978 , publisher=
1978
-
[4]
Physics letters A , volume=
Optimum unambiguous discrimination between linearly independent symmetric states , author=. Physics letters A , volume=. 1998 , publisher=
1998
-
[5]
arXiv preprint arXiv:2310.20651 , year=
The quantum decoding problem , author=. arXiv preprint arXiv:2310.20651 , year=
-
[6]
Annual international conference on the theory and applications of cryptographic techniques , pages=
Quantum algorithms for variants of average-case lattice problems via filtering , author=. Annual international conference on the theory and applications of cryptographic techniques , pages=. 2022 , organization=
2022
-
[7]
No exponential quantum speedup for
Kothari, Robin and O'Donnell, Ryan and Wu, Kewen , journal=. No exponential quantum speedup for
-
[8]
On the Quantum Equivalence between
Chailloux, Andr. On the Quantum Equivalence between. Cryptology ePrint Archive , year=
-
[9]
On lattices, learning with errors, random linear codes, and cryptography
Regev, Oded , biburl =. On lattices, learning with errors, random linear codes, and cryptography. , url =. STOC , editor =
-
[10]
Journal of the ACM , volume=
Verifiable quantum advantage without structure , author=. Journal of the ACM , volume=. 2024 , publisher=
2024
-
[11]
arXiv preprint arXiv:2510.10967 , year=
Verifiable Quantum Advantage via Optimized DQI Circuits , author=. arXiv preprint arXiv:2510.10967 , year=
-
[12]
arXiv preprint arXiv:2510.07298 , year=
Fine-Grained Unambiguous Measurements , author=. arXiv preprint arXiv:2510.07298 , year=
-
[13]
2025 , day =
Shutty, Noah , title =. 2025 , day =
2025
-
[14]
New Journal of Physics , volume=
Belief propagation decoding of quantum channels by passing quantum messages , author=. New Journal of Physics , volume=. 2017 , publisher=
2017
-
[15]
arXiv preprint arXiv:2509.19441 , year=
Efficient and optimal quantum state discrimination via quantum belief propagation , author=. arXiv preprint arXiv:2509.19441 , year=
-
[16]
2020 IEEE International Symposium on Information Theory (ISIT) , pages=
Quantum advantage via qubit belief propagation , author=. 2020 IEEE International Symposium on Information Theory (ISIT) , pages=. 2020 , organization=
2020
-
[17]
arXiv preprint arXiv:2401.07167 , year=
Polar codes for cq channels: Decoding via belief-propagation with quantum messages , author=. arXiv preprint arXiv:2401.07167 , year=
-
[18]
Proceedings of the 56th Annual ACM Symposium on Theory of Computing , pages=
Quantum oblivious LWE sampling and insecurity of standard model lattice-based snarks , author=. Proceedings of the 56th Annual ACM Symposium on Theory of Computing , pages=
-
[19]
Annual International Cryptology Conference , pages=
LWE with quantum amplitudes: algorithm, hardness, and oblivious sampling , author=. Annual International Cryptology Conference , pages=. 2025 , organization=
2025
-
[20]
arXiv preprint arXiv:2509.24796 , year=
The Quantum Decoding Problem: Tight Achievability Bounds and Application to Regev's Reduction , author=. arXiv preprint arXiv:2509.24796 , year=
-
[21]
2022 IEEE Information Theory Workshop (ITW) , pages=
Belief propagation with quantum messages for symmetric classical-quantum channels , author=. 2022 IEEE Information Theory Workshop (ITW) , pages=. 2022 , organization=
2022
-
[22]
Quantum , volume=
Quantum message-passing algorithm for optimal and efficient decoding , author=. Quantum , volume=. 2022 , publisher=
2022
-
[23]
arXiv preprint arXiv:2510.06603 , year=
Algebraic Geometry Codes and Decoded Quantum Interferometry , author=. arXiv preprint arXiv:2510.06603 , year=
-
[24]
International Journal of Theoretical Physics , volume=
Optimum measurements for discrimination among symmetric quantum states and parameter estimation , author=. International Journal of Theoretical Physics , volume=. 1997 , publisher=
1997
-
[25]
Physical Review A , volume=
Quantum channels showing superadditivity in classical capacity , author=. Physical Review A , volume=. 1998 , publisher=
1998
-
[26]
IEEE Transactions on Information Theory , volume=
On quantum detection and the square-root measurement , author=. IEEE Transactions on Information Theory , volume=. 2002 , publisher=
2002
-
[27]
Mandal, Avijit and Pfister, Henry D , title =
-
[28]
2009 , publisher=
Fourier analysis on finite Abelian groups , author=. 2009 , publisher=
2009
-
[29]
Richardson and R
Thomas J. Richardson and R. The capacity of low-density parity-check codes under message-passing decoding , journal =
-
[30]
2023 , note=
Belief-Propagation with Quantum Messages for Polar Codes on Classical-Quantum Channels , author=. 2023 , note=
2023
-
[31]
8th Conference on the Theory of Quantum Computation, Communication and Cryptography , pages=
Towards Efficient Decoding of Classical-Quantum Polar Codes , author=. 8th Conference on the Theory of Quantum Computation, Communication and Cryptography , pages=
-
[32]
IEEE Transactions on Information Theory , volume=
Polar codes for private and quantum communication over arbitrary channels , author=. IEEE Transactions on Information Theory , volume=. 2014 , publisher=
2014
-
[33]
IEEE Transactions on Information Theory , volume=
Polar codes for arbitrary classical-quantum channels and arbitrary cq-macs , author=. IEEE Transactions on Information Theory , volume=
-
[34]
2009 , publisher=
Information, physics, and computation , author=. 2009 , publisher=
2009
-
[35]
Low density parity check codes over
Davey, Matthew C and MacKay, David JC , booktitle=. Low density parity check codes over. 1998 , organization=
1998
-
[36]
and MacKay, D
Davey, M.C. and MacKay, D. , journal=. Low-density parity check codes over. 1998 , volume=
1998
-
[37]
npj Quantum Information , volume=
Belief propagation with quantum messages for quantum-enhanced classical communications , author=. npj Quantum Information , volume=
-
[38]
IEEE Transactions on Information Theory , volume=
Duality of channels and codes , author=. IEEE Transactions on Information Theory , volume=. 2017 , publisher=
2017
-
[39]
arXiv preprint arXiv:1106.1445 , year=
From classical to quantum Shannon theory , author=. arXiv preprint arXiv:1106.1445 , year=
-
[40]
2002 , publisher=
Quantum computation and quantum information , author=. 2002 , publisher=
2002
-
[41]
Physical review letters , volume=
Conjectured strong complementary information tradeoff , author=. Physical review letters , volume=. 2009 , publisher=
2009
-
[42]
IEEE Transactions on Information Theory , volume=
Polar codes for classical-quantum channels , author=. IEEE Transactions on Information Theory , volume=. 2012 , publisher=
2012
-
[43]
IEEE Transactions on information Theory , volume=
Channel polarization: A method for constructing capacity-achieving codes for symmetric binary-input memoryless channels , author=. IEEE Transactions on information Theory , volume=. 2009 , publisher=
2009
-
[44]
Physical Review A , volume=
Quantum union bounds for sequential projective measurements , author=. Physical Review A , volume=. 2015 , publisher=
2015
-
[45]
Proceedings of the Royal Society A , volume=
Union bound for quantum information processing , author=. Proceedings of the Royal Society A , volume=. 2019 , publisher=
2019
-
[46]
Symposium on Simplicity in Algorithms (SOSA) , pages=
The quantum union bound made easy , author=. Symposium on Simplicity in Algorithms (SOSA) , pages=. 2022 , organization=
2022
-
[47]
IEEE Transactions on Information Theory , volume=
The capacity of the quantum channel with general signal states , author=. IEEE Transactions on Information Theory , volume=. 1998 , publisher=
1998
-
[48]
2012 IEEE International Symposium on Information Theory Proceedings , pages=
Polar coding to achieve the Holevo capacity of a pure-loss optical channel , author=. 2012 IEEE International Symposium on Information Theory Proceedings , pages=. 2012 , organization=
2012
-
[49]
2008 , publisher=
Modern coding theory , author=. 2008 , publisher=
2008
-
[50]
IEEE Transactions on Information Theory , volume=
Reliability function of general classical-quantum channel , author=. IEEE Transactions on Information Theory , volume=. 2000 , publisher=
2000
-
[51]
Physical Review A , volume=
Sending classical information via noisy quantum channels , author=. Physical Review A , volume=. 1997 , publisher=
1997
-
[52]
IEEE Transactions on Information Theory , volume=
Polar codes for degradable quantum channels , author=. IEEE Transactions on Information Theory , volume=. 2013 , publisher=
2013
-
[53]
Physical Review A , volume=
Optimal measurements for symmetric quantum states with applications to optical communication , author=. Physical Review A , volume=. 2015 , publisher=
2015
-
[54]
Physical Review A , volume=
Achieving minimum-error discrimination of an arbitrary set of laser-light pulses , author=. Physical Review A , volume=. 2013 , publisher=
2013
-
[55]
IRE Transactions on information theory , volume=
Low-density parity-check codes , author=. IRE Transactions on information theory , volume=. 1962 , publisher=
1962
-
[56]
1 , author=
Near Shannon limit error-correcting coding and decoding: Turbo-codes. 1 , author=. Proceedings of ICC'93-IEEE International Conference on Communications , volume=. 1993 , organization=
1993
-
[57]
IEEE transactions on Information Theory , volume=
Good error-correcting codes based on very sparse matrices , author=. IEEE transactions on Information Theory , volume=. 2002 , publisher=
2002
-
[58]
belief propagation
Turbo decoding as an instance of Pearl's" belief propagation" algorithm , author=. IEEE Journal on selected areas in communications , volume=. 1998 , publisher=
1998
-
[59]
Reverend
Pearl, Judea , year=. Reverend
-
[60]
1998 , publisher=
Iterative decoding of compound codes by probability propagation in graphical models , author=. 1998 , publisher=
1998
-
[61]
arXiv preprint arXiv:2109.08170 , year=
Quantum message-passing algorithm for optimal and efficient decoding , author=. arXiv preprint arXiv:2109.08170 , year=
-
[62]
Journal of Modern Optics , volume=
A ‘pretty good’measurement for distinguishing quantum states , author=. Journal of Modern Optics , volume=. 1994 , publisher=
1994
-
[63]
Teoriya Veroyatnostei i ee Primeneniya , volume=
On asymptotically optimal hypotheses testing in quantum statistics , author=. Teoriya Veroyatnostei i ee Primeneniya , volume=. 1978 , publisher=
1978
-
[64]
IEEE Transactions on Information Theory , volume=
Optimal tight frames and quantum measurement , author=. IEEE Transactions on Information Theory , volume=. 2002 , publisher=
2002
-
[65]
IEEE Transactions on Information Theory , volume=
Geometrically uniform frames , author=. IEEE Transactions on Information Theory , volume=. 2003 , publisher=
2003
-
[66]
2010 IEEE International Symposium on Information Theory , pages=
An entropy inequality for q-ary random variables and its application to channel polarization , author=. 2010 IEEE International Symposium on Information Theory , pages=. 2010 , organization=
2010
-
[67]
2023 IEEE International Symposium on Information Theory (ISIT) , pages=
Belief-propagation with quantum messages for polar codes on classical-quantum channels , author=. 2023 IEEE International Symposium on Information Theory (ISIT) , pages=. 2023 , organization=
2023
-
[68]
2026 , note=
Belief Propagation with Quantum Messages for Q-ary Symmetric Pure-State Channels , author=. 2026 , note=
2026
-
[69]
Nature , volume=
Optimization by decoded quantum interferometry , author=. Nature , volume=. 2025 , publisher=
2025
-
[70]
2006 , journal=
Performance analysis of linear codes under maximum-likelihood decoding: A tutorial , author=. 2006 , journal=
2006
-
[71]
2026 , url=
Lecture Notes on Factor Graphs and Machine Learning , author=. 2026 , url=
2026
-
[72]
IEEE Transactions on Information Theory , volume=
Codes on graphs: Normal realizations , author=. IEEE Transactions on Information Theory , volume=. 2002 , publisher=
2002
-
[73]
IEEE Transactions on Information Theory , volume=
Codes on graphs: Fundamentals , author=. IEEE Transactions on Information Theory , volume=. 2014 , publisher=
2014
-
[74]
IEEE Transactions on Information Theory , volume=
On the BCJR trellis for linear block codes , author=. IEEE Transactions on Information Theory , volume=. 2002 , publisher=
2002
-
[75]
IEEE Transactions on information theory , volume=
Optimal decoding of linear codes for minimizing symbol error rate (corresp.) , author=. IEEE Transactions on information theory , volume=. 2003 , publisher=
2003
-
[76]
arXiv preprint arXiv:2601.21330 , year=
Belief Propagation with Quantum Messages for Symmetric Q-ary Pure-State Channels , author=. arXiv preprint arXiv:2601.21330 , year=
-
[77]
2025 IEEE International Symposium on Information Theory (ISIT) , pages=
Reed--Muller Codes on CQ Channels via a New Correlation Bound for Quantum Observables , author=. 2025 IEEE International Symposium on Information Theory (ISIT) , pages=. 2025 , organization=
2025
-
[78]
Physics Letters A , volume=
How to differentiate between non-orthogonal states , author=. Physics Letters A , volume=. 1988 , publisher=
1988
-
[79]
Physics Letters A , volume=
How to differentiate between non-orthogonal states , author=. Physics Letters A , volume=. 1987 , publisher=
1987
-
[80]
Physics Letters A , volume=
Overlap and distinguishability of quantum states , author=. Physics Letters A , volume=. 1988 , publisher=
1988
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.