2025/04/21 by Li, Guanzhong, Li, Lvzhou, Luo, Jingquan · 2 citations
#FOS: Physical sciences #Quantum Physics (quant-ph)
paper · doi:10.48550/arxiv.2504.15194
We study the phase discrimination problem, in which we want to decide whether the eigenphase θ∈(-π,π] of a given eigenstate |ψ⟩ with eigenvalue eiθ 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 Θ(\frac1λlog\frac1δ) 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((1)/(λ√(ε))) and query complexity O((1)/(√(ε))), where λ is the gap between the zero and non-zero eigenvalues of the graph Laplacian and ε 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 O(n11) to O(n8), in a welded-tree circuit graph with Θ(n2n) vertices. Besides these two applications, we argue that more quantum algorithms might benefit from QPD.