  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. Forward constrained bisimulation
yields a lower-dimensional model which exactly preserves quantum measurements
projected on a linear subspace of interest. Backward constrained bisimulation
gives a reduction that is valid on a subspace containing the circuit input,
from which the circuit result can be fully recovered. We provide an algorithm
to compute the constraint bisimulations yielding coarsest reductions in both
cases, using a duality result relating the two notions. 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. In particular, we show that constrained bisimulation can boost
decision-diagram-based quantum circuit simulation by several orders of
magnitude, allowing thus for substantial synergy effects.
