Marginals optimization procedure: algorithmically extending the capability of near-term quantum computers

We are entering an era in which quantum computers can perform contrived tasks that classical computers cannot. However, these devices are far from being able to break RSA encryption or to simulate complex chemical reactions. A big question driving the field is: can we find a practical use for these near-term intermediate scale quantum (NISQ) devices? A promising approach is to explore “variational quantum algorithms”, which treat a quantum circuit much like an artificial neural network to solve optimization problems approximately. These optimization problems include estimating the ground state energy of a small molecule and understanding the structure of social networks.

Variational quantum algorithms have yet to outperform state-of-the-art classical optimization techniques. While improving quantum devices is necessary to achieve this so-called “quantum advantage”, improving quantum algorithms also brings us closer towards this goal. Based on a simple observation about the role of the quantum computer in these algorithms, we have developed a technique which algorithmically extends the depth of a quantum computer. We describe the marginals optimization procedure for improving variational quantum algorithms and demonstrate its performance in simulations and small experiments.