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

research-article

Symbolic Execution of Hadamard-Toffoli Quantum Circuits

Authors:

Jacques Carette,

Amr SabryAuthors Info & Claims

PEPM 2023: Proceedings of the 2023 ACM SIGPLAN International Workshop on Partial Evaluation and Program Manipulation

Pages 14 - 26

https://doi.org/10.1145/3571786.3573018

Published: 15 January 2023 Publication History

Abstract

The simulation of quantum programs by classical computers is a critical endeavor for several reasons: it provides proof-of-concept validation of quantum algorithms; it provides opportunities to experiment with new programming abstractions suitable for the quantum domain; and most significantly it is a way to explore the elusive boundary at which a quantum advantage may materialize. Here, we show that traditional techniques of symbolic evaluation and partial evaluation yield surprisingly efficient classical simulations for some instances of textbook quantum algorithms that include the Deutsch, Deutsch-Jozsa, Bernstein-Vazirani, Simon, Grover, and Shor's algorithms. The success of traditional partial evaluation techniques in this domain is due to one simple insight: the quantum bits used in these algorithms can be modeled by a symbolic boolean variable while still keeping track of the correlations due to superposition and entanglement. More precisely, the system of constraints generated over the symbolic variables contains all the necessary quantum correlations and hence the answer to the quantum algorithms. With a few programming tricks explained in the paper, quantum circuits with millions of gates can be symbolically executed in seconds. Paradoxically, other circuits with as few as a dozen gates take exponential time. We reflect on the significance of these results in the conclusion.

References

[1]

Alastair A. Abbott. 2012. The Deutsch-Jozsa problem: de-quantization and entanglement. Natural Computing, 11 (2012).

[2]

D. Aharonov. 2003. A simple proof that Toffoli and Hadamard are qauntum universal. arXiv:quant-ph/0301040.

[3]

Yakir Aharonov and Lev Vaidman. 2008. The Two-State Vector Formalism: An Updated Review. Springer Berlin Heidelberg, Berlin, Heidelberg. 399–447. isbn:978-3-540-73473-4 https://doi.org/10.1007/978-3-540-73473-4_13

[4]

Matthew Amy. 2018. Towards Large-scale Functional Verification of Universal Quantum Circuits. In Proceedings 15th International Conference on Quantum Physics and Logic, QPL 2018, Halifax, Canada, 3-7th June 2018, Peter Selinger and Giulio Chiribella (Eds.) (EPTCS, Vol. 287). 1–21. https://doi.org/10.4204/EPTCS.287.1

[5]

Matthew Amy, Martin Roetteler, and Krysta M. Svore. 2017. Verified Compilation of Space-Efficient Reversible Circuits. In Computer Aided Verification, Rupak Majumdar and Viktor Kunčak (Eds.). Springer International Publishing, Cham. 3–21. isbn:978-3-319-63390-9

[6]

Roberto Baldoni, Emilio Coppa, Daniele Cono D’elia, Camil Demetrescu, and Irene Finocchi. 2018. A Survey of Symbolic Execution Techniques. ACM Comput. Surv., 51, 3 (2018), Article 50, may, 39 pages. issn:0360-0300 https://doi.org/10.1145/3182657

Digital Library

[7]

Stephen M. Barnett, John Jeffers, and David T. Pegg. 2021. Quantum Retrodiction: Foundations and Controversies. Symmetry, 13, 4 (2021), issn:2073-8994 https://doi.org/10.3390/sym13040586

[8]

Ethan Bernstein and Umesh Vazirani. 1997. Quantum Complexity Theory. SIAM J. Comput., 26, 5 (1997), 1411–1473. https://doi.org/10.1137/S0097539796300921 arxiv:https://doi.org/10.1137/S0097539796300921.

Digital Library

[9]

Alex Bocharov, Shawn X. Cui, Martin Roetteler, and Krysta M. Svore. 2016. Improved Quantum Ternary Arithmetic. Quantum Info. Comput., 16, 9–10 (2016), jul, 862–884. issn:1533-7146

[10]

Robert S. Boyer, Bernard Elspas, and Karl N. Levitt. 1975. SELECT—a Formal System for Testing and Debugging Programs by Symbolic Execution. SIGPLAN Not., 10, 6 (1975), apr, 234–245. issn:0362-1340 https://doi.org/10.1145/390016.808445

Digital Library

[11]

Daniel E Browne. 2007. Efficient classical simulation of the quantum Fourier transform. New Journal of Physics, 9, 5 (2007), may, 146. https://doi.org/10.1088/1367-2630/9/5/146

[12]

Linda Burnett, William Millan, Edward Dawson, and Andrew Clark. 2004. Simpler Methods for Generating Better Boolean Functions with Good Cryptographic Properties. Australasian Journal of Combinatorics, 29 (2004), 231–247. https://eprints.qut.edu.au/21763/

[13]

