Share on Facebook Tweet on Twitter Share on LinkedIn Share by email
Faster Phase Estimation

Krysta M. Svore, Matthew B. Hastings, and Michael Freedman


We develop several algorithms for performing quantum phase estimation based on basic measurements and classical post-processing. We present a pedagogical review of quantum phase estimation and simulate the algorithm to numerically determine its scaling in circuit depth and width. We show that the use of purely random measurements requires a number of measurements that is optimal up to constant factors, albeit at the cost of exponential classical post-processing; the method can also be used to improve classical signal processing. We then develop a quantum algorithm for phase estimation that yields an asymptotic improvement in runtime, coming within a factor of log* of the minimum number of measurements required while still requiring only minimal classical post-processing. The corresponding quantum circuit requires asymptotically lower depth and width (number of qubits) than quantum phase estimation.


Publication typeArticle
Published inQuantum Information and Computation
PublisherRinton Press
> Publications > Faster Phase Estimation