{
  "$type": "site.standard.document",
  "bskyPostRef": {
    "cid": "bafyreih32or5epyy4yiwv2kqseimteeadc5bffz4qlmorbdgbn3uydkx6y",
    "uri": "at://did:plc:cx57fsir6oyzywdd4jafsdsw/app.bsky.feed.post/3moez7ttcghj2"
  },
  "path": "/papers/q-2026-06-15-2140/",
  "publishedAt": "2026-06-15T14:09:03.000Z",
  "site": "https://quantum-journal.org",
  "tags": [
    "Paper",
    "https://doi.org/10.22331/q-2026-06-15-2140"
  ],
  "textContent": "Quantum 10, 2140 (2026).\n\nhttps://doi.org/10.22331/q-2026-06-15-2140\n\nPhase estimation, due to Kitaev [17], is one of the most fundamental subroutines in quantum computing. In the basic scenario, one is given black-box access to a unitary $U$, and an eigenstate $\\lvert \\psi \\rangle$ of $U$ with unknown eigenvalue $e^{i\\theta}$, and the task is to estimate the eigenphase $\\theta$ within $\\pm\\delta$, with high probability. The cost of an algorithm for us is the number of applications of $U$ and $U^{-1}$. We tightly characterize the cost of several variants of phase estimation where we are no longer given an eigenstate, but are required to estimate the maximum eigenphase of $U$, aided by advice in the form of states (or a unitary preparing those states) which are promised to have at least a certain overlap $\\gamma$ with the top eigenspace. We give algorithms and nearly matching lower bounds for all ranges of parameters. We show that a small number of copies of the advice state (or of an advice-preparing unitary) are not significantly better than having no advice at all. We also show that having lots of advice (applications of the advice-preparing unitary) does not significantly reduce cost, and neither does knowledge of the eigenbasis of $U$. We immediately obtain a lower bound on the complexity of the Unitary recurrence time problem, resolving an open question of She and Yuen [29]. Lastly, we study how efficiently one can reduce the error probability in the basic phase-estimation scenario. We show that a phase-estimation algorithm with precision $\\delta$ and error probability $\\epsilon$ has cost $\\Omega\\left(\\frac{1}{\\delta}\\log\\frac{1}{\\epsilon}\\right)$, matching an easy upper bound. This contrasts with some other scenarios in quantum computing (e.g., search) where error-probability reduction costs only a factor $O(\\sqrt{\\log(1/\\epsilon)})$. Our lower bound uses a variant of the polynomial method with trigonometric polynomials.",
  "title": "Tight Bounds for Quantum Phase Estimation and Related Problems"
}