Cristian S. Calude. 2007. De-quantizing the solution of Deutsch’s problem. International Journal of Quantum Information, 5, 3 (2007), 409–415.

[14]

Jacques Carette, Oleg Kiselyov, and Chung-chieh Shan. 2009. Finally tagless, partially evaluated: Tagless staged interpreters for simpler typed languages. Journal of Functional Programming, 19, 5 (2009), 509–543.

Digital Library

[15]

Jacques Carette, Gerardo Ortiz, and Amr Sabry. 2022. Retrodictive Quantum Computing. arXiv:2205.06346.

[16]

Lori A. Clarke. 1976. A Program Testing System. In Proceedings of the 1976 Annual Conference (ACM ’76). Association for Computing Machinery, New York, NY, USA. 488–491. isbn:9781450374897 https://doi.org/10.1145/800191.805647

Digital Library

[17]

Stephen A. Cook. 1971. The Complexity of Theorem-Proving Procedures. In Proceedings of the Third Annual ACM Symposium on Theory of Computing (STOC ’71). Association for Computing Machinery, New York, NY, USA. 151–158. isbn:9781450374644 https://doi.org/10.1145/800157.805047

Digital Library

[18]

D. Coppersmith. 2002. An approximate Fourier transform useful in quantum factoring. arXiv:quant-ph/0201067

[19]

David Deutsch. 1985. Quantum theory, the Church–Turing principle and the universal quantum computer. Proc. R. Soc. Lond. A 400.

[20]

David Deutsch and Richard Jozsa. 1992. Rapid solution of problems by quantum computation. Proc. R. Soc. Lond. A 439.

[21]

Johann Makowsky Dorit Aharonov, Zeph Landau. 2006. The quantum FFT can be classically simulated. arXiv:quant-ph/0611156

[22]

Michael R. Geller and Zhongyuan Zhou. 2013. Factoring 51 and 85 with 8 qubits. Scientific Reports (3023), 3, 1 (2013).

[23]

D Gottesman. 1998. The Heisenberg representation of quantum computers. 6, https://www.osti.gov/biblio/319738

[24]

Lov K. Grover. 1996. A Fast Quantum Mechanical Algorithm for Database Search. In Proceedings of the Twenty-Eighth Annual ACM Symposium on Theory of Computing (STOC ’96). Association for Computing Machinery, New York, NY, USA. 212–219. isbn:0897917855 https://doi.org/10.1145/237814.237866

Digital Library

[25]

William E. Howden. 1976. Experiments with a symbolic evaluation system. In Proceedings of the National Computer Conference.

Digital Library

[26]

Richard Jozsa and Noah Linden. 2003. On the Role of Entanglement in Quantum-Computational Speed-Up. Proceedings: Mathematical, Physical and Engineering Sciences, 459, 2036 (2003), 2011–2032. issn:13645021 http://www.jstor.org/stable/3560059

[27]

Richard M. Karp. 1972. Reducibility among Combinatorial Problems. Springer US, Boston, MA. 85–103. isbn:978-1-4684-2001-2 https://doi.org/10.1007/978-1-4684-2001-2_9

[28]

James C. King. 1976. Symbolic Execution and Program Testing. Commun. ACM, 19, 7 (1976), jul, 385–394. issn:0001-0782 https://doi.org/10.1145/360248.360252

Digital Library

[29]

Ilan Komargodski, Moni Naor, and Eylon Yogev. 2019. White-Box vs. Black-Box Complexity of Search Problems: Ramsey and Graph Property Testing. J. ACM, 66, 5 (2019), Article 34, jul, 28 pages. issn:0004-5411 https://doi.org/10.1145/3341106

Digital Library

[30]

Liyi Li, Finn Voichick, Kesha Hietala, Yuxiang Peng, Xiaodi Wu, and Michael Hicks. 2022. Verified Compilation of Quantum Oracles. Proc. ACM Program. Lang., 6, OOPSLA2 (2022), Article 146, oct, 27 pages. https://doi.org/10.1145/3563309

Digital Library

[31]

Torben Æ gidius Mogensen. 2011. Partial Evaluation of the Reversible Language Janus. In Proceedings of the 20th ACM SIGPLAN Workshop on Partial Evaluation and Program Manipulation (PEPM ’11). Association for Computing Machinery, New York, NY, USA. 23–32. isbn:9781450304856 https://doi.org/10.1145/1929501.1929506

Digital Library

[32]

Michael A. Nielsen and Isaac L. Chuang. 2010. Quantum Computation and Quantum Information: 10th Anniversary Edition. Cambridge University Press. https://doi.org/10.1017/CBO9780511976667

[33]

David Lorge Parnas and Paul C Clements. 1986. A rational design process: How and why to fake it. IEEE transactions on software engineering, 251–257.

[34]

Peter W. Shor. 1997. Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer. SIAM J. Comput., 26, 5 (1997), 1484–1509. https://doi.org/10.1137/S0097539795293172 arxiv:https://doi.org/10.1137/S0097539795293172.

