Physics – Quantum Physics
Scientific paper
2003-09-06
Quantum Information Processing, vol. 2(5), pp. 347-380, October 2003.
Physics
Quantum Physics
22 pages, 9 figures. Earlier work was reported in quant-ph/0208003; this document shows significantly improved empirical resul
Scientific paper
Simulating quantum computation on a classical computer is a difficult problem. The matrices representing quantum gates, and the vectors modeling qubit states grow exponentially with an increase in the number of qubits. However, by using a novel data structure called the Quantum Information Decision Diagram (QuIDD) that exploits the structure of quantum operators, a useful subset of operator matrices and state vectors can be represented in a form that grows polynomially with the number of qubits. This subset contains, but is not limited to, any equal superposition of n qubits, any computational basis state, n-qubit Pauli matrices, and n-qubit Hadamard matrices. It does not, however, contain the discrete Fourier transform (employed in Shor's algorithm) and some oracles used in Grover's algorithm. We first introduce and motivate decision diagrams and QuIDDs. We then analyze the runtime and memory complexity of QuIDD operations. Finally, we empirically validate QuIDD-based simulation by means of a general-purpose quantum computing simulator QuIDDPro implemented in C++. We simulate various instances of Grover's algorithm with QuIDDPro, and the results demonstrate that QuIDDs asymptotically outperform all other known simulation techniques. Our simulations also show that well-known worst-case instances of classical searching can be circumvented in many specific cases by data compression techniques.
Hayes John P.
Markov Igor L.
Viamontes George F.
No associations
LandOfFree
Improving Gate-Level Simulation of Quantum Circuits does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Improving Gate-Level Simulation of Quantum Circuits, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Improving Gate-Level Simulation of Quantum Circuits will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-263786