pith. sign in

arxiv: 2509.14443 · v2 · submitted 2025-09-17 · 🪐 quant-ph · cs.CC

On the Complexity of Decoded Quantum Interferometry

Kunal Marwaha , Bill Fefferman , Alexandru Gheorghiu , Vojtech Havlicek This is my paper

Pith reviewed 2026-05-18 15:30 UTC · model grok-4.3

classification 🪐 quant-ph cs.CC
keywords Decoded Quantum Interferometrypolynomial hierarchyquantum supremacyMacWilliams identityquantum harmonic oscillatorapproximate optimizationquantum complexityclassical simulation
0
0 comments X

The pith

Decoded Quantum Interferometry can be classically simulated inside the polynomial hierarchy

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

The paper examines the complexity of Decoded Quantum Interferometry, a quantum algorithm for approximate optimization. It shows that DQI evades classical simulation attempts that simply locate high-probability outputs. The main result establishes that DQI nonetheless admits simulation at a low level of the polynomial hierarchy. This places the algorithm in a class that challenges standard quantum supremacy arguments based on presumed hardness. The authors also demonstrate that DQI constructively satisfies a classical coding bound from the MacWilliams identity and reinterpret the procedure as preparing low-energy states of a quantum simple harmonic oscillator.

Core claim

DQI resists classical simulation strategies based on locating outputs with large probabilities, yet it can be simulated at a low level of the polynomial hierarchy. This simulation challenges standard quantum supremacy arguments. DQI further provides a constructive solution to a classical coding-theoretic bound based on the MacWilliams identity. The algorithm admits an interpretation as preparing low-energy states of a quantum simple harmonic oscillator, which suggests a route to generalizations.

What carries the argument

Decoded Quantum Interferometry (DQI), the procedure of decoding a quantum state to induce interference patterns for approximate optimization

If this is right

  • DQI resists classical simulation strategies based on locating outputs with large probabilities.
  • DQI provides a constructive solution to a classical coding-theoretic bound based on the MacWilliams identity.
  • DQI prepares low-energy states of a quantum simple harmonic oscillator.
  • The polynomial-hierarchy simulation of DQI challenges standard quantum supremacy arguments that assume hardness for such interference algorithms.

Where Pith is reading between the lines

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

  • Other quantum algorithms that combine decoding with interference may admit similar polynomial-hierarchy simulations.
  • The MacWilliams identity link could be used to derive new classical bounds for optimization problems solved by DQI.
  • Hardware experiments that realize the harmonic-oscillator viewpoint might reveal practical ways to extend DQI to larger problem sizes.

Load-bearing premise

The DQI output distribution and interference structure allow classical simulation inside the polynomial hierarchy while still resisting simpler probability-based classical strategies.

What would settle it

An explicit classical algorithm that approximates DQI output distributions without using polynomial-hierarchy techniques, or a hardness proof showing that no such polynomial-hierarchy simulation exists, would decide the claim.

Figures

Figures reproduced from arXiv: 2509.14443 by Alexandru Gheorghiu, Bill Fefferman, Kunal Marwaha, Vojtech Havlicek.

Figure 1
Figure 1. Figure 1: By Theorem 33, DQI can find codewords at essentially any distance in [ m 2 − p ℓ(m − ℓ), m 2 + p ℓ(m − ℓ)], where ℓ is the maximum number of efficiently decodable errors in the dual code. Using classical linear programming techniques (i.e. Appendix D), we can predict the existence of codewords in this region all the way up to the decoding threshold d ⊥/2; these codewords are displayed in green. We do not k… view at source ↗
read the original abstract

We study the complexity of Decoded Quantum Interferometry (DQI), a quantum algorithm for approximate optimization. First, we show that the algorithm resists classical simulation strategies based on locating outputs with large probabilities. We then prove that DQI can be simulated at a low level of the polynomial hierarchy, posing challenges to standard quantum supremacy arguments. We further show that DQI is a constructive solution to a classical coding-theoretic bound based on the MacWilliams identity. Lastly, we interpret DQI as preparing low-energy states of a quantum simple harmonic oscillator, a viewpoint we believe suggests a physics-motivated route to generalizing DQI.

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

2 major / 2 minor

