Quantum Approximate Optimization with Sparse Mixers

Abstract

Quals talk:

Recent advancements in noisy intermediate-scale quantum (NISQ) computers have motivated a desire for algorithms that can operate without fully coherent qubits or large circuit depths. The quantum approximate optimization algorithm (QAOA) is a tunable-depth variational approximation algorithm for combinatorial optimization problems that generated much excitement as a possible candidate for running on such near-term NISQ machines. However, the development of classical algorithms that match the QAOA's performance for MAX- 3LIN2, coupled with analysis demonstrating provable obstructions for shallow-depth instances of the QAOA, has limited its scope. These limitations stem from the QAOA's Transverse-Field mixer, which only traverses candidate solutions in a fixed neighborhood characterized by circuit depth. This talk proposes a new class of QAOA mixers that leverages recent advancements in sparse Hamiltonian time-evolution and allows for the encoding of global problem interactions. These sparse mixers have the potential to improve the shallow depth performance of the QAOA and circumvent obstructions related to the local structure of the QAOA.

Please join meeting in Miner Hall #112.