Digital Library

[35]

D.R. Simon. 1994. On the power of quantum computation. In Proceedings 35th Annual Symposium on Foundations of Computer Science. 116–123. https://doi.org/10.1109/SFCS.1994.365701

Digital Library

[36]

Mathias Soeken, Gerhard W Dueck, and D Michael Miller. 2016. A fast symbolic transformation based algorithm for reversible logic synthesis. In International Conference on Reversible Computation. 307–321.

[37]

Natalia Tokareva. 2015. Chapter 1 - Boolean Functions. In Bent Functions, Natalia Tokareva (Ed.). Academic Press, Boston. 1–15. isbn:978-0-12-802318-1 https://doi.org/10.1016/B978-0-12-802318-1.00001-7

[38]

B.A. Trakhtenbrot. 1984. A Survey of Russian Approaches to Perebor (Brute-Force Searches) Algorithms. Annals of the History of Computing, 6, 4 (1984), 384–400. https://doi.org/10.1109/MAHC.1984.10036

Digital Library

[39]

Maarten Van Den Nest. 2013. Efficient Classical Simulations of Quantum Fourier Transforms and Normalizer Circuits over Abelian Groups. Quantum Info. Comput., 13, 11–12 (2013), nov, 1007–1037. issn:1533-7146

[40]

Vlatko Vedral, Adriano Barenco, and Artur Ekert. 1996. Quantum networks for elementary arithmetic operations. Phys. Rev. A, 54 (1996), Jul, 147–153. https://doi.org/10.1103/PhysRevA.54.147

[41]

Satosi Watanabe. 1955. Symmetry of Physical Laws. Part III. Prediction and Retrodiction. Rev. Mod. Phys., 27 (1955), Apr, 179–186. https://doi.org/10.1103/RevModPhys.27.179

[42]

Ingo Wegener. 1987. The Complexity of Boolean Functions. John Wiley & Sons, Inc., USA. isbn:0471915556

[43]

Nadav Yoran and Anthony J. Short. 2007. Efficient classical simulation of the approximate quantum Fourier transform. Phys. Rev. A, 76 (2007), Oct, 042321. https://doi.org/10.1103/PhysRevA.76.042321

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
Normann LGlück RKeller GWang M(2024)Partial Evaluation of Reversible Flowchart ProgramsProceedings of the 2024 ACM SIGPLAN International Workshop on Partial Evaluation and Program Manipulation10.1145/3635800.3636967(119-133)Online publication date: 11-Jan-2024
https://dl.acm.org/doi/10.1145/3635800.3636967

Index Terms

Symbolic Execution of Hadamard-Toffoli Quantum Circuits

Recommendations

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 ...
Construction of quantum gates for concatenated Greenberger---Horne---Zeilinger-type logic qubit

Concatenated Greenberger---Horne---Zeilinger (C-GHZ) state is a kind of logic qubit which is robust in noisy environment. In this paper, we encode the C-GHZ state as the logic qubit and design two kinds of quantum gates for such logic qubit. The first ...
Teleportation-based quantum computation, extended Temperley---Lieb diagrammatical approach and Yang---Baxter equation

This paper focuses on the study of topological features in teleportation-based quantum computation and aims at presenting a detailed review on teleportation-based quantum computation (Gottesman and Chuang in Nature 402: 390, 1999). In the extended ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

PEPM 2023: Proceedings of the 2023 ACM SIGPLAN International Workshop on Partial Evaluation and Program Manipulation

January 2023

65 pages

ISBN:9798400700118

DOI:10.1145/3571786

General Chairs:
Edwin Brady
University of St Andrews, UK
,
Jens Palsberg
University of California at Los Angeles, USA

Copyright © 2023 Owner/Author.

Permission to make digital or hard copies of part or all of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for third-party components of this work must be honored. For all other uses, contact the Owner/Author.

Sponsors

SIGPLAN: ACM Special Interest Group on Programming Languages

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 15 January 2023

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Badges

Artifacts Available / v1.1

Author Tags

Qualifiers

Research-article

Conference

POPL '23

Sponsor:

SIGPLAN

POPL '23: The 50th Annual ACM SIGPLAN Symposium on Principles of Programming Languages

January 16 - 17, 2023

MA, Boston, USA

Acceptance Rates

Overall Acceptance Rate 66 of 120 submissions, 55%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

2
Total Citations
View Citations
183
Total Downloads

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

Reflects downloads up to 02 Mar 2025

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
Normann LGlück RKeller GWang M(2024)Partial Evaluation of Reversible Flowchart ProgramsProceedings of the 2024 ACM SIGPLAN International Workshop on Partial Evaluation and Program Manipulation10.1145/3635800.3636967(119-133)Online publication date: 11-Jan-2024
https://dl.acm.org/doi/10.1145/3635800.3636967

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.

Figures

Tables

Media

View Table of Conten