Summary. The manuscript analyzes the complexity of Decoded Quantum Interferometry (DQI), a quantum algorithm for approximate optimization. It first shows that DQI resists classical simulation strategies that locate high-probability outputs. It then proves that DQI can be simulated at a low level of the polynomial hierarchy, which challenges standard quantum supremacy arguments. The work further provides a constructive solution to a classical coding-theoretic bound derived from the MacWilliams identity and interprets DQI as preparing low-energy states of a quantum simple harmonic oscillator.

Significance. If the central claims are verified, the result is significant for quantum complexity theory: placing a quantum optimization algorithm in low PH while demonstrating resistance to certain classical sampling strategies offers a concrete counterexample to broad supremacy claims. The constructive coding-theoretic result and the SHO physical interpretation are additional strengths that bridge quantum algorithms with coding theory and physics.

major comments (2)
  1. [PH simulation section (following resistance argument)] The proof that DQI admits simulation at a low level of the PH (the section following the resistance-to-large-probability argument) is load-bearing for the challenge to quantum supremacy. The manuscript must explicitly derive how the post-decoding interference pattern, combined with the MacWilliams identity, permits deciding support or marginal properties of the output distribution via a constant number of NP or coNP queries without requiring enumeration or collapsing to simpler probability-based strategies. If decoding correlations are not efficiently characterizable, the reduction fails.
  2. [Resistance to large-probability simulation] The claim that DQI resists classical simulation based on locating large-probability outputs is stated in the abstract and early sections, but the error analysis and precise conditions under which this resistance holds (e.g., for the specific decoding map) need to be expanded to confirm it does not inadvertently allow efficient classical approximation of the same distribution properties used in the PH argument.
minor comments (2)
  1. [Abstract and main theorems] Clarify the precise level of the polynomial hierarchy (e.g., Σ₂ᵖ or Π₂ᵖ) in the statement of the simulation result and ensure consistent notation for the decoding map across the complexity and coding sections.
  2. [Physical interpretation] The SHO interpretation section would benefit from an explicit mapping between the DQI circuit parameters and the oscillator Hamiltonian to make the low-energy state claim more directly verifiable.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for their careful reading and constructive comments on our manuscript. We address each major comment below and have revised the manuscript to incorporate the requested clarifications and expansions.

read point-by-point responses

  1. Referee: [PH simulation section (following resistance argument)] The proof that DQI admits simulation at a low level of the PH (the section following the resistance-to-large-probability argument) is load-bearing for the challenge to quantum supremacy. The manuscript must explicitly derive how the post-decoding interference pattern, combined with the MacWilliams identity, permits deciding support or marginal properties of the output distribution via a constant number of NP or coNP queries without requiring enumeration or collapsing to simpler probability-based strategies. If decoding correlations are not efficiently characterizable, the reduction fails.

    Authors: We thank the referee for highlighting the need for greater explicitness in this load-bearing section. We agree that the derivation benefits from additional detail. In the revised manuscript we have inserted a new subsection that walks through the reduction: the post-decoding interference pattern is expressed via the MacWilliams identity as a linear combination of dual-code weight enumerators; deciding whether a given output has positive support or a given marginal exceeds a threshold then reduces to the existence of a low-weight vector in the dual code satisfying a constant number of linear constraints. These existence questions are NP (or coNP) and require only a constant number of adaptive oracle calls. Because the DQI decoding map is linear and the relevant error patterns lie in a polynomially bounded Hamming ball, the correlations among decoded bits are efficiently characterizable by the same weight-enumerator queries; the procedure therefore does not enumerate the output distribution and remains distinct from the direct probability-sampling strategies analyzed in the resistance section. revision: yes

  2. Referee: [Resistance to large-probability simulation] The claim that DQI resists classical simulation based on locating large-probability outputs is stated in the abstract and early sections, but the error analysis and precise conditions under which this resistance holds (e.g., for the specific decoding map) need to be expanded to confirm it does not inadvertently allow efficient classical approximation of the same distribution properties used in the PH argument.

    Authors: We appreciate the request for a more precise error analysis. In the revised manuscript we have expanded the relevant section to include explicit bounds: under the assumption that the underlying linear code has minimum distance linear in the block length, any classical algorithm that outputs a string whose probability under the DQI distribution exceeds an inverse-polynomial threshold must solve an instance of the bounded-distance decoding problem that is believed to be hard. We further show that the PH simulation decides only support and marginal properties via decision oracles and does not yield an efficient classical procedure for approximating the same high-probability outputs; the two results therefore remain consistent. The expanded analysis now states the precise parameter regime (code rate, distance, and decoding radius) under which the resistance claim holds. revision: yes

