On low-depth algorithms for quantum phase estimation

Hongkang Ni1, Haoya Li2, and Lexing Ying2,1

1Institute for Computational and Mathematical Engineering, Stanford University, Stanford, CA 94305
2Department of Mathematics, Stanford University, Stanford, CA 94305

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

Abstract

Quantum phase estimation is one of the critical building blocks of quantum computing. For early fault-tolerant quantum devices, it is desirable for a quantum phase estimation algorithm to (1) use a minimal number of ancilla qubits, (2) allow for inexact initial states with a significant mismatch, (3) achieve the Heisenberg limit for the total resource used, and (4) have a diminishing prefactor for the maximum circuit length when the overlap between the initial state and the target state approaches one. In this paper, we prove that an existing algorithm from quantum metrology can achieve the first three requirements. As a second contribution, we propose a modified version of the algorithm that also meets the fourth requirement, which makes it particularly attractive for early fault-tolerant quantum devices.

► BibTeX data

► References

[1] D. Aharonov and T. Naveh. Quantum NP-a survey. arXiv preprint quant-ph/​0210077, 2002. https:/​/​doi.org/​10.48550/​arXiv.quant-ph/​0210077.
https:/​/​doi.org/​10.48550/​arXiv.quant-ph/​0210077
arXiv:quant-ph/0210077

[2] F. Belliardo and V. Giovannetti. Achieving Heisenberg scaling with maximally entangled states: An analytic upper bound for the attainable root-mean-square error. Physical Review A, 102 (4): 042613, 2020. https:/​/​doi.org/​10.1103/​PhysRevA.102.042613.
https:/​/​doi.org/​10.1103/​PhysRevA.102.042613

[3] D. W. Berry, A. M. Childs, R. Cleve, R. Kothari, and R. D. Somma. Simulating Hamiltonian dynamics with a truncated Taylor series. Physical review letters, 114 (9): 090502, 2015. https:/​/​doi.org/​10.1103/​PhysRevLett.114.090502.
https:/​/​doi.org/​10.1103/​PhysRevLett.114.090502

[4] 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. https:/​/​doi.org/​10.1098/​rspa.1998.0164.
https:/​/​doi.org/​10.1098/​rspa.1998.0164

[5] Z. Ding and L. Lin. Even shorter quantum circuit for phase estimation on early fault-tolerant quantum computers with applications to ground-state energy estimation. PRX Quantum, 4 (2): 020331, 2023a. https:/​/​doi.org/​10.1103/​PRXQuantum.4.020331.
https:/​/​doi.org/​10.1103/​PRXQuantum.4.020331

[6] Z. Ding and L. Lin. Simultaneous estimation of multiple eigenvalues with short-depth quantum circuit on early fault-tolerant quantum computers. Quantum, 7: 1136, 2023b. https:/​/​doi.org/​10.22331/​q-2023-10-11-1136.
https:/​/​doi.org/​10.22331/​q-2023-10-11-1136

[7] Y. Dong, L. Lin, and Y. Tong. Ground-state preparation and energy estimation on early fault-tolerant quantum computers via quantum eigenvalue transformation of unitary matrices. PRX Quantum, 3 (4): 040305, 2022. https:/​/​doi.org/​10.1103/​PRXQuantum.3.040305.
https:/​/​doi.org/​10.1103/​PRXQuantum.3.040305

[8] V. Giovannetti, S. Lloyd, and L. Maccone. Quantum metrology. Physical review letters, 96 (1): 010401, 2006. https:/​/​doi.org/​10.1103/​PhysRevLett.96.010401.
https:/​/​doi.org/​10.1103/​PhysRevLett.96.010401

[9] B. L. Higgins, D. W. Berry, S. D. Bartlett, H. M. Wiseman, and G. J. Pryde. Entanglement-free Heisenberg-limited phase estimation. Nature, 450 (7168): 393–396, 2007. https:/​/​doi.org/​10.1038/​nature06257.
https:/​/​doi.org/​10.1038/​nature06257

[10] H.-Y. Huang, Y. Tong, D. Fang, and Y. Su. Learning many-body hamiltonians with heisenberg-limited scaling. Physical Review Letters, 130 (20): 200403, 2023. https:/​/​doi.org/​10.1103/​PhysRevLett.130.200403.
https:/​/​doi.org/​10.1103/​PhysRevLett.130.200403

[11] J. Kempe, A. Kitaev, and O. Regev. The complexity of the local Hamiltonian problem. Siam journal on computing, 35 (5): 1070–1097, 2006. https:/​/​doi.org/​10.1137/​S0097539704445226.
https:/​/​doi.org/​10.1137/​S0097539704445226

[12] S. Kimmel, G. H. Low, and T. J. Yoder. Robust calibration of a universal single-qubit gate set via robust phase estimation. Physical Review A, 92 (6): 062315, 2015. https:/​/​doi.org/​10.1103/​PhysRevA.92.062315.
https:/​/​doi.org/​10.1103/​PhysRevA.92.062315

[13] A. Y. Kitaev. Quantum measurements and the abelian stabilizer problem. arXiv preprint quant-ph/​9511026, 1995. https:/​/​doi.org/​10.48550/​arXiv.quant-ph/​9511026.
https:/​/​doi.org/​10.48550/​arXiv.quant-ph/​9511026
arXiv:quant-ph/9511026

[14] A. Y. Kitaev, A. Shen, M. N. Vyalyi, and M. N. Vyalyi. Classical and quantum computation. American Mathematical Soc., 2002. http:/​/​dx.doi.org/​10.1090/​gsm/​047.
https:/​/​doi.org/​10.1090/​gsm/​047

[15] E. Knill, G. Ortiz, and R. D. Somma. Optimal quantum measurements of expectation values of observables. Physical Review A, 75 (1): 012328, 2007. https:/​/​doi.org/​10.1103/​PhysRevA.75.012328.
https:/​/​doi.org/​10.1103/​PhysRevA.75.012328

[16] H. Li, H. Ni, and L. Ying. On low-depth quantum algorithms for robust multiple-phase estimation. arXiv preprint arXiv:2303.08099, 2023. https:/​/​doi.org/​10.48550/​arXiv.2303.08099.
https:/​/​doi.org/​10.48550/​arXiv.2303.08099
arXiv:2303.08099

[17] L. Lin and Y. Tong. Near-optimal ground state preparation. Quantum, 4: 372, 2020. https:/​/​doi.org/​10.22331/​q-2020-12-14-372.
https:/​/​doi.org/​10.22331/​q-2020-12-14-372

[18] L. Lin and Y. Tong. Heisenberg-limited ground-state energy estimation for early fault-tolerant quantum computers. PRX Quantum, 3 (1): 010318, 2022. https:/​/​doi.org/​10.1103/​PRXQuantum.3.010318.
https:/​/​doi.org/​10.1103/​PRXQuantum.3.010318

[19] A. Lumino, E. Polino, A. S. Rab, G. Milani, N. Spagnolo, N. Wiebe, and F. Sciarrino. Experimental phase estimation enhanced by machine learning. Physical Review Applied, 10 (4): 044033, 2018. https:/​/​doi.org/​10.1103/​PhysRevApplied.10.044033.
https:/​/​doi.org/​10.1103/​PhysRevApplied.10.044033

[20] M. A. Nielsen and I. L. Chuang. Quantum Computation and Quantum Information. Cambridge University Press, 2000. http:/​/​dx.doi.org/​10.1017/​CBO9780511976667.
https:/​/​doi.org/​10.1017/​CBO9780511976667

[21] T. E. O’Brien, B. Tarasinski, and B. M. Terhal. Quantum phase estimation of multiple eigenvalues for small-scale (noisy) experiments. New Journal of Physics, 21 (2): 023022, 2019. 10.1088/​1367-2630/​aafb8e.
https:/​/​doi.org/​10.1088/​1367-2630/​aafb8e

[22] D. Poulin and P. Wocjan. Sampling from the thermal quantum gibbs state and evaluating partition functions with a quantum computer. Physical review letters, 103 (22): 220502, 2009. https:/​/​doi.org/​10.1103/​PhysRevLett.103.220502.
https:/​/​doi.org/​10.1103/​PhysRevLett.103.220502

[23] K. Rudinger, S. Kimmel, D. Lobser, and P. Maunz. Experimental demonstration of a cheap and accurate phase estimation. Physical review letters, 118 (19): 190502, 2017. https:/​/​doi.org/​10.1103/​PhysRevLett.118.190502.
https:/​/​doi.org/​10.1103/​PhysRevLett.118.190502

[24] A. E. Russo, K. M. Rudinger, B. C. Morrison, and A. D. Baczewski. Evaluating energy differences on a quantum computer with robust phase estimation. Physical review letters, 126 (21): 210501, 2021. https:/​/​doi.org/​10.1103/​PhysRevLett.126.210501.
https:/​/​doi.org/​10.1103/​PhysRevLett.126.210501

[25] Y. Tong. A tight query complexity lower bound for phase estimation under circuit depth constraint, 2021. URL https:/​/​math.berkeley.edu/​ yu_tong/​lower_bound_low_depth_phase_est.pdf.
https:/​/​math.berkeley.edu/​~yu_tong/​lower_bound_low_depth_phase_est.pdf

