## Project Details

### Description

Quantum-enhanced population transfer (QEPT) has been proposed as a powerful quantum heuristic for optimization [1]. One can first attempt optimization via a classical algorithm (e.g. parallel tempering) until a local minimum is found, then use that as the starting state for QEPT. A measurement can then give a state with similar energy that is not at a local minimum, and can therefore be used as a new starting value for the classical optimization.

However, little effort has been devoted to improving the efficiency of Hamiltonian simulation routines required for the implementation of QEPT. We propose to compile, analyze, and optimize the resources required to implement QEPT on the first generation of fault-tolerant quantum computers.

We will focus on the application of QEPT to three optimization problems that are known to be extremely challenging classically: (i) the “p-spin” problem, (ii) integer partitioning [2], and (iii) the low autocorrelation binary sequences problem [3]. We will investigate both conventional Trotter methods and more sophisticated linear combinations of unitary (LCU) methods of simulation to determine the best approach for each problem.

PI Berry developed many of the key techniques in quantum algorithms for accomplishing Hamiltonian simulations with low overhead [4–8]. PI Berry and Google team member Ryan Babbush have been very successful at reducing the gate counts for this problem for the case of quantum chemistry [9], reducing the complexity by about a factor of a million from prior work. The goal of this one year project is to bring similar techniques to bear on QEPT, and to compile the resulting algorithms all the way to fault-tolerant surface code gates in order

to predict the circumstances under which an error-corrected quantum advantage would emerge given realistic assumptions.

However, little effort has been devoted to improving the efficiency of Hamiltonian simulation routines required for the implementation of QEPT. We propose to compile, analyze, and optimize the resources required to implement QEPT on the first generation of fault-tolerant quantum computers.

We will focus on the application of QEPT to three optimization problems that are known to be extremely challenging classically: (i) the “p-spin” problem, (ii) integer partitioning [2], and (iii) the low autocorrelation binary sequences problem [3]. We will investigate both conventional Trotter methods and more sophisticated linear combinations of unitary (LCU) methods of simulation to determine the best approach for each problem.

PI Berry developed many of the key techniques in quantum algorithms for accomplishing Hamiltonian simulations with low overhead [4–8]. PI Berry and Google team member Ryan Babbush have been very successful at reducing the gate counts for this problem for the case of quantum chemistry [9], reducing the complexity by about a factor of a million from prior work. The goal of this one year project is to bring similar techniques to bear on QEPT, and to compile the resulting algorithms all the way to fault-tolerant surface code gates in order

to predict the circumstances under which an error-corrected quantum advantage would emerge given realistic assumptions.

Acronym | OOA_Google |
---|---|

Status | Finished |

Effective start/end date | 1/11/18 → 31/10/19 |