Trieste Quantum Seminars:

Reductions, Paths, and Search: Three Classical Strategies for the Quantum Stack

prof. Carla Piazza
Dipartimento di Scienze Matematiche, Informatiche e Fisiche, Universita degli Studi di Udine

Abstract: In today's NISQ devices the real bottleneck is not only the hardware, but our ability to adapt problems and circuits to the actual constraints of the machines. In this seminar I show how classical tools from theoretical computer science and artificial intelligence — complexity theory, graph theory, and reinforcement learning — can provide concrete leverage across the entire quantum stack.

In this seminar I briefly present three recent contributions. The first, LE-QAOA, draws on Lreductions from complexity theory to map constrained combinatorial optimization problems onto a canonical MAX2SAT form, which can then be tackled with efficient unconstrained QAOA subroutines followed by a classical repair step; on the Maximum Independent Set problem it matches or exceeds native constrained solvers while retaining the runtime scalability of unconstrained ones. The second addresses qubit routing through swap networks built deterministically from minimum Dominating Paths — a circuit-agnostic construction that decouples routing from circuit structure and consistently produces shorter, more interpretable schedules than stochastic baselines across IBM architectures up to 133 qubits. The third, AlphaCNOT, casts CNOTgate minimization as a planning problem and solves it with a model-based reinforcement learning agent built on Monte Carlo Tree Search (in the spirit of AlphaZero), improving on both classical heuristics and earlier model-free RL approaches in the linear-reversible and topology-aware settings.

The common thread is that mature methods from AI and theoretical computer science, suitably reinterpreted, are powerful levers for moving toward quantum utility.