pith. sign in

arxiv: 2606.04843 · v1 · pith:JXETN3EJnew · submitted 2026-06-03 · 🪐 quant-ph

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

Alexandre Krajenbrink , Colin Krawchuk , Ansis Rosmanis , Matthias Rosenkranz This is my paper

Pith reviewed 2026-06-28 06:00 UTC · model grok-4.3

classification 🪐 quant-ph
keywords Decoded Quantum Interferometrytranslation association schemesrank-metric optimizationGabidulin codesfinite geometriesquantum Fourier transformlow-rank decoding
0
0 comments X

The pith

Decoded Quantum Interferometry extends to translation association schemes by reducing state biasing to a finite tridiagonal eigenvalue problem.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper establishes that the core DQI mechanism, which uses coherent decoding and quantum Fourier transform for structured optimization, can be lifted from Hamming space to finite geometries with translation symmetry. In these translation association schemes, points group into distance shells from a basepoint, so the quantum state is tracked by one amplitude per shell and preparation of a biased state reduces to solving a tridiagonal eigenvalue problem. As a concrete case the authors construct an efficient protocol for finding an m by n matrix over a finite field whose rank differs least from a given target matrix. Uniform superpositions over fixed-rank matrices serve as initial states, Gabidulin codes supply low-rank decoding candidates up to cutoff l, and the resulting solutions carry an effective-rank proxy near min(m,n)-l together with a constant-probability bound on residual rank. The construction identifies the geometric and coding ingredients required for DQI outside Hamming space without claiming an additive optimality guarantee for the rank-metric task.

Core claim

In translation association schemes the DQI state is described by one amplitude per distance shell from a basepoint; biasing toward high-quality solutions therefore becomes the ground state of a finite tridiagonal matrix whose entries are determined by the scheme parameters. For the rank-metric objective the protocol prepares a uniform superposition over fixed-rank matrices and applies Gabidulin-code decoding up to cutoff l, yielding outputs whose effective-rank proxy lies near min(m,n)-l and whose expected score implies a constant-probability upper bound on the residual rank of a single sample.

What carries the argument

Translation association schemes, geometries in which points are partitioned into shells by distance from a fixed basepoint, so that the quantum state is fully described by one complex amplitude per shell.

If this is right

  • Solutions are obtained with effective-rank proxy near min(m,n)-l.
  • The expected score converts into a constant-probability bound on residual rank of a sampled matrix.
  • For Gabidulin nearest-codeword instances the covering-radius obstruction blocks any additive optimality guarantee.
  • The protocol supplies the geometric and coding ingredients needed to run DQI on objectives defined by translation association schemes.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The same shell-amplitude reduction may let DQI address other optimization problems whose feasible sets carry translation symmetry.
  • Because the tridiagonal matrix is small when the number of shells is modest, the biasing step remains classically tractable even for moderately large geometries.
  • The rank-metric example suggests that other association schemes with efficient decoders could be turned into DQI instances for combinatorial search tasks.

Load-bearing premise

Gabidulin codes supply efficient low-rank decoding up to cutoff l and the covering-radius obstruction does not invalidate the protocol's utility for identifying the required geometric and coding ingredients.

What would settle it

A concrete numerical check showing that the ground state of the tridiagonal eigenvalue problem for a given translation association scheme fails to produce any matrix whose rank difference to the target is smaller than the classical greedy minimum.

Figures

Figures reproduced from arXiv: 2606.04843 by Alexandre Krajenbrink, Ansis Rosmanis, Colin Krawchuk, Matthias Rosenkranz.

