O(N^3) Measurement Cost for Variational Quantum Eigensolver on Molecular Hamiltonians

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 […]

Quantum Approximate Optimization With Parallelizable Gates

The quantum approximate optimization algorithm (QAOA) has been introduced as a heuristic digital quantum computing scheme to find approximate solutions of combinatorial optimization problems. We present a scheme to parallelize this approach for arbitrary all-to-all connected problem graphs in a layout of quantum bits (qubits) with nearest-neighbor interactions. The protocol consists of single qubit operations […]