It is generally believed that simulating quantum computers on a classical computer requires time and memory resources that are exponential in the number of qubits. However, I have developed a novel data structure called the Quantum Information Decision Diagram (QuIDD) which can be used to simulate many instances of quantum computational circuits using only polynomial time and memory resources. Based on the Binary Decision Diagram data structure, the QuIDD representation compresses the massive redundancy of matrix elements exhibited in quantum operators and states. Unlike standard compression techniques, QuIDDs can be manipulated directly. Thus, important operations such as matrix multiplication and the tensor product can be performed directly on QuIDDs without any decompression.

I have implemented the QuIDD data structure as a C++ quantum computational circuit simulator called QuIDDPro. Using QuIDDPro, I have been able to perform numerous polynomial time and memory simulations of quantum circuits, including several instances of Grover's algorithm for quantum search in both the state-vector and density matrix models. In my most recent work [3], my advisors and I present a formal complexity analysis which mathematically describes the entire set of matrices and vectors that can be represented and simulated as QuIDDs using only polynomial time and memory on a classical computer. This set includes, but is not limited to, any equal superposition of n qubits, any sequence of n qubits in the computational basis states, n-qubit Pauli operators, and n-qubit Hadamard operators.

QuIDDPro will play a vital role in my dissertation work. In particular, I am using QuIDDPro to explore errors and decoherence, which are pervasive in any quantum computer implementation. In my preliminary efforts towards this goal, I have simulated a NIST benchmark for a 13-qubit circuit which utilizes the Steane error correcting code to cope with phase flip errors in an initially mixed state. In simulating this circuit, NIST's QCSim quantum circuit simulator requires 512.1 MB of memory and a runtime of 287.1 seconds, whereas QuIDDPro only requires 0.516 MB of memory and a runtime of 0.639 seconds. Additionally, I have had success in simulating quantum communication protocols, such as BB84, with QuIDDPro. In quantum communications, an eavesdropper "listening in" on the quantum channel can equivalently be treated as noise. It is therefore no surprise that QuIDDPro delivers performance results that are similar to the phase flip error simulations. With this level of simulation performance, I will be able to explore a larger set of error/decoherence models and quantum communication protocols much more quickly. Lastly, I am also investigating the limitations of quantum computation. Since QuIDDPro can simulate instances of Grover's algorithm and other quantum circuits using only polynomial time and memory on a classical computer, such circuits do not offer any improvement over classical compuation. When combined with the fact that classical computers do not have to deal with probabilistic measurement, these results offer another interesting direction in my thesis work.

[1] G. Viamontes, M. Rajagopalan, I. Markov, J. Hayes, "Gate-Level Simulation of Quantum Circuits," In Proc. of the 6th Intl. Conference on Quantum Communication, Measurement, and Computing, pp. 311-314, MIT Cambridge, MA, July 2002.

[2] G. Viamontes, M. Rajagopalan, I. Markov, J. Hayes, "Gate-Level Simulation of Quantum Circuits," In Proc. of the Asia South Pacific Design Automation Conference, pp. 295-301, January 2003.

[3] G. Viamontes, I. Markov, J. Hayes, "Improving Gate-Level Simulation of Quantum Circuits," submitted to the Journal of Quantum Information Processing (currently being reviewed; preprint available at http://xxx.lanl.gov/abs/quant-ph/0309060).

Krell   |   DOE HPCSF   |   Fellows   |   Contact