More Web Proxy on the site http://driver.im/

research-article

High performance emulation of quantum circuits

Authors:

Damian S. Steiger,

Mikhail Smelyanskiy,

Matthias TroyerAuthors Info & Claims

SC '16: Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis

Article No.: 74, Pages 1 - 9

Published: 13 November 2016 Publication History

Abstract

As quantum computers of non-trivial size become available in the near future, it is imperative to develop tools to emulate small quantum computers. This allows for validation and debugging of algorithms as well as exploring hardware-software co-design to guide the development of quantum hardware and architectures. The simulation of quantum computers entails multiplications of sparse matrices with very large dense vectors of dimension 2ⁿ, where n denotes the number of qubits, making this a memory-bound and network bandwidth-limited application. We introduce the concept of a quantum computer emulator as a component of a software framework for quantum computing, enabling a significant performance advantage over simulators by emulating quantum algorithms at a high level rather than simulating individual gate operations. We describe various optimization approaches and present benchmarking results, establishing the superiority of quantum computer emulators in terms of performance.

References

[1]

G. E. Moore, "Readings in computer architecture," M. D. Hill, N. P. Jouppi, and G. S. Sohi, Eds. San Francisco, CA, USA: Morgan Kaufmann Publishers Inc., 2000, ch. Cramming More Components Onto Integrated Circuits, pp. 56--59. {Online}. Available: http://dl.acm.org/citation.cfm?id=333067.333074

Digital Library

[2]

S. Jordan, "Quantum algorithm zoo," http://math.nist.gov/quantum/zoo/.

[3]

P. W. Shor, "Algorithms for quantum computation: Discrete logarithms and factoring," in Foundations of Computer Science, 1994 Proceedings., 35th Annual Symposium on. IEEE, 1994, pp. 124--134.

Digital Library

[4]

A. Aspuru-Guzik, A. D. Dutoi, P. J. Love, and M. Head-Gordon, "Simulated quantum computation of molecular energies," Science, vol. 309, no. 5741, pp. 1704--1707, 2005.

[5]

B. Bauer, D. Wecker, A. J. Millis, M. B. Hastings, and M. Troyer, "Hybrid quantum-classical approach to correlated materials," arXiv preprint arXiv:1510.03859, 2015.

[6]

T. Häner, D. S. Steiger, K. Svore, and M. Troyer, "A software methodology for compiling quantum programs," arXiv preprint arXiv:1604.01401, 2016.

[7]

A. F. Rodrigues, K. S. Hemmert, B. W. Barrett, C. Kersey, R. Oldfield, M. Weston, R. Risen, J. Cook, P. Rosenfeld, E. CooperBalls et al., "The structural simulation toolkit," ACM SIGMETRICS Performance Evaluation Review, vol. 38, no. 4, pp. 37--42, 2011.

Digital Library

[8]

C.-K. Luk, R. Cohn, R. Muth, H. Patil, A. Klauser, G. Lowney, S. Wallace, V. J. Reddi, and K. Hazelwood, "Pin: Building customized program analysis tools with dynamic instrumentation," in Proceedings of the 2005 ACM SIGPLAN Conference on Programming Language Design and Implementation, ser. PLDI '05. New York, NY, USA: ACM, 2005, pp. 190--200. {Online}. Available: http://doi.acm.org/10.1145/1065010.1065034

Digital Library

[9]

M. B. Hastings, D. Wecker, B. Bauer, and M. Troyer, "Improving quantum algorithms for quantum chemistry," Quantum Information & Computation, vol. 15, no. 1-2, pp. 1--21, 2015.

Digital Library

[10]

R. Babbush, J. McClean, D. Wecker, A. Aspuru-Guzik, and N. Wiebe, "Chemical basis of trotter-suzuki errors in quantum chemistry simulation," Physical Review A, vol. 91, no. 2, p. 022311, 2015.

[11]

C. Bennett, "Logical reversibility of computation," Maxwells Demon. Entropy, Information, Computing, pp. 197--204, 1973.

[12]

A. Parent, M. Roetteler, and K. M. Svore, "Reversible circuit compilation with space constraints," arXiv:1510.00377, 2015.

[13]

