Article

Symbolic Quantum Simulation with Quasimodo

Authors:

Meghana Sistla,

Swarat Chaudhuri,

Thomas RepsAuthors Info & Claims

Computer Aided Verification: 35th International Conference, CAV 2023, Paris, France, July 17–22, 2023, Proceedings, Part III

Pages 213 - 225

https://doi.org/10.1007/978-3-031-37709-9_11

Published: 17 July 2023 Publication History

Abstract

The simulation of quantum circuits on classical computers is an important problem in quantum computing. Such simulation requires representations of distributions over very large sets of basis vectors, and recent work has used symbolic data-structures such as Binary Decision Diagrams (BDDs) for this purpose. In this tool paper, we present Quasimodo, an extensible, open-source Python library for symbolic simulation of quantum circuits. Quasimodo is specifically designed for easy extensibility to other backends. Quasimodo allows simulations of quantum circuits, checking properties of the outputs of quantum circuits, and debugging quantum circuits. It also allows the user to choose from among several symbolic data-structures—both unweighted and weighted BDDs, and a recent structure called Context-Free-Language Ordered Binary Decision Diagrams (CFLOBDDs)—and can be easily extended to support other symbolic data-structures.

References

[1]

Aleksandrowicz, G., et al.: Qiskit: an open-source framework for quantum computing (2021).

[2]

Alur R, Benedikt M, Etessami K, Godefroid P, Reps T, and Yannakakis M Analysis of recursive state machines ACM Trans. Progr. Lang. Syst. 2005 27 4 786-818

[3]

Bahar, R.I., et al.: Algebraic decision diagrams and their applications. Formal Methods Syst. Des. 10(2/3), 171–206 (1997).

[4]

Beauregard, S.: Circuit for Shor’s algorithm using 2n+3 qubits. arXiv preprint quant-ph/0205095 (2002)

[5]

Bryant, R.E.: Graph-based algorithms for Boolean function manipulation. IEEE Trans. Comp. C-35(6), 677–691 (1986)

[6]

Cirq Developers: Cirq (2022). https://doi.org/10.5281/zenodo.7465577. http://github.com/quantumlib/Cirq/graphs/contributors

[7]

Fujita, M., McGeer, P.C., Yang, J.C.: Multi-terminal binary decision diagrams: an efficient data structure for matrix representation. Formal Methods Syst. Des. 10(2/3), 149–169 (1997).

[8]

Gray, J.: quimb: a python library for quantum information and many-body calculations. J. Open Source Softw. 3(29), 819 (2018).

[9]

Niemann, P., Wille, R., Miller, D.M., Thornton, M.A., Drechsler, R.: QMDDs: efficient quantum function representation and manipulation. IEEE Trans. Comput. Aided Des. Integr. Circuits Syst. 35(1), 86–99 (2016).

[10]

Roberts, C., et al.: TensorNetwork: a library for physics and machine learning (2019)

[11]

Sistla, M., Chaudhuri, S., Reps, T.: CFLOBDDs: context-free-language ordered binary decision diagrams. arXiv:2211.06818 (2022)

[12]

Somenzi, F.: CUDD: CU decision diagram package-release 2.4.0. University of Colorado at Boulder (2012)

[13]

Tsai, Y.H., Jiang, J.H.R., Jhang, C.S.: Bit-slicing the Hilbert space: scaling up accurate quantum circuit simulation. In: Design Automation Conference (DAC), pp. 439–444 (2021).

[14]

Viamontes, G.F., Markov, I.L., Hayes, J.P.: High-performance QuIDD-based simulation of quantum circuits. In: 2004 Design, Automation and Test in Europe Conference and Exposition (DATE 2004), 16-20 February 2004, Paris, France, pp. 1354–1355. IEEE Computer Society (2004).

[15]

Wegener, I.: Branching programs and binary decision diagrams. SIAM Monographs on Disc. Math. and Appl., Society for Industrial and Applied Mathematics (2000)

[16]

Wille, R., Burgholzer, L., Artner, M.: Visualizing decision diagrams for quantum computing. In: Design, Automation and Test in Europe (2021)