[26] K. Wan, M. Berta, and E. T. Campbell. Randomized quantum algorithm for statistical phase estimation. Physical Review Letters, 129 (3): 030503, 2022. https:/​/​doi.org/​10.1103/​PhysRevLett.129.030503.
https:/​/​doi.org/​10.1103/​PhysRevLett.129.030503

[27] G. Wang, D. Stilck-França, R. Zhang, S. Zhu, and P. D. Johnson. Quantum algorithm for ground state energy estimation using circuit depth with exponentially improved dependence on precision. arXiv preprint arXiv:2209.06811, 2022. https:/​/​doi.org/​10.48550/​arXiv.2209.06811.
https:/​/​doi.org/​10.48550/​arXiv.2209.06811
arXiv:2209.06811

[28] R. Zhang, G. Wang, and P. Johnson. Computing ground state properties with early fault-tolerant quantum computers. Quantum, 6: 761, 2022. https:/​/​doi.org/​10.22331/​q-2022-07-11-761.
https:/​/​doi.org/​10.22331/​q-2022-07-11-761

[29] S. Zhou, M. Zhang, J. Preskill, and L. Jiang. Achieving the Heisenberg limit in quantum metrology using quantum error correction. Nature communications, 9 (1): 78, 2018. https:/​/​doi.org/​10.1038/​s41467-017-02510-3.
https:/​/​doi.org/​10.1038/​s41467-017-02510-3

[30] M. Zwierz, C. A. Pérez-Delgado, and P. Kok. General optimality of the Heisenberg limit for quantum metrology. Physical review letters, 105 (18): 180402, 2010. https:/​/​doi.org/​10.1103/​PhysRevLett.105.180402.
https:/​/​doi.org/​10.1103/​PhysRevLett.105.180402

Cited by

[1] Qiyao Liang, Yiqing Zhou, Archismita Dalal, and Peter Johnson, "Modeling the performance of early fault-tolerant quantum algorithms", Physical Review Research 6 2, 023118 (2024).

[2] Yongdan Yang, Ying Li, Xiaosi Xu, and Xiao Yuan, "Resource-efficient quantum-classical hybrid algorithm for energy gap evaluation", Physical Review A 109 5, 052416 (2024).

[3] Hongkang Ni, Haoya Li, and Lexing Ying, "Quantum Hamiltonian Learning for the Fermi-Hubbard Model", Acta Applicandae Mathematicae 191 1, 2 (2024).

[4] Haoya Li, Hongkang Ni, and Lexing Ying, "Adaptive low-depth quantum algorithms for robust multiple-phase estimation", Physical Review A 108 6, 062408 (2023).

[5] Zhiyan Ding and Lin Lin, "Even Shorter Quantum Circuit for Phase Estimation on Early Fault-Tolerant Quantum Computers with Applications to Ground-State Energy Estimation", PRX Quantum 4 2, 020331 (2023).

[6] Amara Katabarwa, Katerina Gratsea, Athena Caesura, and Peter D. Johnson, "Early Fault-Tolerant Quantum Computing", arXiv:2311.14814, (2023).

[7] Guoming Wang, Daniel Stilck França, Ruizhe Zhang, Shuchen Zhu, and Peter D. Johnson, "Quantum algorithm for ground state energy estimation using circuit depth with exponentially improved dependence on precision", Quantum 7, 1167 (2023).

[8] Haoya Li, Yu Tong, Hongkang Ni, Tuvia Gefen, and Lexing Ying, "Heisenberg-limited Hamiltonian learning for interacting bosons", arXiv:2307.04690, (2023).

[9] Akash Kundu, "Reinforcement learning-assisted quantum architecture search for variational quantum algorithms", arXiv:2402.13754, (2024).

[10] Zhiyan Ding and Lin Lin, "Simultaneous estimation of multiple eigenvalues with short-depth quantum circuit on early fault-tolerant quantum computers", Quantum 7, 1136 (2023).

[11] Arjun Mirani and Patrick Hayden, "Learning interacting fermionic Hamiltonians at the Heisenberg limit", arXiv:2403.00069, (2024).

[12] Changhao Yi, Cunlu Zhou, and Jun Takahashi, "Quantum Phase Estimation by Compressed Sensing", arXiv:2306.07008, (2023).

[13] Jacob S. Nelson and Andrew D. Baczewski, "An assessment of quantum phase estimation protocols for early fault-tolerant quantum computers", arXiv:2403.00077, (2024).

The above citations are from Crossref's cited-by service (last updated successfully 2024-05-25 02:07:46) and SAO/NASA ADS (last updated successfully 2024-05-25 02:07:47). The list may be incomplete as not all publishers provide suitable and complete citation data.