$O(N^3)$ Measurement Cost for Variational Quantum Eigensolver on Molecular Hamiltonians
Top Cited Papers
Open Access
- 4 November 2020
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Quantum Engineering
- Vol. 1, 1-24
- https://doi.org/10.1109/tqe.2020.3035814
Abstract
Variational quantum eigensolver (VQE) is a promising algorithm for near-term quantum machines. It can be used to estimate the ground state energy of a molecule by performing separate measurements of O(N 4 ) terms. This quartic scaling appears to be a significant obstacle to practical applications. However, we note that it empirically reduces to O(N 3 ) when we partition the terms into linear-sized commuting families that can be measured simultaneously. We confirm these empirical observations by studying the MIN-COMMUTING-PARTITION problem at the level of the fermionic Hamiltonian and its encoding into qubits. Moreover, we provide a fast, precomputable procedure for creating linearly sized commuting partitions by solving a round-robin scheduling problem via flow networks. In addition, we demonstrate how to construct the quantum circuits necessary for simultaneous measurement, and we discuss the statistical implication of simultaneous measurement. Our results are experimentally validated by a ground state estimation of deuteron with low shot budget on a 20-qubit IBM machine.Funding Information
- National Science Foundation (CCF-1730449/1730082)
- STAQ (Phy-1818914)
- U.S. Department of Energy (DE-AC02-06CH11357)
This publication has 66 references indexed in Scilit:
- Quantum Computing for Computer Architects, Second EditionSynthesis Lectures on Computer Architecture, 2011
- Simulation of electronic structure Hamiltonians using quantum computersMolecular Physics, 2011
- Fermionic Quantum ComputationAnnals of Physics, 2002
- Quantum Computation and Quantum InformationAmerican Journal of Physics, 2002
- A quantitative study of the scaling properties of the Hartree–Fock methodThe Journal of Chemical Physics, 1995
- Approximating maximum independent sets by excluding subgraphsBIT Numerical Mathematics, 1992
- Comparison of coupled-cluster methods which include the effects of connected triple excitationsThe Journal of Chemical Physics, 1990
- Algorithm 457: finding all cliques of an undirected graphCommunications of the ACM, 1973
- The Activated Complex in Chemical ReactionsThe Journal of Chemical Physics, 1935
- ber das Paulische quivalenzverbotThe European Physical Journal A, 1928