Speaker
Description
I will present our recent progress in designing algorithms that depend on quantum-mechanical resources – superposition, interference, and entanglement – for the solution of computational problems. Combined, these algorithms cover a large variety of challenging computational tasks spanning combinatorial optimization, machine learning, and model counting. First, I will discuss an algorithm for combinatorial optimization based on stabilizer states and Clifford quantum circuits. The algorithm iteratively builds a quantum circuit that maps an initial easy-to-prepare state to approximate solutions of optimization problems. Since Clifford circuits can be efficiently simulated classically, the result is a classical quantum-inspired algorithm. We benchmark this algorithm on synthetic instances of two NP-hard problems, namely MAXCUT and the Sherrington-Kirkpatrick model, and observe performance competitive with established algorithms for the solution of these problems. Next, I will present a quantum machine learning (QML) model based on matchgate quantum circuits. This restricted class of quantum circuits is efficiently simulable classically through a mapping to free Majorana fermions. We apply our matchgate QML model to commonly studied datasets, including MNIST and UCI ML Breast Cancer Wisconsin (Diagnostic), and obtain better classification accuracy than corresponding unrestricted QML models. Finally, I will outline ongoing work on algorithms for hard problems in #P, the computational complexity class encompassing counting problems. These examples demonstrate that (a) using restricted quantum resources as an algorithmic design principle of classical algorithms may lead to significant advantages even without a quantum computer, and (b) the frontier of near-term quantum advantage may lie further in the future than anticipated by some.
Keyword-1 | Quantum computing |
---|---|
Keyword-2 | Quantum-inspired algorithms |
Keyword-3 | Combinatorial optimization |