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 weighted Prange for some OPI cases while extending to Hamiltonian DQI.
On the Complexity of Decoded Quantum Interferometry
8 Pith papers cite this work. Polarity classification is still indexing.
8
Pith papers citing it
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.
citation-role summary
background 4
citation-polarity summary
fields
quant-ph 8verdicts
UNVERDICTED 8roles
background 3representative citing papers
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.
Decoded quantum interferometry is generalized to translation association schemes, reducing analysis to tridiagonal eigenvalue problems, with a finite-field matrix rank-difference protocol that produces constant-probability residual-rank bounds but no additive optimality guarantee.
DQI-Kit automates encoding of objectives and constraints into Max-LINSAT instances and estimates expected DQI performance on the resulting problems.
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.
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.
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.
A review describing the Decoded Quantum Interferometry algorithm for quantum speedups in max-LINSAT optimization, with claimed superpolynomial advantage in the OPI problem.
citing papers explorer
-
Multivariate Decoded Quantum Interferometry for Weighted Optimization
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 weighted Prange for some OPI cases while extending to Hamiltonian DQI.
-
Approximability limits for bounded-degree max-LINSAT and implications for decoded quantum interferometry
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.
-
Decoded Quantum Interferometry Beyond Hamming: Rank-Metric and Translation Association Schemes
Decoded quantum interferometry is generalized to translation association schemes, reducing analysis to tridiagonal eigenvalue problems, with a finite-field matrix rank-difference protocol that produces constant-probability residual-rank bounds but no additive optimality guarantee.
-
From Constraint to Code: DQI-Kit -- A Software Framework for Decoded Quantum Interferometry
DQI-Kit automates encoding of objectives and constraints into Max-LINSAT instances and estimates expected DQI performance on the resulting problems.
-
Regev's reduction as a candidate quantum algorithm for the discrete logarithm problem in finite abelian groups
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.
-
Hidden Quantum Advantage near the Decoding Threshold of Decoded Quantum Interferometry
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.
-
Mind the gaps: The fraught road to quantum advantage
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.
-
Quantum Decoding Algorithms: Quantum Speedups in Optimization
A review describing the Decoded Quantum Interferometry algorithm for quantum speedups in max-LINSAT optimization, with claimed superpolynomial advantage in the OPI problem.