Pith. sign in

REVIEW 2 major objections 5 minor 46 references

Classical MCMC matches DQI optimization scores, with OPI runtime scaling like 1.1 to the power of qubit number.

Reviewed by Pith at T0; open to challenge. T0 means a machine referee read the full paper against a public rubric. the ladder, T0–T4 →

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

T0 review · grok-4.5

2026-07-31 17:16 UTC pith:LHM4HFY7

load-bearing objection Solid theory-plus-empirics paper: binomial-moment take on DQI plus MCMC baselines that hit DQI scores, with OPI cost ~1.1^{n_p} up to ~150 qubits—nuances the advantage claim without refuting it. the 2 major comments →

arxiv 2607.28120 v1 pith:LHM4HFY7 submitted 2026-07-30 quant-ph

Approximate sampling from decoded quantum interferometry via Markov chain Monte Carlo methods

Elies Gil-Fuster , Matan Ninio , Lennart Bittel , Yishai Shimoni , Jens Eisert , Stefan Woerner , Almudena Carrera V\'azquez This is my paper
classification quant-ph
keywords decoded quantum interferometryMarkov chain Monte Carloblock-Gibbs samplingmax-XORSAToptimal polynomial intersectionapproximation ratioquantum optimizationsampling complexity
verification ladder T0 review T1 audit T2 compute T3 formal T4 reserved

The pith

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

Decoded quantum interferometry (DQI) is a quantum method that turns approximate optimization into a sampling task linked to classical decoding, with a claimed super-polynomial edge on optimal polynomial intersection (OPI). This paper asks whether ordinary classical samplers can reach the same approximation ratios. Using the fact that DQI output probabilities are classically computable, the authors run block-Gibbs MCMC on the induced distribution. On sparse max-XORSAT they reach beyond 1000 qubits with polynomial mixing; on OPI they reach beyond 150 effective qubits and find empirical runtime growing roughly as 1.1 to the power of the qubit count. Analytically they show that DQI’s moments reduce to binomial statistics whenever the dual code has high distance, and they spell out obstacles to proving sampling hardness or reducing search to decision. The work does not overturn the asymptotic claims, but it shows that classical sampling already tracks DQI’s optimization performance with a small exponential base, so any practical quantum edge may appear only at very large sizes.

Core claim

Block-Gibbs MCMC can reliably attain the approximation ratios that DQI is guaranteed to achieve: polynomial scaling on max-XORSAT beyond 1000 qubits, and exponential scaling approximately 1.1^{n_p} on OPI beyond 150 effective qubits in the regime where a super-polynomial quantum advantage has been claimed. Matching the score threshold, not full distributional closeness, is treated as the relevant success criterion for optimization performance.

What carries the argument

Block-Gibbs sampling (block size κ=3) from the DQI distribution P(x)=P(f(x))², whose unnormalized values are efficiently computable; the chain is stopped when the score first exceeds the DQI threshold ⟨s⟩_DQI, yielding mixing and sampling times whose scaling is measured directly.

Load-bearing premise

That the observed OPI base near 1.1, and the exponential-versus-power-law transition around score 0.66, continue to hold at sizes far beyond the largest instances studied (about 156 effective qubits).

What would settle it

Run the same block-Gibbs protocol on substantially larger OPI instances (or with tighter score thresholds) and check whether the fitted base stays near 1.1 or jumps, and whether a power-law fit ever becomes competitive again at the full DQI threshold.

Watch this falsifier — get emailed when new claim-graph text bears on it.

If this is right

  • Classical MCMC already matches DQI’s guaranteed approximation ratios on the two flagship problem families at the sizes tested.
  • Any practical quantum advantage for DQI on OPI is pushed to instance sizes where a 1.1^{n} classical cost becomes prohibitive.
  • Studying DQI advantage requires the search or sampling versions of max-LINSAT; the decision version is classically easy once dual-code distance is high.
  • Keep-going versus restart sampling performance differs between max-XORSAT and OPI, consistent with different clustering of high-score solutions.
  • Lowering the OPI score target below roughly 0.66 changes the empirical scaling from exponential back toward polynomial.

