Spectral Graph Theory for Quantum Codes and Quantum Algorithms
Principal investigators
Simon Apers, SECRET research team, Inria
Anthony Leverrier, SECRET research team, Inria
Ronald de Wolf, Algorithms & Complexity, CWI
Abstract
This project aims to apply tools from spectral graph theory to the study of quantum codes and quantum algorithms, such as SDP-solvers and quantum walks. Specifically we wish to gain better insight in the entanglement and preparation complexity of low-energy states of a quantum code, or for instance the Gibbs states underlying quantum SDP-solvers. Spectral graph theory provides both an algebraic and algorithmic connection between the spectral and structural or clustering properties of low-energy states of graphs. Augmented with recently established connections between clustering and entanglement properties of quantum states, these tools give a new and promising handle on the study of these states. From an algorithmic perspective, we wish to use the spectral graph connection to improve quantum Gibbs samplers of graph Laplacians. Such samplers are a key component of quantum SDP-solvers, and a main hurdle towards speeding up approximation algorithms for graph problems.
Website: in progress
Keywords: quantum algorithms, quantum error-correcting codes, spectral graph theory
