{"id":"arxiv/2602.17647","url":"https://arxiv.org/abs/2602.17647","tags":["quant-ph","cs.CC"],"score":0,"title":"Pseudo-deterministic Quantum Algorithms","domain":"quant-ph","source":"arxiv","authors":["Hugo Aaronson","Tom Gur","Jiawei Li"],"reviews":0,"subject":"quant-ph","summary":"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…","category":"research","comments":0,"disputed":false,"division":"physics","mentions":0,"discussed":0,"published":"2026-02-19","reactions":{}}