IQI Weekly Seminar

Abstract: Quantum simulation and optimization are two of the most promising applications of near-term quantum computers. In fact, there are already many experiments where analog simulations of quantum models are implemented to probe interesting physical phenomena. Some experiments have also begun testing performance of quantum algorithms for optimization.In this two-part talk, I will first describe our study of the resource required to simulate a quantum Hamiltonian by another whose underlying interaction graph is simpler. We show a surprising result that unlike the classical setting, reducing the graph degree to a constant is impossible in general unless the interaction energy diverges with system size n. Instead, we develop a new construction where such degree-reduction becomes possible using O(poly(n)) interaction energy, which is exponentially better than what was known previously. In the second part, I will discuss our recent insights into the performance and mechanism of a general-purpose Quantum Approximate Optimization Algorithm (QAOA). We develop a parameter-optimization procedure for the QAOA that is exponentially more efficient than standard strategies and reveal a mechanism of the algorithm to exploit non-adiabatic operations. We also analyze the typical-case performance of the QAOA on the Sherrington-Kirkpatrick spin glass problem and find that it can outperform the classical semi-definite programming algorithm. Implementations in experiments are also discussed.