{"id":"arxiv/2610.01902","url":"https://arxiv.org/abs/2610.01902","tags":["quant-ph","cs.CC","cs.DS"],"score":0,"title":"Exponential quantum advantages for decoded quantum interferometry in the streaming setting","domain":"quant-ph","source":"arxiv","authors":["Kewen Wu","Guangxu Yang"],"reviews":0,"subject":"quant-ph","summary":"Decoded quantum interferometry (DQI) is a polynomial-time quantum algorithm introduced by Jordan et al. (Nature 2025). For a natural optimization problem, known as optimal polynomial intersection (OPI), it achieves approximation guarantees in regimes where all known classical algorithms require exponential time. Besides time, space is another central resource: storing and manipulating a massive input can be very challenging, especially when logical qubits carry substantial fault-tolerant implementation overhead. This motivates the following question: does DQI yield quantum advantages in…","category":"research","comments":0,"disputed":false,"division":"physics","mentions":0,"discussed":0,"published":"2026-10-01","reactions":{}}