May 26 – 31, 2024
Western University
America/Toronto timezone
Welcome to the 2024 CAP Congress Program website! / Bienvenue au siteweb du programme du Congrès de l'ACP 2024!

Physics-inspired algorithms for optimization, learning, and counting

May 28, 2024, 2:15 PM
30m
SSC Rm 2028 (cap. 135) (Social Science Centre, Western U.)

SSC Rm 2028 (cap. 135)

Social Science Centre, Western U.

Invited Speaker / Conférencier(ère) invité(e) Theoretical Physics / Physique théorique (DTP-DPT) (DTP) T2-2 Theoretical and Mathematical Physics | Physique théorique et mathématique (DPT)

Speaker

Stefanos Kourtis

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

Author

Stefanos Kourtis

Presentation materials

There are no materials yet.