  Verifying equivalence between two quantum circuits is a hard problem, that is
nonetheless crucial in compiling and optimizing quantum algorithms for
real-world devices. This paper gives a Turing reduction of the (universal)
quantum circuits equivalence problem to weighted model counting (WMC). Our
starting point is a folklore theorem showing that equivalence checking of
quantum circuits can be done in the so-called Pauli-basis. We combine this
insight with a WMC encoding of quantum circuit simulation, which we extend with
support for the Toffoli gate. Finally, we prove that the weights computed by
the model counter indeed realize the reduction. With an open-source
implementation, we demonstrate that this novel approach can outperform a
state-of-the-art equivalence-checking tool based on ZX calculus and decision
diagrams.