Where Pith is reading between the lines

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

  • Warm-starting MCMC from a single DQI sample could exploit regimes where mixing time greatly exceeds intra-sample time, turning a hybrid loop into a practical classical booster.
  • If better classical heuristics (Prange, annealing) were scaled the same way, the residual gap to DQI might shrink further or vanish at moderate sizes.
  • The binomial-moment characterization suggests that low-body marginals of the DQI distribution may be classically samplable yet still unhelpful for search, offering a clean negative test.
  • Extending the same MCMC protocol to Hamiltonian DQI or soft-decoder variants would test whether sharper landscapes inflate the exponential base.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit.

Referee Report

2 major / 5 minor

Summary. The paper studies decoded quantum interferometry (DQI) both analytically and empirically. Analytically, it gives a simplified moment characterization: for dual-code distance d and DQI polynomial degree ℓ with 2ℓ+1≤d, low-order moments of the objective under the uniform and DQI distributions reduce to moments of a binomial (Theorems 2–3, Appendix B), and it spells out obstacles to standard hardness arguments for sampling and to a search-to-decision reduction (Appendix D). Empirically, it uses block-Gibbs MCMC (κ=3) with efficiently computable DQI probabilities to hit DQI’s expected approximation ratios on sparse max-XORSAT (beyond ~1000 qubits, mixing ~n^5) and on OPI (beyond ~150 effective qubits), where MCMC step counts scale roughly as 1.1^{n_p} in the regime of claimed super-polynomial DQI advantage. The authors carefully do not refute existing advantage claims; they argue for a more nuanced practical reading given the small exponential base.

Significance. If the results hold as stated, the work is a useful contribution to the quantum-optimization literature: it separates decision/search/sampling for DQI, supplies a cleaner monomial/binomial route to performance moments than the original symmetric-polynomial analysis, and provides the first large-scale classical sampling benchmarks against DQI score thresholds (max-XORSAT >1000 qubits; OPI to n_p=156). Strengths include explicit fits and goodness-of-fit (Table E.1, R²_×≈0.94–0.98), a public repository, and scoped claims that match score thresholds rather than full TV simulation of P_DQI. The OPI ~1.1^{n_p} observation is the main practical takeaway and is worth publishing even without asymptotic classical poly-time.

major comments (2)
  1. [Section V.C–D, Fig. 3d, Table E.1, Appendix C] §V.C–D and Fig. 3d / Table E.1: the central practical claim is the OPI MCMC step-count base ≈1.096–1.104 up to n_p=156 (first point dropped as outlier; sampling averages use K=10). That base is load-bearing for the “nuanced practical advantage” conclusion. Please report uncertainty on the fitted base (e.g., leave-one-out or bootstrap CIs), state explicitly the n_p range over which the fit is claimed, and add a short comparison of total classical work (steps × per-step cost O(p^κ m n) from App. C, κ=3) against a rough DQI circuit-cost scaling, so readers can judge when 1.1^{n_p} would still be competitive in practice.
  2. [Title, Abstract, Section III.B] §III.B and title: success is defined as matching ⟨s⟩_DQI (first-passage / N=10 good samples), not approximate sampling in total variation from P_DQI. That choice is defensible for optimization and is discussed, but the title and abstract lead with “approximate sampling from DQI.” Please tighten the abstract/intro wording so the primary figure of merit (optimization score at the DQI threshold) is unambiguous, and reserve “approximate sampling” for the MCMC method rather than the claim being tested against quantum advantage.
