CRII: FET: Quantum Advantages through Discrete Quantum Walks

Quantum computing has shown great potential in efficiently exploring solution spaces and enhancing optimization tasks in supply chain and logistics. A key tool in quantum computing, known as discrete quantum walks, can be used to build quantum circuits and model a number of quantum algorithms including Grover's search. While advantages of discrete quantum walks become clear through numerical evidence, a unified, graph-theoretical framework that allows researchers to prove these advantages is missing. To bridge the gap, this project addresses the following question: how is the behavior of a discrete quantum walk determined by the combinatorial properties of the underlying graph? Answers to this question will help pinpoint graphs on which discrete quantum walks exhibit advantages, and ultimately lead to new constructions of quantum-walk-based algorithms. Broader impacts of this project include quantum-inspired transformations in AI technology, biomedical research, climate science, optimization, financial modelling, and training of a diverse workforce in quantum science and technology. The technical objective of this project is to prove (or disprove) certain phenomena in discrete quantum walks using graph theory and algebra. Prior work by the investigator has revealed spectral relations between the transition matrix of a discrete quantum walk and the incidence matrices of various combinatorial structures. Built upon these relations, this project will (1) offer characterizations of graphs that are "spectrally nice" to enable desired quantum phenomena, such as high-fidelity state transfer and uniform mixing, (2) establish connections between discrete quantum walks and continuous quantum walks, which are physically different but share transferable mathematical machinery, and (3) identify test cases for discrete-quantum-walk approaches to hard combinatorial problems, thereby assessing their effectiveness. Outcomes of this project will not only advance scientific understanding of quantum walks, but also enrich educational experience by incorporating these findings into future quantum computing courses and engaging students in mentoring activities. This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.