Pseudo-deterministic Quantum Algorithms
2026-02-19 • Computational Complexity
Computational Complexity
AI summaryⓘ
The authors study a special type of quantum algorithm called pseudo-deterministic algorithms, which almost always give the same unique answer for each input. They find some problems that are very easy for classical random algorithms but hard for these quantum algorithms, and others where quantum pseudo-deterministic algorithms are much faster than classical ones. They also show that quantum pseudo-deterministic algorithms can only be somewhat better than deterministic ones on general problems. Finally, they identify certain quantum search tasks that can be made pseudo-deterministic without much extra work.
pseudo-deterministic algorithmsquantum algorithmsquery complexityGrover's algorithmrandomized algorithmsquantum speed-uplower bound techniqueselement distinctnesstriangle findinggraph collision
Authors
Hugo Aaronson, Tom Gur, Jiawei Li
Abstract
We initiate a systematic study of pseudo-deterministic quantum algorithms. These are quantum algorithms that, for any input, output a canonical solution with high probability. Focusing on the query complexity model, our main contributions include the following complexity separations, which require new lower bound techniques specifically tailored to pseudo-determinism: - We exhibit a problem, Avoid One Encrypted String (AOES), whose classical randomized query complexity is $O(1)$ but is maximally hard for pseudo-deterministic quantum algorithms ($Ω(N)$ query complexity). - We exhibit a problem, Quantum-Locked Estimation (QL-Estimation), for which pseudo-deterministic quantum algorithms admit an exponential speed-up over classical pseudo-deterministic algorithms ($O(\log(N))$ vs. $Θ(\sqrt{N})$), while the randomized query complexity is $O(1)$. Complementing these separations, we show that for any total problem $R$, pseudo-deterministic quantum algorithms admit at most a quintic advantage over deterministic algorithms, i.e., $D(R) = \tilde O(psQ(R)^5)$. On the algorithmic side, we identify a class of quantum search problems that can be made pseudo-deterministic with small overhead, including Grover search, element distinctness, triangle finding, $k$-sum, and graph collision.