Tight Bounds for Quantum Phase Estimation and Related Problems
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2023
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866908706110701568 |
|---|---|
| author | Mande, Nikhil S. de Wolf, Ronald |
| author_facet | Mande, Nikhil S. de Wolf, Ronald |
| contents | Phase estimation, due to Kitaev [arXiv'95], 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 ψ\rangle$ of $U$ with unknown eigenvalue $e^{iθ}$, and the task is to estimate the eigenphase $θ$ within $\pmδ$, 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 $γ$ 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~[ITCS'23].
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 $δ$ and error probability $ε$ has cost $Ω\left(\frac{1}δ\log\frac{1}ε\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/ε)})$. Our lower bound uses a variant of the polynomial method with trigonometric polynomials. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2305_04908 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Tight Bounds for Quantum Phase Estimation and Related Problems Mande, Nikhil S. de Wolf, Ronald Quantum Physics Computational Complexity Phase estimation, due to Kitaev [arXiv'95], 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 ψ\rangle$ of $U$ with unknown eigenvalue $e^{iθ}$, and the task is to estimate the eigenphase $θ$ within $\pmδ$, 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 $γ$ 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~[ITCS'23]. 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 $δ$ and error probability $ε$ has cost $Ω\left(\frac{1}δ\log\frac{1}ε\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/ε)})$. Our lower bound uses a variant of the polynomial method with trigonometric polynomials. |
| title | Tight Bounds for Quantum Phase Estimation and Related Problems |
| topic | Quantum Physics Computational Complexity |
| url | https://arxiv.org/abs/2305.04908 |