Heisenberg-limited quantum phase estimation of multiple eigenvalues with few control qubits

Alicja Dutkiewicz1, Barbara M. Terhal2, and Thomas E. O'Brien1,3

1Instituut-Lorentz, Universiteit Leiden, 2300 RA Leiden, The Netherlands
2QuTech, Delft University of Technology, P.O. Box 5046, 2600 GA Delft, The Netherlands and JARA Institute for Quantum Information, Forschungszentrum Juelich, D-52425 Juelich, Germany
3Google Quantum AI, 80636 Munich, Germany

Find this paper interesting or want to discuss? Scite or leave a comment on SciRate.


Quantum phase estimation is a cornerstone in quantum algorithm design, allowing for the inference of eigenvalues of exponentially-large sparse matrices.The maximum rate at which these eigenvalues may be learned, –known as the Heisenberg limit–, is constrained by bounds on the circuit complexity required to simulate an arbitrary Hamiltonian. Single-control qubit variants of quantum phase estimation that do not require coherence between experiments have garnered interest in recent years due to lower circuit depth and minimal qubit overhead. In this work we show that these methods can achieve the Heisenberg limit, $also$ when one is unable to prepare eigenstates of the system. Given a quantum subroutine which provides samples of a `phase function' $g(k)=\sum_j A_j e^{i \phi_j k}$ with unknown eigenphases $\phi_j$ and overlaps $A_j$ at quantum cost $O(k)$, we show how to estimate the phases $\{\phi_j\}$ with (root-mean-square) error $\delta$ for total quantum cost $T=O(\delta^{-1})$. Our scheme combines the idea of Heisenberg-limited multi-order quantum phase estimation for a single eigenvalue phase [Higgins et al (2009) and Kimmel et al (2015)] with subroutines with so-called dense quantum phase estimation which uses classical processing via time-series analysis for the QEEP problem [Somma (2019)] or the matrix pencil method. For our algorithm which adaptively fixes the choice for $k$ in $g(k)$ we prove Heisenberg-limited scaling when we use the time-series/QEEP subroutine. We present numerical evidence that using the matrix pencil technique the algorithm can achieve Heisenberg-limited scaling as well.

A common task for a quantum computer is the estimation of the eigenphases of a unitary operator U, so-called quantum phase estimation or QPE. One may reduce the quantum overhead for QPE by turning it into a problem of classically processing the expectation values of $U^k$ as a time-series in $k$. However, it was not clear whether such a method could achieve known bounds on the cost of QPE — the so-called Heisenberg limit — when estimating multiple eigenphases. This work gives an algorithm with provable performance bounds that achieve the Heisenberg limit.

► BibTeX data

► References

[1] B. L. Higgins, D. W. Berry, S. D. Bartlett, M. W. Mitchell, H. M. Wiseman, and G. J. Pryde. Demonstrating Heisenberg-limited unambiguous phase estimation without adaptive measurements. New J. Phys., 11 (7): 073023, 2009. 10.1088/​1367-2630/​11/​7/​073023. URL https:/​/​arxiv.org/​abs/​0809.3308.

[2] Shelby Kimmel, Guang Hao Low, and Theodore J. Yoder. Robust calibration of a universal single-qubit gate-set via robust phase estimation. Phys. Rev. A, 92: 062315, 2015. 10.1103/​PhysRevA.92.062315. URL https:/​/​arxiv.org/​abs/​1502.02677.

[3] Rolando D. Somma. Quantum eigenvalue estimation via time series analysis. New J. Phys., 21: 123025, 2019. 10.1088/​1367-2630/​ab5c60. URL https:/​/​iopscience.iop.org/​article/​10.1088/​1367-2630/​ab5c60/​pdf.

[4] Pawel Wocjan and Shengyu Zhang. Several natural BQP-complete problems. ArXiv:quant-ph/​0606179, 2006. 10.48550/​arXiv.quant-ph/​0606179. URL https:/​/​arxiv.org/​abs/​quant-ph/​0606179.

[5] Peter W. Shor. Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM J. Sci. Stat. Comp., 26: 1484, 1997. 10.1137/​S0097539795293172. URL https:/​/​arxiv.org/​abs/​quant-ph/​9508027.

[6] Aram W. Harrow, Avinatan Hassidim, and Seth Lloyd. Quantum algorithm for solving linear systems of equations. Phys. Rev. Lett., 15 (103): 150502, 2009. 10.1103/​PhysRevLett.103.150502. URL https:/​/​arxiv.org/​abs/​0811.3171.

[7] James D. Whitfield, Jacob Biamonte, and Alán Aspuru-Guzik. Simulation of electronic structure Hamiltonians using quantum computers. Mol. Phys., 109: 735–750, 2011. 10.1080/​00268976.2011.552441. URL https:/​/​arxiv.org/​abs/​1001.3855.

[8] M.A. Nielsen and I.L. Chuang. Quantum Computation and Quantum Information. Cambridge Series on Information and the Natural Sciences. Cambridge University Press, 2000. ISBN 9780521635035. 10.1017/​CBO9780511976667. URL https:/​/​books.google.de/​books?id=65FqEKQOfP8C.

[9] R. Cleve, A. Ekert, C. Macchiavello, and M. Mosca. Quantum algorithms revisited. Proceedings of the Royal Society of London. Series A: Mathematical, Physical and Engineering Sciences, 454 (1969): 339–354, 1998. 10.1098/​rspa.1998.0164. URL https:/​/​royalsocietypublishing.org/​doi/​abs/​10.1098/​rspa.1998.0164.

[10] Vittorio Giovannetti, Seth Lloyd, and Lorenzo Maccone. Quantum metrology. Physical review letters, 96 (1): 010401, 2006. 10.1103/​PhysRevLett.96.010401. URL https:/​/​journals.aps.org/​prl/​abstract/​10.1103/​PhysRevLett.96.010401.

[11] Wim van Dam, G. Mauro D'Ariano, Artur Ekert, Chiara Macchiavello, and Michele Mosca. Optimal quantum circuits for general phase estimation. Phys. Rev. Lett., 98: 090501, Mar 2007. 10.1103/​PhysRevLett.98.090501. URL https:/​/​link.aps.org/​doi/​10.1103/​PhysRevLett.98.090501.

[12] Dominic W Berry, Brendon L Higgins, Stephen D Bartlett, Morgan W Mitchell, Geoff J Pryde, and Howard M Wiseman. How to perform the most accurate possible phase measurements. Physical Review A, 80 (5): 052114, 2009. 10.1103/​PhysRevA.80.052114.

[13] Robert B. Griffiths and Chi-Sheng Niu. Semiclassical Fourier transform for quantum computation. Physical Review Letters, 76 (17): 3228–3231, Apr 1996. ISSN 1079-7114. 10.1103/​physrevlett.76.3228. URL 10.1103/​PhysRevLett.76.3228.

[14] A. Yu. Kitaev. Quantum measurements and the Abelian stabilizer problem. ArXiv:quant-ph/​9511026, 1995. 10.48550/​arXiv.quant-ph/​9511026. URL https:/​/​arxiv.org/​abs/​quant-ph/​9511026.

[15] Dominic W. Berry, Graeme Ahokas, Richard Cleve, and Barry C. Sanders. Efficient quantum algorithms for simulating sparse Hamiltonians. Comm. Math. Phys., 270 (359), 2007. 10.1007/​s00220-006-0150-x. URL https:/​/​arxiv.org/​abs/​quant-ph/​0508139.

[16] Nathan Wiebe and Chris Granade. Efficient Bayesian phase estimation. Phys. Rev. Lett., 117: 010503, 2016. 10.1103/​PhysRevLett.117.010503. URL https:/​/​arxiv.org/​abs/​1508.00869.

[17] Krysta M. Svore, Matthew B. Hastings, and Michael Freedman. Faster phase estimation. Quant. Inf. Comp., 14 (3-4): 306–328, 2013. 10.48550/​arXiv.1304.0741. URL https:/​/​arxiv.org/​abs/​1304.0741.

[18] Ewout van den Berg. Efficient Bayesian phase estimation using mixed priors. ArXiv:2007.11629, 2020. 10.22331/​q-2021-06-07-469. URL https:/​/​arxiv.org/​abs/​2007.11629.

[19] Thomas E O'Brien, Brian Tarasinski, and Barbara M Terhal. Quantum phase estimation of multiple eigenvalues for small-scale (noisy) experiments. New J. Phys., 21: 023022, 2019. 10.1088/​1367-2630/​aafb8e. URL https:/​/​iopscience.iop.org/​article/​10.1088/​1367-2630/​aafb8e.

[20] David C. Rife and Robert R. Boorstyn. Single-tone parameter estimation from discrete-time observations. IEEE Trans. Inf. Th., 20 (5): 591–598, 1974. 10.1109/​TIT.1974.1055282. URL https:/​/​ieeexplore.ieee.org/​document/​1055282.

[21] Sirui Lu, Mari Carmen Bañuls, and J. Ignacio Cirac. Algorithms for quantum simulation at finite energies. PRX Quantum, 2: 020321, 2020. 10.1103/​PRXQuantum.2.020321. URL https:/​/​journals.aps.org/​prxquantum/​abstract/​10.1103/​PRXQuantum.2.020321.

[22] T.E. O'Brien, S. Polla, N.C. Rubin, W.J. Huggins, S. McArdle, S. Boixo, J.R. McClean, and R. Babbush. Error mitigation via verified phase estimation. ArXiv:2010.02538, 2020. 10.1103/​PRXQuantum.2.020317. URL https:/​/​arxiv.org/​abs/​2010.02538.

[23] Alessandro Roggero. Spectral density estimation with the Gaussian integral transform. ArXiv:2004.04889, 2020. 10.1103/​PhysRevA.102.022409. URL https:/​/​arxiv.org/​abs/​2004.04889.

[24] András Gilyén, Yuan Su, Guang Hao Low, and Nathan Wiebe. Quantum singular value transformation and beyond: Exponential improvements for quantum matrix arithmetics. In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, STOC 2019, page 193–204, New York, NY, USA, 2019. Association for Computing Machinery. ISBN 9781450367059. 10.1145/​3313276.3316366. URL 10.1145/​3313276.3316366.

[25] O. Regev. A subexponential time algorithm for the dihedral hidden subgroup problem with polynomial space. ArXiv:quant-ph/​0406151, 2004. 10.48550/​arXiv.quant-ph/​0406151. URL https:/​/​arxiv.org/​abs/​quant-ph/​0406151.

[26] Lin Lin and Yu Tong. Heisenberg-limited ground state energy estimation for early fault-tolerant quantum computers. ArXiv:2102.11340, 2021. 10.1103/​PRXQuantum.3.010318. URL https:/​/​arxiv.org/​abs/​2102.11340.

[27] Valentin Gebhart, Augusto Smerzi, and Luca Pezzè. Heisenberg-limited bayesian multiphase estimation algorithm. ArXiv:2010.09075, 2020. 10.1103/​PhysRevApplied.16.014035. URL https:/​/​arxiv.org/​abs/​2010.09075.

[28] Andrew M. Childs, Yuan Su, Minh C. Tran, Nathan Wiebe, and Shuchen Zhu. Theory of trotter error with commutator scaling. Phys. Rev. X, 11: 011020, Feb 2021. 10.1103/​PhysRevX.11.011020. URL https:/​/​link.aps.org/​doi/​10.1103/​PhysRevX.11.011020.

[29] Harald Cramér. Mathematical Methods of Statistics. Princeton University Press, 1946. ISBN 0691080046. 10.1515/​9781400883868. URL https:/​/​archive.org/​details/​in.ernet.dli.2015.223699.

[30] Calyampudi Radakrishna Rao. Information and the accuracy attainable in the estimation of statistical parameters. Bull. Calcutta Math. Soc., 37: 81–89, 1945. 10.1007/​978-1-4612-0919-5_16. URL https:/​/​link.springer.com/​chapter/​10.1007/​978-1-4612-0919-5_16.

[31] Yingbo Hua and Tapan Sarkar. Matrix pencil method for estimating parameters of exponentially damped/​undamped sinusoids in noise. IEEE Transactions on Acoustic Speech and Signal Processing, 38 (5), 1990. 10.1109/​29.56027. URL https:/​/​ieeexplore.ieee.org/​document/​56027.

[32] Ankur Moitra. Super-resolution, extremal functions and the condition number of Vandermonde matrices. In Proceedings of the Forty-Seventh Annual ACM Symposium on Theory of Computing, STOC '15, page 821–830, New York, NY, USA, 2015. Association for Computing Machinery. ISBN 9781450335362. 10.1145/​2746539.2746561. URL 10.1145/​2746539.2746561.

[33] Lin Lin and Yu Tong. Near-optimal ground state preparation. Quantum, 4: 372, December 2020. ISSN 2521-327X. 10.22331/​q-2020-12-14-372. URL 10.22331/​q-2020-12-14-372.

Cited by

[1] Casper Gyurik, Chris Cade, and Vedran Dunjko, "Towards quantum advantage via topological data analysis", arXiv:2005.02607, Quantum 6, 855 (2022).

[2] Kianna Wan, Mario Berta, and Earl T. Campbell, "Randomized Quantum Algorithm for Statistical Phase Estimation", Physical Review Letters 129 3, 030503 (2022).

[3] Andrés Gómez and Javier Mas, "Hermitian matrix definiteness from quantum phase estimation", Quantum Information Processing 21 6, 213 (2022).

The above citations are from Crossref's cited-by service (last updated successfully 2022-11-30 09:56:38) and SAO/NASA ADS (last updated successfully 2022-11-30 09:56:39). The list may be incomplete as not all publishers provide suitable and complete citation data.