Quantum phase discrimination with applications to quantum search on graphs
Fuente:
arXiv
Salvato in:
| Autori principali: | , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866915252376961024 |
|---|---|
| author | Li, Guanzhong Li, Lvzhou Luo, Jingquan |
| author_facet | Li, Guanzhong Li, Lvzhou Luo, Jingquan |
| contents | We study the phase discrimination problem, in which we want to decide whether the eigenphase $θ\in(-π,π]$ of a given eigenstate $|ψ\rangle$ with eigenvalue $e^{iθ}$ is zero or not, using applications of the unitary $U$ provided as a black box oracle.We propose a quantum algorithm named {\it quantum phase discrimination(QPD)} for this task, with optimal query complexity $Θ(\frac{1}λ\log\frac{1}δ)$ to the oracle $U$, where $λ$ is the gap between zero and non-zero eigenphases and $δ$ the allowed one-sided error. The quantum circuit is simple, consisting of only one ancillary qubit and a sequence of controlled-$U$ interleaved with single qubit $Y$ rotations, whose angles are given by a simple analytical formula. Quantum phase discrimination could become a fundamental subroutine in other quantum algorithms, as we present two applications to quantum search on graphs:
i) Spatial search on graphs. Inspired by the structure of QPD, we propose a new quantum walk model, and based on them we tackle the spatial search problem, obtaining a novel quantum search algorithm. For any graph with any number of marked vertices, the quantum algorithm that can find a marked vertex with probability $Ω(1)$ in total evolution time $ O(\frac{1}{λ\sqrt{\varepsilon}})$ and query complexity $ O(\frac{1}{\sqrt{\varepsilon}})$, where $λ$ is the gap between the zero and non-zero eigenvalues of the graph Laplacian and $\varepsilon$ is a lower bound on the proportion of marked vertices.
ii) Path-finding on graphs.} By using QPD, we reduce the query complexity of a path-finding algorithm proposed by Li and Zur [arxiv: 2311.07372] from $\tilde{O}(n^{11})$ to $\tilde{O}(n^8)$, in a welded-tree circuit graph with $Θ(n2^n)$ vertices.
Besides these two applications, we argue that more quantum algorithms might benefit from QPD. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2504_15194 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Quantum phase discrimination with applications to quantum search on graphs Li, Guanzhong Li, Lvzhou Luo, Jingquan Quantum Physics We study the phase discrimination problem, in which we want to decide whether the eigenphase $θ\in(-π,π]$ of a given eigenstate $|ψ\rangle$ with eigenvalue $e^{iθ}$ is zero or not, using applications of the unitary $U$ provided as a black box oracle.We propose a quantum algorithm named {\it quantum phase discrimination(QPD)} for this task, with optimal query complexity $Θ(\frac{1}λ\log\frac{1}δ)$ to the oracle $U$, where $λ$ is the gap between zero and non-zero eigenphases and $δ$ the allowed one-sided error. The quantum circuit is simple, consisting of only one ancillary qubit and a sequence of controlled-$U$ interleaved with single qubit $Y$ rotations, whose angles are given by a simple analytical formula. Quantum phase discrimination could become a fundamental subroutine in other quantum algorithms, as we present two applications to quantum search on graphs: i) Spatial search on graphs. Inspired by the structure of QPD, we propose a new quantum walk model, and based on them we tackle the spatial search problem, obtaining a novel quantum search algorithm. For any graph with any number of marked vertices, the quantum algorithm that can find a marked vertex with probability $Ω(1)$ in total evolution time $ O(\frac{1}{λ\sqrt{\varepsilon}})$ and query complexity $ O(\frac{1}{\sqrt{\varepsilon}})$, where $λ$ is the gap between the zero and non-zero eigenvalues of the graph Laplacian and $\varepsilon$ is a lower bound on the proportion of marked vertices. ii) Path-finding on graphs.} By using QPD, we reduce the query complexity of a path-finding algorithm proposed by Li and Zur [arxiv: 2311.07372] from $\tilde{O}(n^{11})$ to $\tilde{O}(n^8)$, in a welded-tree circuit graph with $Θ(n2^n)$ vertices. Besides these two applications, we argue that more quantum algorithms might benefit from QPD. |
| title | Quantum phase discrimination with applications to quantum search on graphs |
| topic | Quantum Physics |
| url | https://arxiv.org/abs/2504.15194 |