Talk "Efficient Quantum Circuit Analysis via Constrained Bisimulation"

by Max Tschaikowski

Mon, 05 February 2024 at 04:30 pm in Salzburg, Austria

Joint work with: Antonio Jiménez-Pastor, Kim G. Larsen and Mirco Tribastone

Abstract: Efficient methods for the simulation of quantum circuits on classic computers are crucial for their analysis due to the exponential growth of the problem size with the number of qubits. Here we study lumping methods based on bisimulation, an established class of techniques that has been proven successful for (classic) stochastic and deterministic systems such as Markov chains and ordinary differential equations. Constrained bisimulation yields a lower-dimensional model which gives from which the circuit result can be fully recovered. We provide an algorithm to compute the constraint bisimulation yielding coarsest reductions. As applications, we provide theoretical bounds on the size of the reduced state space for well-known quantum algorithms for search, optimization, and factorization. Using a prototype implementation, we report significant reductions on a set of benchmarks. Furthermore, we show that constraint bisimulation complements state-of-the-art methods for the simulation of quantum circuits based on decision diagrams. Accepted at TACAS'24, available at https://arxiv.org/abs/2308.09510