Efficient Quantum Circuit Simulation

Quantum mechanical phenomena are playing an increasing role in information processing as transistor sizes approach the nanometer level, and quantum circuits and data encoding methods appear in the securest forms of communication. Quantum-mechanical phenomena with a finite number of states can be modeled as quantum circuits, the quantum analogue of digital logic circuits. Simulation of quantum circuits can therefore be used as a tool to characterize important issues in the design of quantum information processing devices. Unfortunately, simulating such phenomena efficiently is exceedingly difficult because of the vast size of the quantum state space involved. The matrices representing quantum operators (gates), and vectors modeling quantum states grow exponentially with an increase in the number of states.

The information represented by quantum states and operators often exhibits various forms of structure that may be exploited to enable efficient simulation of certain classes of quantum circuits. We study the development of simulation methods that run on conventional computers and take advantage such structure. In particular, we define a new data structure for simulating quantum circuits called the quantum information decision diagram (QuIDD). Like the classical algebraic decision diagram (ADD) from which it is derived, a QuIDD is a compressed graph representation of a vector or matrix and permits computations to be performed directly on the compressed data.