O(N3) Measurement Cost for Variational Quantum Eigensolver on Molecular Hamiltonians

Pranav Gokhale, Olivia Angiuli, Yongshan Ding, Kaiwen Gui, Teague Tomesh, Martin Suchara, Margaret Martonosi, Frederic T. Chong

Research output: Contribution to journalArticlepeer-review

45 Scopus citations


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(N4) terms. This quartic scaling appears to be a significant obstacle to practical applications. However, we note that it empirically reduces to O(N3) 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.

Original languageEnglish (US)
JournalIEEE Transactions on Quantum Engineering
StatePublished - 2020

All Science Journal Classification (ASJC) codes

  • Software
  • Computer Science (miscellaneous)
  • Condensed Matter Physics
  • Engineering (miscellaneous)
  • Mechanical Engineering
  • Computer Science Applications
  • Electrical and Electronic Engineering


  • Quantum computing, variational quantum eigensolver (VQE)


Dive into the research topics of 'O(N3) Measurement Cost for Variational Quantum Eigensolver on Molecular Hamiltonians'. Together they form a unique fingerprint.

Cite this