Optimal Coherent Quantum Phase Estimation via Tapering

Abstract

Due to its significance as a subroutine, in this work, we consider the coherent version of the quantum phase estimation problem, where given an arbitrary input state and black-box access to unitaries $U$ and controlled-$U$, the goal is to estimate the phases of $U$ in superposition. Most existing phase estimation algorithms involve intermediary measurements that disrupt coherence. Only a couple of algorithms, including the standard quantum phase estimation algorithm, consider this coherent setting. However, the standard algorithm only succeeds with a constant probability. To boost this success probability, one can employ the coherent median technique, resulting in an algorithm with asymptotically optimal query complexity (the total number of calls to $U$ and controlled-$U$). However, this coherent median technique requires a large number of ancilla qubits and a computationally expensive quantum sorting network. To address this, in this work, we propose an improved version of the standard algorithm called the tapered quantum phase estimation (tQPE) algorithm, which leverages tapering (or window) functions commonly used in classical signal processing. Our algorithm achieves the asymptotically optimal query complexity without requiring the expensive coherent median technique to boost success probability. Moreover, we find the absolutely optimal taper - not only in the asymptotic scaling but in terms of exact performance. We provide an efficiently preparable ancilla state based on an approximation of the optimal taper, which incurs at most a factor-of-two increase in the probability of error, thereby maintaining near-optimal performance in practice. In the appendices, we give an explicit construction of the taper state preparation circuit. Finally, we derive an error bound for coherent QPE when the phase estimate is used as a control and subsequently uncomputed.

37 pages, 8 figures; Major additions in version 3: worst-case to average-case reduction using phase randomization, derivation of an error bound for coherent QPE when the phase estimate is used as a control and subsequently uncomputed, explicit constructions of taper state preparation circuits

References in corpus (23)

• Quantum algorithm for solving linear systems of equations
• Quantum principal component analysis
• Analysis of Dynamic Brain Imaging Data
• Quantum singular value transformation and beyond: exponential improvements for quantum matrix arithmetics
• Quantum Data Fitting
• Quantum Metropolis Sampling
• Efficient Distributed Quantum Computing
• Heisenberg-limited ground state energy estimation for early fault-tolerant quantum computers
• Quantum phase estimation of multiple eigenvalues for small-scale (noisy) experiments
• A randomized quantum algorithm for statistical phase estimation
• Even shorter quantum circuit for phase estimation on early fault-tolerant quantum computers with applications to ground-state energy estimation
• Quantum Algorithms for Estimating Physical Quantities using Block-Encodings
• Quantum-accelerated multilevel Monte Carlo methods for stochastic differential equations in mathematical finance
• On low-depth algorithms for quantum phase estimation
• Spectral density estimation with the Gaussian Integral Transform
• Analyzing Prospects for Quantum Advantage in Topological Data Analysis
• Linear embedding of nonlinear dynamical systems and prospects for efficient quantum algorithms
• Bayesian Quantum Multiphase Estimation Algorithm
• The Eigenvalue Distribution of Discrete Periodic Time-Frequency Limiting Operators
• Effects of Cosine Tapering Window on Quantum Phase Estimation
• Discrete-to-continuous transition in quantum phase estimation
• Automatic Post-selection by Ancillae Thermalisation
• Efficient state initialization by a quantum spectral filtering algorithm

Cited by in corpus (2)

• Fault-tolerant quantum algorithms for quantum molecular systems: A survey
• Quantum phase estimation with optimal confidence interval using three control qubits