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.
Szegedy, Quantum advantage for combinatorial optimiza- tion problems, simplified, (2022)
2 Pith papers cite this work. Polarity classification is still indexing.
2
Pith papers citing it
citation-role summary
background 2
citation-polarity summary
fields
quant-ph 2verdicts
UNVERDICTED 2roles
background 1polarities
support 1representative citing papers
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.
citing papers explorer
-
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.
-
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.