Simulating Quantum Circuits by Model Counting

Lecture notes in computer science, pp. 555–578

Abstract

Abstract Quantum circuit compilation comprises many computationally hard reasoning tasks that lie inside # $${\textsf{P}}$$ P and its decision counterpart in $${\textsf{PP}}$$ PP . The classical simulation of universal quantum circuits is a core example. We show for the first time that a strong simulation of universal quantum circuits can be efficiently tackled through weighted model counting by providing a linear-length encoding of Clifford+Tcircuits. To achieve this, we exploit the stabilizer formalism by Knill, Gottesmann, and Aaronson by reinterpreting quantum states as a linear combination of stabilizer states. With an open-source simulator implementation, we demonstrate empirically that model counting often outperforms state-of-the-art simulation techniques based on the ZX calculus and decision diagrams. Our work paves the way to apply the existing array of powerful classical reasoning tools to realize efficient quantum circuit compilation; one of the obstacles on the road towards quantum supremacy.

Authors 3

1. Jingyi Mei corresponding Aachen

   Leiden University

   Affiliation as printed

   Leiden University, Leiden, The Netherlands

2. Marcello Bonsangue Aachen

   Leiden University

   Affiliation as printed

   Leiden University, Leiden, The Netherlands

3. Alfons Laarman Aachen

   Leiden University

   Affiliation as printed

   Leiden University, Leiden, The Netherlands