Faster Phase Estimation

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

Abstract

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.

Details

Publication typeArticle
Published inQuantum Information and Computation
URLhttp://arxiv.org/abs/1304.0741
Pages306-328
Volume14
Number3&4
PublisherRinton Press
> Publications > Faster Phase Estimation