  Quantum computation is a promising emerging technology which, compared to
conventional computation, allows for substantial speed-ups e.g. for integer
factorization or database search. However, since physical realizations of
quantum computers are in their infancy, a significant amount of research in
this domain still relies on simulations of quantum computations on conventional
machines. This causes a significant complexity which current state-of-the-art
simulators try to tackle with a rather straight forward array-based
representation and by applying massive hardware power. There also exist
solutions based on decision diagrams (i.e. graph-based approaches) that try to
tackle the exponential complexity by exploiting redundancies in quantum states
and operations. However, these existing approaches do not fully exploit
redundancies that are actually present. In this work, we revisit the basics of
quantum computation, investigate how corresponding quantum states and quantum
operations can be represented even more compactly, and, eventually, simulated
in a more efficient fashion. This leads to a new graph-based simulation
approach which outperforms state-of-the-art simulators (array-based as well as
graph-based). Experimental evaluations show that the proposed solution is
capable of simulating quantum computations for more qubits than before, and in
significantly less run-time (several magnitudes faster compared to previously
proposed simulators). An implementation of the proposed simulator is publicly
available online at http://iic.jku.at/eda/research/quantum_simulation.
