Towards a complete formal and computational description of linear optical quantum circuits

Abstract

Quantum computers leverage the principles of quantum physics to encode and process information, offering promising applications that may overcome the capabilities of classical computers. This thesis explores one of the leading technologies for quantum computation: linear optics, where computations are performed with photons passing through linear optical circuits. While linear optical circuits are well understood and computationally tractable when they are small, their real significance emerges at larger scales, where they transition into regimes beyond classical computational reach. This thesis addresses both aspects: first, by developing a more detailed computational description to push the limits of classical simulations; and second, by establishing a formal framework to analyze these systems from a higher-level perspective. On the simulation side, a key challenge is computing output probabilities efficiently. We develop new algorithms to compute several of these probabilities, where memory usage is optimized to significantly reduce computation time. This work leads to the development of Perceval, an open-source software platform specifically designed for photonic quantum computing. On the theoretical side, we construct a formal and diagrammatic framework that fully captures the structure of linear optical processes. Specifically, we introduce graphical languages, widely used in quantum computing, to model linear optical circuits. We establish a complete equational theory, proving that any two equivalent linear optical circuits can always be rewritten locally using our set of equations. Finally, we show how our contributions provide tools to both physics and theoretical quantum computing problems. In particular, we extend our complete equational theory for linear optical circuits to derive a complete equational theory for general quantum circuits, resolving a long-standing open problem.