Fair sampling of weighted ground state configurations in quantum annealing

Several problems in science and engineering, such as finding ground states of frustrated spin systems or an engineering network’s reliability, require finding all the solutions of an optimization problem. Recently, quantum annealing, which solves the optimization problem by finding the ground states of a classical Hamiltonian, has become a popular tool. However, the commonly used form of quantum annealing often exponentially (in the number of bits) or completely suppresses some ground states, thereby rendering it an unreliable method to find all the desired solutions. We propose a driver Hamiltonian for quantum annealing that results in a final wavefunction which is an equal superposition of all the ground states of the final Hamiltonian, with these ground states encoding the solutions of the optimization problem. We extend our proposal even to cases where the ground states need to be weighted unequally, a requirement in several engineering problems. We show that implementing a single annealing experiment with our driver Hamiltonian is only polynomial slower than implementing common driver Hamiltonians. Finally, we construct quantum circuits to implement the annealing on a quantum computer.