Improving Gate-Level Simulation of Quantum Circuits
dc.contributor.author | Viamontes, George F. | en_US |
dc.contributor.author | Markov, Igor L. | en_US |
dc.contributor.author | Hayes, John P. (John Patrick) | en_US |
dc.date.accessioned | 2006-09-11T16:09:49Z | |
dc.date.available | 2006-09-11T16:09:49Z | |
dc.date.issued | 2003-10 | en_US |
dc.identifier.citation | Viamontes, George F.; Markov, Igor L.; Hayes, John P.; (2003). "Improving Gate-Level Simulation of Quantum Circuits." Quantum Information Processing 2(5): 347-380. <http://hdl.handle.net/2027.42/45525> | en_US |
dc.identifier.issn | 1570-0755 | en_US |
dc.identifier.issn | 1573-1332 | en_US |
dc.identifier.uri | https://hdl.handle.net/2027.42/45525 | |
dc.description.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. | en_US |
dc.format.extent | 380010 bytes | |
dc.format.extent | 3115 bytes | |
dc.format.mimetype | application/pdf | |
dc.format.mimetype | text/plain | |
dc.language.iso | en_US | |
dc.publisher | Kluwer Academic Publishers-Plenum Publishers; Plenum Publishing Corporation ; Springer Science+Business Media | en_US |
dc.subject.other | Computer Science, General | en_US |
dc.subject.other | Physics | en_US |
dc.subject.other | Physics, General | en_US |
dc.subject.other | Quantum Search | en_US |
dc.subject.other | Quantum Computation | en_US |
dc.subject.other | Decision Diagrams | en_US |
dc.subject.other | Algorithms | en_US |
dc.subject.other | Characterization and Evaluation Materials | en_US |
dc.subject.other | Mathematics, General | en_US |
dc.subject.other | Engineering, General | en_US |
dc.subject.other | Quantum Computer Simulation | en_US |
dc.subject.other | Data Compression | en_US |
dc.subject.other | Graphs | en_US |
dc.title | Improving Gate-Level Simulation of Quantum Circuits | en_US |
dc.type | Article | en_US |
dc.subject.hlbsecondlevel | Philosophy | en_US |
dc.subject.hlbsecondlevel | Computer Science | en_US |
dc.subject.hlbtoplevel | Humanities | en_US |
dc.subject.hlbtoplevel | Engineering | en_US |
dc.description.peerreviewed | Peer Reviewed | en_US |
dc.contributor.affiliationum | Advanced Computer Architecture Laboratory, The University of Michigan, Ann Arbor, Michigan, 48109-2122, USA | en_US |
dc.contributor.affiliationum | Advanced Computer Architecture Laboratory, The University of Michigan, Ann Arbor, Michigan, 48109-2122, USA | en_US |
dc.contributor.affiliationum | Advanced Computer Architecture Laboratory, The University of Michigan, Ann Arbor, Michigan, 48109-2122, USA | en_US |
dc.contributor.affiliationumcampus | Ann Arbor | en_US |
dc.description.bitstreamurl | http://deepblue.lib.umich.edu/bitstream/2027.42/45525/1/11128_2004_Article_482625.pdf | en_US |
dc.identifier.doi | http://dx.doi.org/10.1023/B:QINP.0000022725.70000.4a | en_US |
dc.identifier.source | Quantum Information Processing | en_US |
dc.owningcollname | Interdisciplinary and Peer-Reviewed |
Files in this item
Remediation of Harmful Language
The University of Michigan Library aims to describe library materials in a way that respects the people and communities who create, use, and are represented in our collections. Report harmful or offensive language in catalog records, finding aids, or elsewhere in our collections anonymously through our metadata feedback form. More information at Remediation of Harmful Language.
Accessibility
If you are unable to use this file in its current format, please select the Contact Us link and we can modify it to make it more accessible to you.