Circularity Check

0 steps flagged

No significant circularity; derivation is self-contained in complexity theory

full rationale

The paper's central claims—that DQI resists large-probability classical sampling yet admits simulation at a low level of the polynomial hierarchy—are derived from the MacWilliams identity (a standard coding-theoretic fact) applied to the DQI output distribution and interference structure. No step reduces by construction to a fitted parameter, self-definition, or load-bearing self-citation whose validity depends on the present work. The PH placement exploits the specific decoding map and interference pattern without collapsing to the very sampling resistance being proved separately. The argument is therefore independent of its own outputs and stands against external benchmarks in complexity theory and coding theory.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The central claims rest on standard mathematical frameworks from complexity theory and coding theory with no free parameters or new invented entities introduced.

axioms (2)
  • standard math Standard properties of the polynomial hierarchy
    Invoked to place the DQI simulation at a low level.
  • standard math MacWilliams identity from coding theory
    Basis for the constructive solution to the coding-theoretic bound.

pith-pipeline@v0.9.0 · 5635 in / 1177 out tokens · 71754 ms · 2026-05-18T15:30:00.876285+00:00 · methodology

discussion (0)

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

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

What do these tags mean?
matches
The paper's claim is directly supported by a theorem in the formal canon.
supports
The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends
The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses
The paper appears to rely on the theorem as machinery.
contradicts
The paper's claim conflicts with a theorem or certificate in the canon.
unclear
Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Forward citations

Cited by 8 Pith papers

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

  1. Multivariate Decoded Quantum Interferometry for Weighted Optimization

    quant-ph 2026-05 unverdicted novelty 7.0

    The work develops multivariate DQI states for weighted Max-LINSAT over prime fields, derives closed-form asymptotic expressions for expectation values and concentration, provides an explicit single-decoder preparation...

  2. Multivariate Decoded Quantum Interferometry for Weighted Optimization

    quant-ph 2026-05 unverdicted novelty 7.0

    Multivariate DQI uses N-variable polynomials for weighted Max-LINSAT, derives closed-form asymptotics for expectation and concentration, provides a single-decoder preparation circuit, and shows outperformance over wei...

  3. From Constraint to Code: DQI-Kit -- A Software Framework for Decoded Quantum Interferometry

    quant-ph 2026-05 unverdicted novelty 6.0

    DQI-Kit automates encoding of objectives and constraints into Max-LINSAT instances and estimates expected DQI performance on the resulting problems.

  4. Regev's reduction as a candidate quantum algorithm for the discrete logarithm problem in finite abelian groups

    quant-ph 2026-05 unverdicted novelty 6.0

    Regev's reduction on Cheng-Wan DLOG instances does not yield an efficient quantum algorithm for discrete log because decoders fall short of the threshold and the Pretty Good Measurement is inefficient.

  5. Hidden Quantum Advantage near the Decoding Threshold of Decoded Quantum Interferometry

    quant-ph 2026-04 unverdicted novelty 5.0

    A Master Theorem gives a strictly tighter lower bound on quantum advantage in DQI by replacing the worst-case error penalty with an eigenvector-weighted Rayleigh quotient penalty.

  6. Mind the gaps: The fraught road to quantum advantage

    quant-ph 2025-10 unverdicted novelty 4.0

    The authors identify four transitions needed to reach fault-tolerant application-scale quantum computing from current NISQ devices.

  7. Mind the gaps: The fraught road to quantum advantage

    quant-ph 2025-10 unverdicted novelty 3.0

    The paper identifies four key hurdles in the transition from NISQ to FASQ quantum computers and argues that targeting them will accelerate progress toward useful quantum advantage.

  8. Quantum Decoding Algorithms: Quantum Speedups in Optimization

    quant-ph 2026-05 unverdicted novelty 1.0

    A review describing the Decoded Quantum Interferometry algorithm for quantum speedups in max-LINSAT optimization, with claimed superpolynomial advantage in the OPI problem.

