Graphs are powerful tools to represent relationships, but figuring out if two complex graphs are truly different (or structurally equivalent) is surprisingly hard. By simulating quantum walks over graphs and computing meaningful representations, this project takes a quantum leap toward solving the infamous Graph Isomorphism Problem.
A quantum walk is the quantum version of a classical random walk. In a classical random walk, a walker moves from one node to another in a graph based on certain probabilities. In contrast, in a quantum walk, the walker exists in a superposition of many possible paths at once, and its evolution is governed by quantum amplitudes, not classical probabilities. There are two main types of quantum walks: Discrete-Time (which evolves in discrete steps with a coin operator), and Continuous-Time (which evolves continuously based on the graph’s Laplacian matrix). In this project, we focus on Continuous-Time quantum walk, where the walker’s state evolves according to the Schrödinger equation.
This project starts with a pair of randomly generated graphs – possibly isomorphic, possibly not. We then simulate a continuous-time quantum walk on each graph. Instead of measuring this quantum state directly (which is costly and difficult), we apply a technique called shadow tomography, which allows us efficiently “snapshot” the quantum state many times using randomly chosen measurements and then reconstruct meaningful observable properties from the snapshots using classical processing. This approach gives us a compressed classical representation of the quantum state that can be used to estimate many observables with high accuracy and few samples. After obtaining a pool of samples, we use a neural network trained on the shadow observable space to distinguish the structure of pairs of graphs.
The ultimate goal is to generalize a fingerprint derived from quantum dynamics that uniquely captures the structure of a graph. With such a fingerprint, graph isomorphism testing reduces to a simple comparison, possibly opening doors for works in chemistry (such as protein structure analysis), network forensics, cryptography, and beyond. This work lies at the intersection of quantum computing, graph theory, and machine learning, and provides insights into how quantum principles can enhance classical algorithms, even without a full quantum computer.