Riccardo Romanello<https://riccardoromanello.github.io/publications.html> will visit our group Oct 6-Oct 10. He will present his work on quantum computing and graphs on Oct 6, 11-12. (NB, Riccardo will give a second presentation about emerging directions "Wiring Up Quantum Circuits: A Graph Story" in the Quantum Software Seminar Friday 10/10/10:00 Turing 230). See Mattermost/Quantum Software for details) Title: On the role of graphs in quantum computation Abstract: In this talk, I will present three papers I authored during my PhD, highlighting both theoretical and practical aspects of quantum computing. The first part of the talk focuses on a fundamental problem concerning the representation of graphs within quantum algorithms. In the gate-based model of quantum computing, how can a graph be encoded as a unitary matrix? Addressing this question is essential for designing quantum algorithms capable of outperforming classical approaches. I will show that the solution is closely connected to the notion of Eulerian graphs, revealing deep links between graph theory and quantum algorithm design. The second part of the talk shifts to quantum circuit compilation, with a particular focus on CNOT circuits-circuits constructed exclusively from CNOT gates. A central question here is the minimality of such circuits: how can we generate the smallest possible CNOT circuits for a given computation? I will present two complementary approaches. The first is an exact method based on Answer Set Programming, which guarantees the synthesis of optimal CNOT circuits. The second is an approximate approach using Reinforcement Learning, which demonstrates how techniques from Artificial Intelligence can inform and accelerate circuit synthesis, providing a practical bridge between algorithmic optimization and machine learning. The aim of this talk is not only to survey these problems but also to highlight open challenges and potential research directions, with the goal of promoting discussions in quantum algorithm design and circuit optimization.