  Generic quantum-circuit simulation appears intractable for conventional
computers and may be unnecessary because useful quantum circuits exhibit
significant structure that can be exploited during simulation. For example,
Gottesman and Knill identified an important subclass, called stabilizer
circuits, which can be simulated efficiently using group-theory techniques and
insights from quantum physics. Realistic circuits enriched with quantum
error-correcting codes and fault-tolerant procedures are dominated by
stabilizer subcircuits and contain a relatively small number of non-Clifford
components. Therefore, we develop new data structures and algorithms that
facilitate parallel simulation of such circuits. Stabilizer frames offer more
compact storage than previous approaches but require more sophisticated
bookkeeping. Our implementation, called Quipu, simulates certain quantum
arithmetic circuits (e.g., reversible ripple-carry adders) in polynomial time
and space for equal superpositions of $n$-qubits. On such instances, known
linear-algebraic simulation techniques, such as the (state-of-the-art)
BDD-based simulator QuIDDPro, take exponential time. We simulate quantum
Fourier transform and quantum fault-tolerant circuits using Quipu, and the
results demonstrate that our stabilizer-based technique empirically outperforms
QuIDDPro in all cases. While previous high-performance, structure-aware
simulations of quantum circuits were difficult to parallelize, we demonstrate
that Quipu can be parallelized with a nontrivial computational speedup.