S. A. Cuccaro, T. G. Draper, S. A. Kutin, and D. P. Moulton, "A new quantum ripple-carry addition circuit," arXiv preprint quant-ph/0410184, 2004.

[14]

M. A. Nielsen and I. L. Chuang, Quantum computation and quantum information. Cambridge university press, 2010.

Digital Library

[15]

D. H. Bailey, "Ffts in external or hierarchical memory," J. Supercomput., vol. 4, no. 1, pp. 23--35, Mar. 1990. {Online}. Available: http://dx.doi.org/10.1007/BF00162341

Digital Library

[16]

M. Frigo and S. G. Johnson, "The design and implementation of FFTW3," Proceedings of the IEEE, vol. 93, no. 2, pp. 216--231, 2005, special issue on "Program Generation, Optimization, and Platform Adaptation".

[17]

S. Beauregard, "Circuit for shor's algorithm using 2n+ 3 qubits," arXiv preprint quant-ph/0205095, 2002.

Digital Library

[18]

G. H. Golub, S. Nash, and C. Van Loan, "A hessenberg-schur method for the problem ax+ xb= c," Automatic Control, IEEE Transactions on, vol. 24, no. 6, pp. 909--913, 1979.

[19]

"Texas Advanced Computing Center (TACC)," https://www.tacc.utexas.edu/stampede/, retrieved: 2014-12-01.

[20]

ARB OpenMP, "Openmp 4.0 specification, june 2013," 2013.

[21]

P. T. P. Tang, J. Kestyn, and E. Polizzi, "A new highly parallel non-hermitian eigensolver," in Proceedings of the High Performance Computing Symposium, ser. HPC '14. San Diego, CA, USA: Society for Computer Simulation International, 2014, pp. 1:1--1:9. {Online}. Available: http://dl.acm.org/citation.cfm?id=2663510.2663511

Digital Library

[22]

M. Smelyanskiy, N. P. Sawaya, and A. Aspuru-Guzik, "qhipster: The quantum high performance software testing environment," arXiv preprint arXiv:1601.07195, 2016.

[23]

D. Wecker and K. M. Svore, "LIQUi|&rang;: A software design architecture and domain-specific language for quantum computing," arXiv:1402.4467, 2014.

[24]

A. S. Green, P. L. Lumsdaine, N. J. Ross, P. Selinger, and B. Valiron, "Quipper: a scalable quantum programming language," in ACM SIGPLAN Notices, vol. 48, no. 6. ACM, 2013, pp. 333--342.

Digital Library

[25]

R. Somma, S. Boixo, H. Barnum, and E. Knill, "Quantum simulations of classical annealing processes," Physical review letters, vol. 101, no. 13, p. 130504, 2008.

[26]

N. Wiebe, A. Kapoor, and K. M. Svore, "Quantum deep learning," arXiv preprint arXiv:14123489, 2014.

[27]

N. Wiebe, A. Kapoor, and K. Svore, "Quantum nearest-neighbor algorithms for machine learning," arXiv preprint arXiv:1401.2142, 2014.

[28]

P. Rebentrost, M. Mohseni, and S. Lloyd, "Quantum support vector machine for big data classification," Physical review letters, vol. 113, no. 13, p. 130503, 2014.

Cited By

Guo XZhao JZhao P(2024)On Repairing Quantum Programs Using ChatGPTProceedings of the 5th ACM/IEEE International Workshop on Quantum Software Engineering10.1145/3643667.3648223(9-16)Online publication date: 16-Apr-2024
https://dl.acm.org/doi/10.1145/3643667.3648223
Takahashi KMori TTakizawa H(2023)Prototype of a Batched Quantum Circuit Simulator for the Vector EngineProceedings of the SC '23 Workshops of The International Conference on High Performance Computing, Network, Storage, and Analysis10.1145/3624062.3624226(1499-1505)Online publication date: 12-Nov-2023
https://dl.acm.org/doi/10.1145/3624062.3624226
Resch SKarpuzcu U(2021)Benchmarking Quantum Computers and the Impact of Quantum NoiseACM Computing Surveys10.1145/346442054:7(1-35)Online publication date: 18-Jul-2021
https://dl.acm.org/doi/10.1145/3464420
Show More Cited By

Recommendations

