Quantum chemistry on near-term quantum computers: the measurement problem

Quantum chemistry calculations including computing the ground state energies of complex molecules are touted as a promising application of near-term quantum computers. While numerous small-scale proof-of-concept calculations have been performed for small molecules, whether near-term quantum algorithms will offer any useful advantage over existing classical computers remains an intensely-debated question.

The variational quantum eigensolver is a leading candidate for near-term quantum computers. This algorithm uses a hybrid quantum-classical feedback loop to optimise the parameters of the quantum gates and minimise the required circuit depth. Each iteration of this algorithm requires estimating the energy of the trial solution, which requires O(1/ε^2) measurements to achieve an accuracy of ε. This becomes a severe bottleneck as the problem size is increased. 

For example, Google's recent paper preparing the Hartree-Fock wavefunction required 250,000 measurements to estimate each observable to sufficient accuracy, translating to a few seconds to perform a single iteration of the algorithm with N=12 qubits. They employed clever tricks to obtain the N^2 one-particle reduced density matrix elements required to compute the energy using only N+1 measurements. When electronic correlations are taken into account, N^4 two-particle reduced density matrix elements are needed to estimate energies. This poor scaling must be improved for the variational quantum eigensolver to have any practical applications.

Interestingly, larger error-corrected quantum computers may not solve this problem: Pessimists estimate that millions of qubits and years of runtime will be required to run error-corrected algorithms such as quantum phase estimation on useful problem sizes.

One approach towards tackling this problem is to use more efficient problem encodings. The most-commonly employed second quantization approach uses N qubits to encode N electron orbitals, and can represent states containing up to N electrons. However, typically the number of orbitals needs to be considerably larger than the number of electrons K in order to achieve convergence to accurate ground state energies. Alternatively, using a first quantization encoding can encode the quantum state using K log N qubits. Estimating the energy then requires measuring elements of a Hamiltonian with ~(KN)^2 nonzero elements. However, one needs to be careful to ensure that the required antisymmetry of the trial wavefunction is preserved. Nevertheless, this approach may be superior for achieving chemical accuracy when a large number of basis states is required. Further discussion on this point can be found in this paper.

Some other useful references I read today on this topic:

This preprint estimates runtimes for applying the quantum phase estimation algorithm to compute energies of catalysts.

This preprint proposes a Bayesian approach to estimating energies with runtime interpolating between the 1/ε^2 of the variational quantum eigensolver and the 1/ε of quantum phase estimation, which trades longer circuit depths for fewer required measurements.

This preprint discusses the measurement problem further.