On the Role of Graphs in Quantum Computing

This thesis investigates the role of graphs in quantum computing, exploring whether their utility in classical computation—where they serve as tools for representation, optimization, and problem-solving—extends meaningfully into quantum computational paradigms. Beginning with the foundational importance of graphs in classical computing, this work examines how graphs are used to model, compress, and solve complex computational problems, particularly in contexts that benefit from their semantic flexibility. Building on this, the thesis addresses the question of how graphs can be encoded and manipulated within quantum computing, with a specific focus on the gate-based model of quantum computation. Encoding graphs for quantum systems presents unique challenges, particularly the need for unitary transformations that respect quantum mechanics' constraints. Through the exploration of graph-based techniques in quantum settings, this thesis develops and analyzes methods for encoding classical graph structures in ways compatible with quantum requirements. Additionally, it examines the application of graphs in quantum-specific tasks, such as quantum random walks, quantum automata, and quantum circuit synthesis, showing that graph-based approaches can aid in circuit optimization and algorithm design. The findings contribute to understanding whether classical tools like graphs can provide practical and theoretical advantages in quantum computation, offering a bridge between classical and quantum frameworks. This thesis presents several encoding strategies, practical applications, and a comparative analysis, concluding with insights into future directions where graph theory might further intersect with quantum computing advancements.