Figure 1
Figure 1. Figure 1: Shells around a basepoint 0 and the radial and shell directions. The state 𝐴𝑖 |0⟩ is supported on the shell Γ𝑖 , while 𝐴1 induces a ‘radial walk’ between a shell and its two neighbouring shells. Equation (11) shows that the adjacency matrix 𝐴1 induces a walk that mixes points on neighbouring shells [PITH_FULL_IMAGE:figures/full_fig_p005_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: Plot of the rescaled 𝑞-Krawtchouk polynomial √ |Γ𝑡 |/|Γ𝑟 |𝜆𝑟(𝑡)𝑞 −𝑚𝑛/2 as a function of 𝑡 ∈ [0, 𝐷] for all 𝑟 ∈ [0, 𝐷]. The evaluation of the function has been extrapolated from the integer points to continuous points by using the connection between the 𝑞-Krawtchouk polynomial and the 𝑞-deformed hypergeometric function 𝜆𝑟(𝑡) = (−1)𝑟 𝑞 ( 𝑟 2) ( 𝐷 𝑟 )𝑞 2𝜙1( 𝑞 −𝑟 , 𝑞 𝑡−𝐷 𝑞 −𝐷 ; 𝑞, 𝑞 𝑀−𝑡+1) with 𝐷 = min(𝑚, 𝑛) a… view at source ↗
Figure 3
Figure 3. Figure 3: Schematic state-preparation circuits used in Lemma [PITH_FULL_IMAGE:figures/full_fig_p037_3.png] view at source ↗
read the original abstract

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.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

0 major / 2 minor

Summary. The paper extends Decoded Quantum Interferometry (DQI) from Hamming space to translation association schemes with translation symmetry, where the state biasing step reduces to a finite tridiagonal eigenvalue problem. For the rank-metric problem of finding an m×n matrix over a finite field with minimal rank difference to a target, it constructs initial states as uniform superpositions over fixed-rank matrices, invokes Gabidulin codes for efficient low-rank decoding up to cutoff l, obtains solutions whose effective-rank proxy is near min(m,n)−l, and converts the expected score into a constant-probability bound on residual rank; the manuscript explicitly notes that a covering-radius obstruction blocks any additive optimality guarantee and makes no claim of quantum advantage.

Significance. If the eigenvalue reduction and probability conversion hold, the work supplies a systematic route for applying DQI to geometries beyond Hamming space by exploiting shell structure and translation symmetry, while furnishing a concrete rank-metric example together with the requisite coding ingredients (Gabidulin codes). The explicit acknowledgment of the covering-radius limitation keeps the contribution focused on identifying the necessary geometric and algebraic components rather than overstating performance.

minor comments (2)
  1. The abstract refers to 'the corresponding expected score can be converted into a constant-probability bound' without indicating the section or lemma that performs the conversion; adding an explicit pointer (e.g., §4.3, Lemma 12) would improve traceability.
  2. Notation for the tridiagonal matrix arising from the association scheme (eigenvalues, off-diagonal entries) is introduced only in the abstract; a short table or equation block early in §3 would clarify the finite-dimensional reduction for readers unfamiliar with association-scheme theory.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the careful reading, accurate summary of the manuscript, and the positive assessment. The recommendation for minor revision is noted; we will incorporate appropriate changes in the revised version.

Circularity Check

0 steps flagged

No significant circularity; derivation self-contained

full rationale

The manuscript derives the extension of DQI to translation association schemes by tracking amplitudes per shell and reducing the biasing step to a finite tridiagonal eigenvalue problem that follows directly from the translation symmetry and distance partitioning of the scheme. Gabidulin codes are invoked solely as an external efficient classical decoder up to cutoff l, with no fitted parameters renamed as predictions and no self-citation chain required to justify the core reduction or the effective-rank proxy. The paper explicitly notes the covering-radius obstruction and refrains from optimality claims, keeping all steps independent of the target results. No quoted equation or premise reduces by construction to its own inputs.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The paper relies on existing mathematical structures rather than new postulates; no free parameters or invented entities are introduced in the abstract.

axioms (2)
  • domain assumption Translation association schemes permit reduction of the state to one amplitude per shell
    Invoked to turn the biasing step into a tridiagonal eigenvalue problem.
  • domain assumption Gabidulin codes admit efficient low-rank decoding up to cutoff l
    Used as the decoding primitive in the rank-metric example.

pith-pipeline@v0.9.1-grok · 5809 in / 1437 out tokens · 45131 ms · 2026-06-28T06:00:03.939581+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score.

  1. Approximability limits for bounded-degree max-LINSAT and implications for decoded quantum interferometry

    quant-ph 2026-06 unverdicted novelty 6.0

    Extends NP-hardness of exceeding r/q + O(1/sqrt(D)) for bounded-degree max-Ek-LINSAT(q,r) over F_q and shows quantum decoding is required for DQI to achieve the hardness-optimal 1/sqrt(D) scaling.

Reference graph

Works this paper leans on

47 extracted references · 11 linked inside Pith · cited by 1 Pith paper

  1. [1]

    S. P. Jordan, N. Shutty, M. Wootters, A. Zalcman, A. Schmidhuber, R. King, S. V. Isakov, T. Khattar, and R. Babbush, Nature646, 831 (2025)

    2025

  2. [2]

    Khattar, N

    T. Khattar, N. Shutty, C. Gidney, A. Zalcman, N. Yosri, D. Maslov, R. Babbush, and S. P. Jordan, Verifiable Quantum Advantage via Optimized DQI Circuits (2025), arXiv:2510.10967 [quant-ph]

    arXiv 2025

  3. [3]

    Regev, inProceedings of the Thirty-Seventh Annual ACM Symposium on Theory of Computing, STOC ’05 (Association for Computing Machinery, 2005) p

    O. Regev, inProceedings of the Thirty-Seventh Annual ACM Symposium on Theory of Computing, STOC ’05 (Association for Computing Machinery, 2005) p. 84–93

    2005

  4. [4]

    Regev, J

    O. Regev, J. ACM56, 34:1 (2009), arXiv:2401.03703

    arXiv 2009

  5. [5]

    Debris-Alazard, M

    T. Debris-Alazard, M. Remaud, and J.-P. Tillich, IEEE Trans. Inf. Theor.70, 5323 (2024)

    2024

  6. [6]

    Blanvillain, A

    A. Blanvillain, A. Chailloux, and J.-P. Tillich, The Quantum Decoding Problem : Tight Achievability Bounds and Application to Regev’s Reduction (2025), arXiv:2509.24796

    arXiv 2025

  7. [7]

    Roth, IEEE Transactions on Information Theory37, 328 (1991)

    R. Roth, IEEE Transactions on Information Theory37, 328 (1991)

    1991

  8. [8]

    Koetter and F

    R. Koetter and F. R. Kschischang, IEEE Transactions on Information Theory54, 3579 (2008)

    2008

  9. [9]

    Bartz, L

    H. Bartz, L. Holzbaur, H. Liu, S. Puchinger, J. Renner, and A. Wachter-Zeh, Rank-Metric Codes and Their Applications (2022), arXiv:2203.12384 [cs.IT]

    arXiv 2022

  10. [10]

    E. M. Gabidulin, Problems of Information Transmission21, 1 (1985)

    1985

  11. [11]

    Y. Chen, Q. Liu, and M. Zhandry, inAdvances in Cryptology – EUROCRYPT 2022, edited by O. Dunkel- man and S. Dziembowski (Springer International Publishing, Cham, 2022) pp. 372–401

    2022

  12. [12]

    Yamakawa and M

    T. Yamakawa and M. Zhandry, J. ACM71, 20:1 (2024), arXiv:2204.02063

    arXiv 2024

  13. [13]

    Chailloux and J.-P

    A. Chailloux and J.-P. Tillich, in19th Conference on the Theory of Quantum Computation, Commu- nication and Cryptography (TQC 2024), Leibniz International Proceedings in Informatics (LIPIcs), Vol. 310, edited by F. Magniez and A. B. Grilo (Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Dagstuhl, Germany, 2024) pp. 6:1–6:14

    2024

  14. [14]

    Rosmanis, A nearly linear-time Decoded Quantum Interferometry algorithm for the Optimal Polynomial Intersection problem (2026), arXiv:2601.15171 [quant-ph]

    A. Rosmanis, A nearly linear-time Decoded Quantum Interferometry algorithm for the Optimal Polynomial Intersection problem (2026), arXiv:2601.15171 [quant-ph]

    arXiv 2026

  15. [15]

    Piveteau and J

    C. Piveteau and J. M. Renes, Efficient and optimal quantum state discrimination via quantum belief propagation (2025), arXiv:2509.19441 [quant-ph]

    arXiv 2025

  16. [16]

    Gu and S

    A. Gu and S. P. Jordan, Algebraic geometry codes and decoded quantum interferometry (2025), arXiv:2510.06603 [quant-ph]

    arXiv 2025

  17. [17]

    K. Bu, W. Gu, and X. Li, Multivariate Decoded Quantum Interferometry for Weighted Optimization (2026), arXiv:2605.10666

    Pith/arXiv arXiv 2026

  18. [18]

    Chailloux and J.-P

    A. Chailloux and J.-P. Tillich, inProceedings of the 57th Annual ACM Symposium on Theory of Computing, STOC ’25 (Association for Computing Machinery, New York, NY, USA, 2025) p. 738–749

    2025

  19. [19]

    Chailloux, OPI x Soft Decoders (2025), arXiv:2511.22691

    A. Chailloux, OPI x Soft Decoders (2025), arXiv:2511.22691 . 21

    arXiv 2025

  20. [20]

    Shutty, A

    N. Shutty, A. Mandal, S. Ragavan, Q. Buzet, A. Chailloux, N. C. Rubin, A. Khan, S. Boulebnane, R. Shaydulin, J. Azariah, and S. P. Jordan, Optimization Using Locally-Quantum Decoders (2026), arXiv:2604.24633

    Pith/arXiv arXiv 2026

  21. [21]

    Schmidhuber, J

    A. Schmidhuber, J. Z. Lu, N. Shutty, S. Jordan, A. Poremba, and Y. Quek, Hamiltonian Decoded Quantum Interferometry (2025), arXiv:2510.07913 [quant-ph]

    arXiv 2025

  22. [22]

    K. Bu, W. Gu, and X. Li, Hamiltonian Decoded Quantum Interferometry for General Pauli Hamil- tonians (2026), arXiv:2601.18773 [quant-ph]

    arXiv 2026

  23. [23]

    Wocjan, A Factorization Identity for Twisted Multinomial Coefficients with Application to Pilot States in Hamiltonian Decoded Quantum Interferometry (2026), arXiv:2604.01022

    P. Wocjan, A Factorization Identity for Twisted Multinomial Coefficients with Application to Pilot States in Hamiltonian Decoded Quantum Interferometry (2026), arXiv:2604.01022

    Pith/arXiv arXiv 2026

  24. [24]

    E. R. Anschuetz, D. Gamarnik, and J. Z. Lu, Decoded Quantum Interferometry Requires Structure (2025), arXiv:2509.14509 [quant-ph]

    arXiv 2025

  25. [25]

    Parekh, No Quantum Advantage in Decoded Quantum Interferometry for MaxCut (2025), arXiv:2509.19966 [quant-ph]

    O. Parekh, No Quantum Advantage in Decoded Quantum Interferometry for MaxCut (2025), arXiv:2509.19966 [quant-ph]

    arXiv 2025

  26. [26]

    M. J. Kramer, C. Schubert, and J. Eisert, Tight Inapproximability of Max-LINSAT and Implications for Decoded Quantum Interferometry (2026), arXiv:2603.04540

    arXiv 2026

  27. [27]

    Sun and M

    Y. Sun and M. Wootters, On Worst-Case Optimal Polynomial Intersection (2026), arXiv:2604.09533

    Pith/arXiv arXiv 2026

  28. [28]

    Patamawisut, N

    N. Patamawisut, N. Benchasattabuse, M. Hajdušek, and R. Van Meter, in2025 IEEE International Conference on Quantum Computing and Engineering (QCE)(2025) pp. 291–301, arXiv:2504.18334

    arXiv 2025

  29. [29]

    K. Bu, W. Gu, D. E. Koh, and X. Li, Quantum Science and Technology11, 025010 (2026)

    2026

  30. [30]

    Wang, Kernelized Decoded Quantum Interferometry (2025), arXiv:2511.20016 [quant-ph]

    F. Wang, Kernelized Decoded Quantum Interferometry (2025), arXiv:2511.20016 [quant-ph]

    arXiv 2025

  31. [31]

    Sabater, O

    F. Sabater, O. E. Harzli, G.-J. Besjes, M. Erdmann, J. Klepsch, J. Hiltrop, J.-F. Bobier, Y. Cao, and C. A. Riofrio, Towards solving industrial integer linear programs with Decoded Quantum Interferometry (2025), arXiv:2509.08328 [quant-ph]

    Pith/arXiv arXiv 2025

  32. [32]

    Bollmann and M

    L. Bollmann and M. Hess, Benchmarking Techniques for Decoded Quantum Interferometry (2026), arXiv:2603.24441 [quant-ph]

    arXiv 2026

  33. [33]

    Marwaha, B

    K. Marwaha, B. Fefferman, A. Gheorghiu, and V. Havlicek, On the Complexity of Decoded Quantum Interferometry (2025), arXiv:2509.14443

    Pith/arXiv arXiv 2025

  34. [34]

    Koekoek, P

    R. Koekoek, P. A. Lesky, and R. F. Swarttouw,Hypergeometric Orthogonal Polynomials and Their Q-Analogues, Springer Monographs in Mathematics (Springer, Berlin, Heidelberg, 2010)

    2010

  35. [35]

    Richter and S

    G. Richter and S. Plass, inITG-Fachbericht(2004) pp. 203–210

    2004

  36. [36]

    Gorla, U

    E. Gorla, U. Martínez-Peñas, and F. Salizzoni, Sum-rank metric codes (2023), arXiv:2304.12095 [cs.IT]

    arXiv 2023

  37. [37]

    Martínez-Peñas, Journal of Algebra504, 587 (2018)

    U. Martínez-Peñas, Journal of Algebra504, 587 (2018)

    2018

  38. [38]

    Camps-Moreno, E

    E. Camps-Moreno, E. Gorla, C. Landolina, E. L. García, U. Martínez-Peñas, and F. Salizzoni, IEEE Transactions on Information Theory68, 3806 (2022)

    2022

  39. [39]

    Delsarte, Journal of Combinatorial Theory, Series A25, 226 (1978)

    P. Delsarte, Journal of Combinatorial Theory, Series A25, 226 (1978). 22

    1978

  40. [40]

    (17.9.2), F

    NIST Digital Library of Mathematical Functions, Chapter 17:𝑞-hypergeometric and related func- tions, https://dlmf.nist.gov/17.9.E2 (2026), version 1.2.6; Section 17.9, Eq. (17.9.2), F. H. Jack- son’s transformations

    2026

  41. [41]

    Byrne and A

    E. Byrne and A. Ravagnani, SIAM Journal on Discrete Mathematics31, 927 (2017)

    2017

  42. [42]

    Zhandry, Journal of Cryptology34, 6 (2021), arXiv:1711.02276

    M. Zhandry, Journal of Cryptology34, 6 (2021), arXiv:1711.02276

    Pith/arXiv arXiv 2021

  43. [43]

    Silberstein and T

    N. Silberstein and T. Etzion, IEEE Transactions on Information Theory57, 365 (2011), arXiv:0911.3256

    Pith/arXiv arXiv 2011

  44. [44]

    Grover and T

    L. Grover and T. Rudolph, Creating superpositions that correspond to efficiently integrable proba- bility distributions (2002), arXiv:quant-ph/0208112

    Pith/arXiv arXiv 2002

  45. [45]

    C. H. Bennett, SIAM Journal on Computing18, 766 (1989)

    1989

  46. [46]

    Beauregard, G

    S. Beauregard, G. Brassard, and J. M. Fernandez, Quantum arithmetic on galois fields (2003), arXiv:quant-ph/0301163

    Pith/arXiv arXiv 2003

  47. [47]

    Amento, M

    B. Amento, M. Roetteler, and R. Steinwandt, Quantum Information & Computation13, 116 (2013), arXiv:1209.5491 . 23 A Rank-metric𝑞-Krawtchouk polynomials We provide in this section additional details on the radial Fourier eigenvalues 𝜆𝑟(⋅)in the rank- metric scheme. These are the 𝑞-Krawtchouk polynomials. First, recall that Lemma 8 gives the first 𝑞-Krawtch...

    Pith/arXiv arXiv 2013