Heisenberg-limited Quantum Phase Estimation Of Multiple Eigenvalues With Few Control Qubits

Republished By Plato

Followers: 0

Alicja Dutkiewicz¹, Barbara M. Terhal², and Thomas E. O’Brien^1,3

¹Instituut-Lorentz, Universiteit Leiden, 2300 RA Leiden, The Netherlands
²QuTech, 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
³Google Quantum AI, 80636 Munich, Germany

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

Abstract

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.

Featured image: A Heisenberg-limited scheme for detecting multiple phases $phi_j$. First, an initial estimate of $phi_jin[0,2pi]$ is made from a time series ${langle Urangle, langle U^2rangle ldots}$. Then, an estimate is made of $kphi_j$ for some $k>1$, using ${langle U^{k}rangle, langle U^{2k}rangle,ldots }$. This generates a more-accurate estimate of $phi_j$ (smaller error bars), but modulo $2pi/k$. Data from the first estimation is used to stabilize this estimate and remove unwanted aliases (dashed lines). This is repeated for ever-larger values of $k$ to achieve the Heisenberg limit. The multiplier $k$ is chosen based on the previous estimates to enable unambiguous estimation.

Popular summary

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

@article{Dutkiewicz2022heisenberglimited, doi = {10.22331/q-2022-10-06-830}, url = {https://doi.org/10.22331/q-2022-10-06-830}, title = {Heisenberg-limited quantum phase estimation of multiple eigenvalues with few control qubits}, author = {Dutkiewicz, Alicja and Terhal, Barbara M. and O’Brien, Thomas E.}, journal = {{Quantum}}, issn = {2521-327X}, publisher = {{Verein zur F{“{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}}, volume = {6}, pages = {830}, month = oct, year = {2022} }

► 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.
https://doi.org/10.1088/1367-2630/11/7/073023
arXiv: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.
https://doi.org/10.1103/PhysRevA.92.062315
arXiv: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.
https://doi.org/10.1088/1367-2630/ab5c60

[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.
https://doi.org/10.48550/arXiv.quant-ph/0606179
arXiv: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.
https://doi.org/10.1137/S0097539795293172
arXiv: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.
https://doi.org/10.1103/PhysRevLett.103.150502
arXiv: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.
https://doi.org/10.1080/00268976.2011.552441
arXiv: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.
https://doi.org/10.1017/CBO9780511976667
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.
https://doi.org/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.
https://doi.org/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.
https://doi.org/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.
https://doi.org/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.
https://doi.org/10.1103/physrevlett.76.3228
http://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.
https://doi.org/10.48550/arXiv.quant-ph/9511026
arXiv: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.
https://doi.org/10.1007/s00220-006-0150-x
arXiv: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.
https://doi.org/10.1103/PhysRevLett.117.010503
arXiv: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.
https://doi.org/10.48550/arXiv.1304.0741
arXiv: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.
https://doi.org/10.22331/q-2021-06-07-469
arXiv: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.
https://doi.org/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.
https://doi.org/10.1109/TIT.1974.1055282
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.
https://doi.org/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.
https://doi.org/10.1103/PRXQuantum.2.020317
arXiv: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.
https://doi.org/10.1103/PhysRevA.102.022409
arXiv: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.
https://doi.org/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.
https://doi.org/10.48550/arXiv.quant-ph/0406151
arXiv: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.
https://doi.org/10.1103/PRXQuantum.3.010318
arXiv: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.
https://doi.org/10.1103/PhysRevApplied.16.014035
arXiv: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.
https://doi.org/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.
https://doi.org/10.1515/9781400883868
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.
https://doi.org/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.
https://doi.org/10.1109/29.56027
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.
https://doi.org/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.
https://doi.org/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.

[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 SAO/NASA ADS (last updated successfully 2022-10-07 02:35:12). The list may be incomplete as not all publishers provide suitable and complete citation data.

Could not fetch Crossref cited-by data during last attempt 2022-10-07 02:35:10: Could not fetch cited-by data for 10.22331/q-2022-10-06-830 from Crossref. This is normal if the DOI was registered recently.

This Paper is published in Quantum under the Creative Commons Attribution 4.0 International (CC BY 4.0) license. Copyright remains with the original copyright holders such as the authors or their institutions.

Time Stamp: October 6, 2022October 7, 2022

Time Stamp: Feb 29, 2024

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

Republished By Plato

Abstract

Popular summary

► BibTeX data

► References

Cited by

More from Quantum Journal

Symmetry enhanced variational quantum spin eigensolver

High-accuracy Hamiltonian learning via delocalized quantum state evolutions

Finite Rate QLDPC-GKP Coding Scheme that Surpasses the CSS Hamming Bound

Structural risk minimization for quantum linear classifiers

Unifying different notions of quantum incompatibility into a strict hierarchy of resource theories of communication

Adaptive syndrome measurements for Shor-style error correction

Correlations in typicality and an affirmative solution to the exact catalytic entropy conjecture

Rapid quantum approaches for combinatorial optimisation inspired by optimal state-transfer

Limitations of the Macaulay matrix approach for using the HHL algorithm to solve multivariate polynomial systems

Discovering optimal fermion-qubit mappings through algorithmic enumeration

Bicolor loop models and their long range entanglement

About Us

Vertical Search & Ai

Platform

Stay Connected

Account