  High-performance techniques to simulate quantum programs on classical
hardware rely on exponentially large vectors to represent quantum states. When
simulating quantum algorithms, the quantum states that occur are often sparse
due to special structure in the algorithm or even in the underlying problem. We
thus introduce a new simulation method that exploits this sparsity to reduce
memory usage and simulation runtime. Moreover, our prototype implementation
includes optimizations such as gate (re)scheduling, which amortizes data
structure accesses and reduces memory usage.
  To benchmark our implementation, we run quantum algorithms for factoring,
computing integer and elliptic curve discrete logarithms, and for chemistry.
Our simulator successfully runs a factoring instance of a 20-bit number using
102 qubits, and elliptic curve discrete logarithm over a 10-bit curve with 110
qubits. While previous work needed a supercomputer to simulate such instances
of factoring, our approach succeeds in less than 4 minutes using a single core
and less than 100 MB of memory. To the best of our knowledge, we are the first
to fully simulate a quantum algorithm to compute elliptic curve discrete
logarithms.
