Recognition: unknown
On the Complexity of Decoded Quantum Interferometry
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.
This paper has not been read by Pith yet.
Forward citations
Cited by 4 Pith papers
-
Decoded Quantum Interferometry for Weighted Optimization Problems
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...
-
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.
-
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.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.