dorsal/arxiv
View SchemaImproving Gate-Level Simulation of Quantum Circuits
| Authors | George F. Viamontes, Igor L. Markov, John P. Hayes |
|---|---|
| Categories | |
| ArXiv ID | quant-ph/0309060 |
| URL | https://arxiv.org/abs/quant-ph/0309060 |
| Journal | Quantum Information Processing, vol. 2(5), pp. 347-380, October 2003. |
Abstract
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.
{
"annotation_id": "3dc47288-1fce-4dd2-bcdc-86f9af7953f4",
"date_created": "2026-03-02T18:02:02.726000Z",
"date_modified": "2026-03-02T18:02:02.726000Z",
"file_hash": "5b3746dd4f6f980f9b31957ae118336a7600eec8c7ffd5f58e9e590ac446e6b4",
"private": false,
"record": {
"abstract": "Simulating quantum computation on a classical computer is a difficult\nproblem. The matrices representing quantum gates, and the vectors modeling\nqubit states grow exponentially with an increase in the number of qubits.\nHowever, by using a novel data structure called the Quantum Information\nDecision Diagram (QuIDD) that exploits the structure of quantum operators, a\nuseful subset of operator matrices and state vectors can be represented in a\nform that grows polynomially with the number of qubits. This subset contains,\nbut is not limited to, any equal superposition of n qubits, any computational\nbasis state, n-qubit Pauli matrices, and n-qubit Hadamard matrices. It does\nnot, however, contain the discrete Fourier transform (employed in Shor\u0027s\nalgorithm) and some oracles used in Grover\u0027s algorithm. We first introduce and\nmotivate decision diagrams and QuIDDs. We then analyze the runtime and memory\ncomplexity of QuIDD operations. Finally, we empirically validate QuIDD-based\nsimulation by means of a general-purpose quantum computing simulator QuIDDPro\nimplemented in C++. We simulate various instances of Grover\u0027s algorithm with\nQuIDDPro, and the results demonstrate that QuIDDs asymptotically outperform all\nother known simulation techniques. Our simulations also show that well-known\nworst-case instances of classical searching can be circumvented in many\nspecific cases by data compression techniques.",
"arxiv_id": "quant-ph/0309060",
"authors": [
"George F. Viamontes",
"Igor L. Markov",
"John P. Hayes"
],
"categories": [
"quant-ph"
],
"journal_ref": "Quantum Information Processing, vol. 2(5), pp. 347-380, October\n 2003.",
"title": "Improving Gate-Level Simulation of Quantum Circuits",
"url": "https://arxiv.org/abs/quant-ph/0309060"
},
"schema_id": "dorsal/arxiv",
"source": {
"execution_id": "c475875d-ac56-4dda-8442-8317714963cf",
"id": "arXiv Dataset IDs",
"type": "Model",
"variant": "snapshot-2026-03-01",
"version": "0.1.0"
},
"user_id": 1000002
}