{
  "$type": "site.standard.document",
  "bskyPostRef": {
    "cid": "bafyreigzrywjxxx46xctrtu2ld2ppm4v23fmqwicxpnulhpieutqzsfqre",
    "uri": "at://did:plc:4rgrdigiftglskeax4wvmsev/app.bsky.feed.post/3mfbbl5blohm2"
  },
  "coverImage": {
    "$type": "blob",
    "ref": {
      "$link": "bafkreiflo6xt7is6b2iafwghkjahlgggocme5jwjsbeuqqwcywuvjhmszm"
    },
    "mimeType": "image/png",
    "size": 24783
  },
  "path": "/abs/2602.17647v1",
  "publishedAt": "2026-02-20T01:00:00.000Z",
  "site": "https://arxiv.org",
  "tags": [
    "Hugo Aaronson",
    "Tom Gur",
    "Jiawei Li"
  ],
  "textContent": "**Authors:** Hugo Aaronson, Tom Gur, Jiawei Li\n\nWe 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.",
  "title": "Pseudo-deterministic Quantum Algorithms"
}