minor comments (5)
  1. [Section V.C, Fig. 5] Fig. 5 phase transition near threshold ~0.66 is interesting but R²_× is low on both sides of the transition; state more clearly that this is exploratory and not used to claim a sharp complexity threshold.
  2. [Section II.B, Table II, Section V.A] Eq. (3)–(4) and Table II: briefly remind the reader that ⟨s⟩_DQI/m for OPI is worst-case over F while max-XORSAT is average-case over v, so τ_max vs τ_avg are not interchangeable metrics.
  3. [Appendix B] Appendix B proofs are long but valuable; a one-paragraph roadmap at the start of App. B (what is new vs Ref. [6]) would help non-specialists.
  4. [Section V heading; Section V.C] Typographical: “V . NUMERICAL RESULTS” has a stray space; “keep-going” / “keep going” hyphenation is inconsistent in §V.C; arXiv IDs in the bibliography are fine but ensure journal style on acceptance.
  5. [Section V, Ref. [37]] Cite or point more explicitly to the public repo [37] in the main numerical section (not only Conclusions) for reproducibility of ℓ_DQI, ε estimates, and MCMC seeds.

Circularity Check

0 steps flagged

No significant circularity: DQI thresholds are external inputs; MCMC runtimes and binomial-moment theorems are independent of those thresholds by construction.

full rationale

The paper’s load-bearing claims split cleanly into (i) analytical moment identities and (ii) empirical MCMC first-passage/sampling times. Theorems 2–3 and Lemma 1 derive E[f^k] under Unif and PDQI from the dual-code distance and multinomial/Fourier combinatorics equating low moments to a Binom(m,r/p) random variable; the target score formulas (Eqs. 3–4) are not inputs to those proofs, nor are the numerical bases 1.1^{n_p} or n^5. Numerically, ⟨s⟩DQI (and ℓ_DQI for max-XORSAT via estimated ε in Eq. 4) are taken from the external DQI performance guarantees of Ref. [6] and used only as fixed stopping thresholds; block-Gibbs (κ=3) then measures independent mixing/sampling step counts against those thresholds. Fitting τ ~ 1.1^{n_p} or ~n^5 to those measured times is ordinary post-hoc scaling description, not a prediction forced by a parameter fitted to the same quantity. Appendix A reuses the standard optimal-polynomial construction of [6]; that is ordinary prior-art reuse, not a self-citation uniqueness chain. No step reduces a claimed derivation to its own fitted input or definition. Score 0 is appropriate.

Axiom & Free-Parameter Ledger

5 free parameters · 5 axioms · 0 invented entities

The paper rests on standard coding/MCMC math plus the DQI framework and performance formulas from Jordan et al., plus empirical modeling choices (block size, thresholds, fit forms). No new physical entities. Free parameters are fit coefficients for runtime scaling and the numerically chosen ℓ_DQI / ε for LDPC instances.

free parameters (5)
  • OPI MCMC exponential base (~1.096–1.104) = ≈1.1 (e.g. 1.096 for τ_max, 1.104 for restart τ_10)
    Fitted from mixing/sampling times vs n_p (Figs. 3d, 4d; Table E.1); load-bearing for the ‘small-base exponential’ practical message.
  • max-XORSAT power-law degree (~4–5) = τ_avg ~ n^4.90; sampling ~ n^4.0–4.5
    Fitted mixing/sampling times vs n; supports polynomial classical tractability claim for that family.
  • block size κ = 3
    Hand-chosen tradeoff for block-Gibbs; fixed to 3 in all experiments (Sec. III A).
  • ℓ_DQI and ε(ℓ) for sparse max-XORSAT = ℓ/m just below ~0.13; ⟨s⟩_DQI/m → ~0.831
    Numerically estimated BP failure rates and argmax of Eq. (4) per size (Fig. 2); set the score target MCMC must hit.
  • N good samples and K random instances = N=10; K=100 (max-XORSAT, OPI search), K=10 (OPI sampling)
    Stopping and averaging hyperparameters for sampling/search metrics.
axioms (5)
  • domain assumption DQI expected fraction of satisfied constraints is given by Eqs. (3)–(4) in the large-m,ℓ limit when a decoder corrects ℓ errors (deterministically or with failure ε).
    Imported from Jordan et al. [6]; used as the external performance target for MCMC throughout Sec. V.
  • standard math For dual-code distance d, the first d moments of f under the uniform distribution equal those of (2J−m) for J~Binom(m,r/p).
    Theorem 2 / App. B; Fourier and distance arguments; standard coding theory plus multinomial expansions.
  • standard math Block-Gibbs with the DQI unnormalized weights P²(f(x)) is irreducible/aperiodic on F_p^n and converges to PDQI.
    Invoked via standard MCMC references [29–31] in Sec. III A; not re-proved for these landscapes.
  • domain assumption Sparse max-XORSAT duals are LDPC-like with BP approximately decoding below a weight threshold; OPI duals are Reed-Solomon with Berlekamp–Massey up to ⌊n/2⌋.
    Table II and Sec. II; standard coding facts plus numerical ε for LDPC.
  • ad hoc to paper Matching DQI’s expected score is a sufficient figure of merit for assessing practical optimization advantage (vs full distributional simulation).
    Explicit methodological choice in Sec. III B; drives all numerical success criteria.

pith-pipeline@v1.2.0-daily-grok45 · 34981 in / 3606 out tokens · 74615 ms · 2026-07-31T17:16:53.382985+00:00 · methodology

0 comments
read the original abstract

Optimization problems are among the leading candidates for industrially relevant quantum advantage. Decoded quantum interferometry (DQI) has been proposed to tackle approximate optimization, establishing a connection to classical decoding problems. While previous work has primarily focused on the theoretical complexity of DQI, comparatively little is known about its empirical performance relative to classical algorithms. In this work, we shed further light on the complexity of DQI and investigate numerically whether classical sampling methods can emulate the optimization capabilities of DQI. We first present a simplified analytical characterization of DQI that connects its expected performance to binomial statistics, and we identify concrete obstacles in further studying the complexity of DQI. Exploiting the fact that DQI output probabilities are efficiently computable, we apply Markov chain Monte Carlo (MCMC) techniques, particularly block-Gibbs sampling, to sample from the induced distribution. We study the runtime scaling of these methods for two optimization problems called max-XORSAT, where we reach beyond $1000$ effective qubits; and OPI, where we reach beyond $150$ effective qubits. Our results show that MCMC algorithms can reliably attain the approximation ratios expected from DQI across a broad range of problem sizes. In OPI, in the regime where a super-polynomial advantage is claimed for DQI, we observe an empirical runtime for MCMC that scales approximately as $1.1^{n}$, indicating exponential growth with a comparatively small base. Our findings do not refute existing quantum advantage claims but provide new empirical evidence that classical sampling algorithms can closely match DQI's optimization performance, offering a more nuanced perspective on the practical advantage of DQI.

Figures

Figures reproduced from arXiv: 2607.28120 by Almudena Carrera V\'azquez, Elies Gil-Fuster, Jens Eisert, Lennart Bittel, Matan Ninio, Stefan Woerner, Yishai Shimoni.

Figure 1
Figure 1. Figure 1: FIG. 1 [PITH_FULL_IMAGE:figures/full_fig_p001_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: FIG. 2 [PITH_FULL_IMAGE:figures/full_fig_p008_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: FIG. 3 [PITH_FULL_IMAGE:figures/full_fig_p009_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: FIG. 4 [PITH_FULL_IMAGE:figures/full_fig_p009_4.png] view at source ↗
Figure 5
Figure 5. Figure 5: FIG. 5 [PITH_FULL_IMAGE:figures/full_fig_p010_5.png] view at source ↗

discussion (0)

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

Reference graph

Works this paper leans on

46 extracted references · 11 linked inside Pith

  1. [1]

    Montanaro, Quantum algorithms: an overview, npj Quant

    A. Montanaro, Quantum algorithms: an overview, npj Quant. Inf.2, 15023 (2016)

    2016

  2. [2]

    A. M. Dalzell, S. McArdle, M. Berta, P. Bienias, C.-F. Chen, A. Gily´en, C. T. Hann, M. J. Kastoryano, E. T. Khabiboulline, A. Kubica,et al.,Quantum algorithms: A survey of applica- tions and end-to-end complexities(Cambridge University Press, Cambridge (UK), 2025)

    2025

  3. [3]

    Eisert and J

    J. Eisert and J. Preskill, Mind the gaps: The fraught road to quantum advantage, arXiv:2510.19928 (2025)

    Pith/arXiv arXiv 2025

  4. [4]

    Abbas, A

    A. Abbas, A. Ambainis, B. Augustino, A. B¨artschi, H. Buhrman, C. Coffrin, G. Cortiana, V . Dunjko, D. J. Egger, B. G. Elmegreen, N. Franco, F. Fratini, B. Fuller, J. Gacon, C. Gonciulea, S. Gri- bling, S. Gupta, S. Hadfield, R. Heese, G. Kircher, T. Kleinert, T. Koch, G. Korpas, S. Lenk, J. Marecek, V . Markov, G. Maz- zola, S. Mensa, N. Mohseni, G. Nann...

    2024

  5. [5]

    Pirnay, V

    N. Pirnay, V . Ulitzsch, F. Wilde, J. Eisert, and J.-P. Seifert, An in-principle super-polynomial quantum advantage for approxi- mating combinatorial optimization problems via computational learning theory, Science Adv.10, eadj5170 (2024)

    2024

  6. [6]

    S. P. Jordan, N. Shutty, M. Wootters, A. Zalcman, A. Schmid- huber, R. King, S. V . Isakov, T. Khattar, and R. Babbush, Opti- mization by decoded quantum interferometry, Nature646, 831 (2025)

    2025

  7. [7]

    T. Koch, D. E. B. Neira, Y . Chen, G. Cortiana, D. J. Egger, R. Heese, N. N. Hegade, A. G. Cadavid, R. Huang, T. Itoko, T. Kleinert, P. M. Xavier, N. Mohseni, J. A. Montanez-Barrera, K. Nakano, G. Nannicini, C. O’Meara, J. Pauckert, M. Proissl, A. Ramesh, M. Schicker, N. Shimada, M. Takeori, V . Valls, D. V . Bulck, S. Woerner, and C. Zoufal, Quantum opti...

    Pith/arXiv arXiv 2025

  8. [8]

    Regev, On lattices, learning with errors, random linear codes, and cryptography, J

    O. Regev, On lattices, learning with errors, random linear codes, and cryptography, J. ACM56, 34:1 (2009)

    2009

  9. [9]

    Marwaha, B

    K. Marwaha, B. Fefferman, A. Gheorghiu, and V . Havlicek, On the complexity of decoded quantum interferometry, 12 arXiv:2509.14443 (2025)

    Pith/arXiv arXiv 2025

  10. [10]

    M. J. Kramer, C. Schubert, and J. Eisert, Tight inapproximability of max-linsat and implications for decoded quantum interferom- etry, arXiv:2603.04540 (2026)

    arXiv 2026

  11. [11]

    M. J. Kramer, C. Schubert, and J. Eisert, Approximability limits for bounded-degree max-LINSAT and implications for decoded quantum interferometry, arXiv:2606.13570 (2026)

    Pith/arXiv arXiv 2026

  12. [12]

    Sun and M

    Y . Sun and M. Wootters, On worst-case optimal polynomial intersection, arXiv:2604.09533 (2026)

    Pith/arXiv arXiv 2026

  13. [13]

    E. R. Anschuetz, D. Gamarnik, and J. Z. Lu, Decoded quantum interferometry requires structure, arXiv:2509.14509 (2025)

    arXiv 2025

  14. [14]

    Parekh, No quantum advantage in decoded quantum interfer- ometry for MaxCut, arXiv:2509.19966 (2025)

    O. Parekh, No quantum advantage in decoded quantum interfer- ometry for MaxCut, arXiv:2509.19966 (2025)

    arXiv 2025

  15. [15]

    K. Bu, W. Gu, D. Enshan Koh, and X. Li, Decoded quantum interferometry under noise, Quant. Sc. Tech.11, 025010 (2026)

    2026

  16. [16]

    Sabater, O

    F. Sabater, O. El Harzli, G.-J. Besjes, M. Erdmann, J. Klepsch, J. Hiltrop, J.-F. Bobier, Y . Cao, and C. A. Riofr ´ıo, Towards solving industrial integer linear programs with decoded quantum interferometry, Quant. Sc. Tech.11, 025054 (2026)

    2026

  17. [17]

    Thelen and W

    S. Thelen and W. Mauerer, From constraint to code: Dqi-kit– a software framework for decoded quantum interferometry, arXiv:2605.16955 (2026)

    Pith/arXiv arXiv 2026

  18. [18]

    Khattar, N

    T. Khattar, N. Shutty, C. Gidney, A. Zalcman, N. Yosri, D. Maslov, R. Babbush, and S. P. Jordan, Verifiable quantum ad- vantage via optimized DQI circuits, arXiv:2510.10967 (2025)

    arXiv 2025

  19. [19]

    Patamawisut, N

    N. Patamawisut, N. Benchasattabuse, M. Hajdu ˇsek, and R. Van Meter, Quantum circuit design for decoded quantum interferometry, in2025 IEEE International Conference on Quan- tum Computing and Engineering (QCE), V ol. 1 (IEEE, 2025) pp. 291–301

    2025

  20. [20]

    Chailloux and J.-P

    A. Chailloux and J.-P. Tillich, Quantum advantage from soft decoders, inProceedings of the 57th Annual ACM Symposium on Theory of Computing(2025) pp. 738–749

    2025

  21. [21]

    Chailloux, OPI x soft decoders, arXiv:2511.22691 (2025)

    A. Chailloux, OPI x soft decoders, arXiv:2511.22691 (2025)

    arXiv 2025

  22. [22]

    Blanvillain, A

    A. Blanvillain, A. Chailloux, and J.-P. Tillich, The quan- tum decoding problem: tight achievability bounds and application to Regev’s reduction, IEEE Trans. Inf. Th. 10.48550/arXiv.2509.24796 (2026)

    doi:10.48550/arxiv.2509.24796 2026

  23. [23]

    Horinaga and T

    S. Horinaga and T. Yamakawa, Worst-case quantum algorithm for optimal polynomial intersection beyond decoded quantum interferometry, arXiv:2607.14650 (2026)

    Pith/arXiv arXiv 2026

  24. [24]

    Gu and S

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

    arXiv 2025

  25. [25]

    K. Bu, W. Gu, and X. Li, Multivariate decoded quantum interfer- ometry for weighted optimization, arXiv:2605.10666 (2026)

    Pith/arXiv arXiv 2026

  26. [26]

    Schmidhuber, J

    A. Schmidhuber, J. Z. Lu, N. Shutty, S. Jordan, A. Poremba, and Y . Quek, Hamiltonian decoded quantum interferometry, arXiv:2510.07913 (2025)

    arXiv 2025

  27. [27]

    K. Bu, W. Gu, and X. Li, Hamiltonian decoded quantum in- terferometry for general Pauli Hamiltonians, arXiv:2601.18773 (2026)

    arXiv 2026

  28. [28]

    Hangleiter and J

    D. Hangleiter and J. Eisert, Computational advantage of quantum random sampling, Rev. Mod. Phys.95, 035001 (2023)

    2023

  29. [29]

    Liu,Monte Carlo strategies in scientific computing, edited by J

    J. Liu,Monte Carlo strategies in scientific computing, edited by J. Liu (Springer Verlag, New York, Berlin, Heidelberg, 2008) p. 344

    2008

  30. [30]

    Gilks, S

    W. Gilks, S. Richardson, and D. Spiegelhalter,Markov Chain Monte Carlo in Practice, Chapman & Hall/CRC Interdisci- plinary Statistics (Taylor & Francis, 1995)

    1995

  31. [31]

    Robert and G

    C. Robert and G. Casella,Monte Carlo statistical methods (Springer Verlag, 2004)

    2004

  32. [32]

    Aaronson and A

    S. Aaronson and A. Arkhipov, The computational complexity of linear optics, Th. Comp.9, 143 (2013), arXiv:1011.3245

    Pith/arXiv arXiv 2013

  33. [33]

    E. R. Berlekamp,Algebraic coding theory - revised edition (WorldScientific, 2015)

    2015

  34. [34]

    H˚astad, Some optimal inapproximability results, J

    J. H˚astad, Some optimal inapproximability results, J. ACM48, 798–859 (2001)

    2001

  35. [35]

    Jo, Efficient exact quantum sampling from the sun-wootters distribution for optimal polynomial intersection, arXiv preprint arXiv:2607.16541 (2026)

    S. Jo, Efficient exact quantum sampling from the sun-wootters distribution for optimal polynomial intersection, arXiv preprint arXiv:2607.16541 (2026)

    Pith/arXiv arXiv 2026

  36. [36]

    Shutty, A

    N. Shutty, A. Mandal, S. Ragavan, Q. Buzet, A. Chailloux, N. C. Rubin, A. Khan, S. Boulebnane, R. Shaydulin, J. Azariah,et al., Optimization using locally-quantum decoders, arXiv preprint arXiv:2604.24633 (2026)

    Pith/arXiv arXiv 2026

  37. [37]

    dqi-mcmc, GitHub repository (2026)

    2026

  38. [38]

    S. K. Lam, A. Pitrou, and S. Seibert, Numba: a LLVM-based Python JIT compiler, inProceedings of the Second Workshop on the LLVM Compiler Infrastructure in HPC, LLVM ’15 (Associ- ation for Computing Machinery, New York, NY , USA, 2015)

    2015

  39. [39]

    Approximate sampling from decoded quantum interferometry via Markov chain Monte Carlo methods

    L. G. Valiant, The complexity of enumeration and reliability problems, SIAM J. Comp.8, 410 (1979). 13 Supplementary material for “Approximate sampling from decoded quantum interferometry via Markov chain Monte Carlo methods” Appendix A: Construction of the optimal polynomial Letf=f 1 +. . .+fm be the objective function, withf i :F p → {+1,−1},r:=|f −1 i (...

    1979

  40. [40]

    Obstacle against proving hardness of sampling One possible direction to tackle the complexity of sampling would be to reduce the sampling problem into a counting problem. Counting problems have been used to argue about the hardness of other sampling problems based on quantum circuits, like random circuit sampling and other quantum random sampling schemes ...

  41. [41]

    One natural way to define a decisionproblem would be, given a thresholdα∈Z, decide between: •YES: if there existsx∈F n 2 such thatf(x)≥α

    Obstacles against the standard reduction from search to decision Let us consider an abstract optimization problem specified by an objective function f:F n 2 →Z . One natural way to define a decisionproblem would be, given a thresholdα∈Z, decide between: •YES: if there existsx∈F n 2 such thatf(x)≥α. •NO: for allx∈F n 2 , it holdsf(x)< α. One natural way to...

  42. [42]

    Initializeg←(⊥) n, which is0-definite

  43. [43]

    (b) Query the oracle

    Repeatntimes, on thet th step: (a) Fix thet th component of the guessg t ←0, which is nowt-definite. (b) Query the oracle. IfO α(g) =YES, move to the next iteration; else correct thet th component of the guessg t ←1

  44. [44]

    Under the promise that a solution exists, Oα ((⊥)n) =YES , we reach a solution x after n queries

    Outputx=g. Under the promise that a solution exists, Oα ((⊥)n) =YES , we reach a solution x after n queries. The iterative procedure ensures that there exists a solution which agrees with the definite entries of the growing guess at all times, hence no back-tracking is required. This procedure can be straightforwardly generalized on fields Fp, where every...

  45. [45]

    breaks down

    The reduced problem arising from N-definite guesses for large N involves only a few variables n−N . In the reduction from optimization to decoding, we observe that the number of variables in the optimization problem corresponds to the number of parity checks in the error-correcting code. Knowing that an error-correcting code with few checks cannot have la...

  46. [46]

    From decoding being NP-hard, it follows that certain structure is required for DQI to perform well

    The performance guarantee assumes not only that ℓ is known, but also that an efficient decoder is provided. From decoding being NP-hard, it follows that certain structure is required for DQI to perform well. For us to be able to use Eq. (D1) throughout the procedure we would then need the added requirement that the structure is preserved under reducing th...