[17]

Zulehner, A., Hillmich, S., Wille, R.: How to efficiently handle complex values? Implementing decision diagrams for quantum computing. International Conference on Computer Aided Design (ICCAD) (2019)

[18]

Zulehner, A., Wille, R.: Advanced simulation of quantum computations. Trans. CAD Integr. Circuit. Syst. 38(5), 848–859 (2019).

[19]

Zulehner, A., Wille, R.: Introducing Design Automation for Quantum Computing. Springer (2020).

Cited By

Fang WYing M(2024)Symbolic Execution for Quantum Error Correction ProgramsProceedings of the ACM on Programming Languages10.1145/36564198:PLDI(1040-1065)Online publication date: 20-Jun-2024
https://dl.acm.org/doi/10.1145/3656419
Mei JBonsangue MLaarman A(2024)Simulating Quantum Circuits by Model CountingComputer Aided Verification10.1007/978-3-031-65633-0_25(555-578)Online publication date: 24-Jul-2024
https://dl.acm.org/doi/10.1007/978-3-031-65633-0_25
Dai AYing M(2024)QReach: A Reachability Analysis Tool for Quantum Markov ChainsComputer Aided Verification10.1007/978-3-031-65633-0_23(520-532)Online publication date: 24-Jul-2024
https://dl.acm.org/doi/10.1007/978-3-031-65633-0_23

Recommendations

A Symbolic Classical Computer Language for Simulation of Quantum Algorithms
QI '09: Proceedings of the 3rd International Symposium on Quantum Interaction

Quantum computing is an extremely promising research combining theoretical and experimental quantum physics, mathematics, quantum information theory and computer science. Classical simulation of quantum computations will cover part of the gap between ...
Digital quantum simulation with Rydberg atoms

We discuss in detail the implementation of an open-system quantum simulator with Rydberg states of neutral atoms held in an optical lattice. Our scheme allows one to realize both coherent as well as dissipative dynamics of complex spin models involving ...
Efficient quantum circuit simulation

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Guide Proceedings

Computer Aided Verification: 35th International Conference, CAV 2023, Paris, France, July 17–22, 2023, Proceedings, Part III

Jul 2023

512 pages

ISBN:978-3-031-37708-2

DOI:10.1007/978-3-031-37709-9

Editors:
Constantin Enea
LIX, Ecole Polytechnique, CNRS and Institut Polytechnique de Paris, Palaiseau, France
,
Akash Lal
Microsoft Research, Bangalore, India

© The Author(s) 2023.

Open Access This chapter is licensed under the terms of the Creative Commons Attribution 4.0 International License (http://creativecommons.org/licenses/by/4.0/), which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons license and indicate if changes were made.The images or other third party material in this chapter are included in the chapter's Creative Commons license, unless indicated otherwise in a credit line to the material. If material is not included in the chapter's Creative Commons license and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder.

Publisher

Springer-Verlag

Berlin, Heidelberg

Publication History

Published: 17 July 2023

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

2
Total Citations
View Citations
0
Total Downloads

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

Reflects downloads up to 16 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Fang WYing M(2024)Symbolic Execution for Quantum Error Correction ProgramsProceedings of the ACM on Programming Languages10.1145/36564198:PLDI(1040-1065)Online publication date: 20-Jun-2024
https://dl.acm.org/doi/10.1145/3656419
Mei JBonsangue MLaarman A(2024)Simulating Quantum Circuits by Model CountingComputer Aided Verification10.1007/978-3-031-65633-0_25(555-578)Online publication date: 24-Jul-2024
https://dl.acm.org/doi/10.1007/978-3-031-65633-0_25
Dai AYing M(2024)QReach: A Reachability Analysis Tool for Quantum Markov ChainsComputer Aided Verification10.1007/978-3-031-65633-0_23(520-532)Online publication date: 24-Jul-2024
https://dl.acm.org/doi/10.1007/978-3-031-65633-0_23

View Options

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

Media

Figures

Other

Tables

View Table of Contents