2026-09-08T01:22:02Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:26392 2026-09-05T19:41:57Z ddc:004 open_access

Pseudo-Deterministic Quantum Algorithms Aaronson, Hugo Gur, Tom Li, Jiawei Pseudo-determinism Quantum Computing Algorithms 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. Θ(√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., 𝖣(R) = Õ(psQ(R)⁵). 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Hugo Aaronson and Tom Gur and Jiawei Li 2026 Is Part Of LIPIcs, Volume 374, 53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2026.3 urn:nbn:de:0030-drops-263928 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2026.3 eng https://creativecommons.org/licenses/by/4.0/legalcode