Reference graph

Works this paper leans on

7 extracted references · 7 canonical work pages · cited by 6 Pith papers · 2 internal anchors

  1. [1]

    Quantum Algorithms for Variants of Average- Case Lattice Problems via Filtering

    doi: 10.1051/m2an/2024001. [CHM23] Antares Chen, Neng Huang, and Kunal Marwaha. Local algorithms and the failure of log-depth quantum advantage on sparse random CSPs . 2023. arXiv: 2310.01563. [CLZ22] Yilei Chen, Qipeng Liu, and Mark Zhandry. “Quantum Algorithms for Variants of Average- Case Lattice Problems via Filtering”. In: Advances in Cryptology – EU...

    work page doi:10.1051/m2an/2024001 2023

  2. [2]

    Encoding a qubit in an oscillator

    doi: 10.1145/73007.73010. [GKP01] Daniel Gottesman, Alexei Kitaev, and John Preskill. “Encoding a qubit in an oscillator”. In: Physical Review A 64.1 (June 2001). issn: 1094-1622. doi: 10.1103/physreva.64.012310. [Gur10] Venkatesan Guruswami. 15-859V: Introduction to Coding Theory . 2010. url: https://www. cs.cmu.edu/~venkatg/teaching/codingtheory/. [HW00...

    work page doi:10.1145/73007.73010 2001

  3. [3]

    Proceedings of the Forty-First Annual ACM Symposium on Theory of Computing , pages =

    doi: 10.1145/1536414.1536461. [Reg09] Oded Regev. “On lattices, learning with errors, random linear codes, and cryptography”. In: Journal of the ACM (JACM) 56.6 (2009), pp. 1–40. doi: 10.1145/1568318.1568324. arXiv: 2401.03703. [Sam23] Alex Samorodnitsky. “One more proof of the first linear programming bound for binary codes and two conjectures”. In: Isra...

    work page doi:10.1145/1536414.1536461 2009

  4. [4]

    Efficient Quantum Algorithms for Estimating Gauss Sums

    arXiv: quant-ph/0207131. [Vya03] Michael N. Vyalyi. Hardness of approximating the weight enumerator of a binary linear code

    work page internal anchor Pith review Pith/arXiv arXiv

  5. [5]

    Hardness of approximating the weight enumerator of a binary linear code

    arXiv: cs/0304044. [YZ24] Takashi Yamakawa and Mark Zhandry. “Verifiable quantum advantage without structure”. In: Journal of the ACM 71.3 (2024), pp. 1–50. doi: 10.1145/3658665. arXiv: 2204.02063. 30 A Deferred proofs Definition 38. The kth elementary symmetric polynomial P (k) on m inputs is defined as P (k)(a1, . . . , am) = X i1,...,ik distinct ai1 × ...

    work page internal anchor Pith review Pith/arXiv arXiv doi:10.1145/3658665 2024

  6. [6]

    The state |ψ′ P ⟩ is supported on |s⟩ if and only if the decoder successfully infers some y where |y| ≤ ℓ

    Given a basis state |s⟩ where s = BT y, we can use the DQI decoder to classically infer y. The state |ψ′ P ⟩ is supported on |s⟩ if and only if the decoder successfully infers some y where |y| ≤ ℓ. If the decoder fails, ⟨s|ψ′ P ⟩ = 0. Otherwise, ⟨s|ψ′ P ⟩ = w|y| 1q ( m |y|)(−1)v·y

    work page

  7. [7]

    | ⟨x|ψ′ P ⟩ |2}, we first sample k ∈ [0, 1,

    To sample from the distribution {x w.p. | ⟨x|ψ′ P ⟩ |2}, we first sample k ∈ [0, 1, . . . , ℓ] according to probability distribution ( |w0|2, |w1|2, . . . ,|wℓ|2). Then, sample a uniformly random subset S ⊆ [m] of size |S| = k. Let y ∈ Fm 2 be the indicator vector of S; then return BT y. Corollary 43. Consider a DQI state |ψP ⟩ from Eq. (2) prepared with ...

    work page