Commuting quantum circuits: efficient classical simulations versus hardness results

The study of quantum circuits composed of commuting gates is particularly useful to understand the delicate boundary between quantum and classical computation. Indeed, while being a restricted class, commuting circuits exhibit genuine quantum effects ...
Quantum circuits and spin(3n) groups

All quantum gates with one and two qubits may be described by elements of Spin groups due to isomorphisms Spin(3) ≃ SU(2) and Spin(6) ≃ SU(4). However, the group of n-qubit gates SU(2ⁿ) for n > 2 has bigger dimension than Spin(3n). A quantum circuit ...
Quantum circuits for qubit fusion

We consider four-dimensional qudits as qubit pairs and their qudit Pauli operators as qubit Clifford operators. This introduces a nesting, C₁² ⊂ C₂⁴ ⊂ C₃², where C_n^m is the nth level of the m-dimensional qudit Clifford hierarchy. If we can convert ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

SC '16: Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis

November 2016

1034 pages

ISBN:9781467388153

Conference Chair:
John West
University of Texas at Austin

Sponsors

SIGARCH: ACM Special Interest Group on Computer Architecture
IEEE-CS: Computer Society

In-Cooperation

SIGHPC: ACM Special Interest Group on High Performance Computing, Special Interest Group on High Performance Computing

Publisher

IEEE Press

Publication History

Published: 13 November 2016

Check for updates

Qualifiers

Research-article

Conference

SC16

Sponsor:

SIGARCH
IEEE-CS

SC16: The International Conference for High Performance Computing, Networking, Storage and Analysis

November 13 - 18, 2016

Utah, Salt Lake City

Acceptance Rates

SC '16 Paper Acceptance Rate 81 of 442 submissions, 18%;

Overall Acceptance Rate 1,516 of 6,373 submissions, 24%

Upcoming Conference

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

7
Total Citations
View Citations
269
Total Downloads

Downloads (Last 12 months)12
Downloads (Last 6 weeks)3

Reflects downloads up to 15 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Guo XZhao JZhao P(2024)On Repairing Quantum Programs Using ChatGPTProceedings of the 5th ACM/IEEE International Workshop on Quantum Software Engineering10.1145/3643667.3648223(9-16)Online publication date: 16-Apr-2024
https://dl.acm.org/doi/10.1145/3643667.3648223
Takahashi KMori TTakizawa H(2023)Prototype of a Batched Quantum Circuit Simulator for the Vector EngineProceedings of the SC '23 Workshops of The International Conference on High Performance Computing, Network, Storage, and Analysis10.1145/3624062.3624226(1499-1505)Online publication date: 12-Nov-2023
https://dl.acm.org/doi/10.1145/3624062.3624226
Resch SKarpuzcu U(2021)Benchmarking Quantum Computers and the Impact of Quantum NoiseACM Computing Surveys10.1145/346442054:7(1-35)Online publication date: 18-Jul-2021
https://dl.acm.org/doi/10.1145/3464420
Li AFang BGranade CPrawiroatmodjo GHeim BRoetteler MKrishnamoorthy Sde Supinski BHall MGamblin T(2021)SV-simProceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis10.1145/3458817.3476169(1-14)Online publication date: 14-Nov-2021
https://dl.acm.org/doi/10.1145/3458817.3476169
Huang YMartonosi MManne SHunter HAltman E(2019)Statistical assertions for validating patterns and finding bugs in quantum programsProceedings of the 46th International Symposium on Computer Architecture10.1145/3307650.3322213(541-553)Online publication date: 22-Jun-2019
https://dl.acm.org/doi/10.1145/3307650.3322213
Beillahi SMahmoud MTahar S(2019)A modeling and verification framework for optical quantum circuitsFormal Aspects of Computing10.1007/s00165-019-00480-531:3(321-351)Online publication date: 1-Jun-2019
https://dl.acm.org/doi/10.1007/s00165-019-00480-5
Häner TRoetteler MSvore K(2017)Factoring using 2n + 2 qubits with Toffoli based modular multiplicationQuantum Information & Computation10.5555/3179553.317956017:7-8(673-684)Online publication date: 1-Jun-2017
https://dl.acm.org/doi/10.5555/3179553.3179560

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents