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

research-article

Silq: a high-level quantum language with safe uncomputation and intuitive semantics

Authors:

Benjamin Bichsel,

Maximilian Baader,

Martin VechevAuthors Info & Claims

PLDI 2020: Proceedings of the 41st ACM SIGPLAN Conference on Programming Language Design and Implementation

Pages 286 - 300

https://doi.org/10.1145/3385412.3386007

Published: 11 June 2020 Publication History

Abstract

Existing quantum languages force the programmer to work at a low level of abstraction leading to unintuitive and cluttered code. A fundamental reason is that dropping temporary values from the program state requires explicitly applying quantum operations that safely uncompute these values.

We present Silq, the first quantum language that addresses this challenge by supporting safe, automatic uncomputation. This enables an intuitive semantics that implicitly drops temporary values, as in classical computation. To ensure physicality of Silq's semantics, its type system leverages novel annotations to reject unphysical programs.

Our experimental evaluation demonstrates that Silq programs are not only easier to read and write, but also significantly shorter than equivalent programs in other quantum languages (on average -46% for Q#, -38% for Quipper), while using only half the number of quantum primitives.

References

[1]

Matthew Amy, Martin Roetteler, and Krysta M. Svore. 2017. Verified Compilation of Space-Efficient Reversible Circuits. In CAV’17. Vol. 10427. Cham, 3–21.

[2]

Charles H Bennett. 1973. Logical Reversibility of Computation. IBM Journal of Research and Development 17, 6 (Nov. 1973), 525–532.

Digital Library

[3]

Andrew M. Childs and Robin Kothari. 2011. Quantum query complexity of minor-closed graph properties. In STACS’11 (Dagstuhl, Germany, 2011) (Leibniz International Proceedings in Informatics (LIPIcs)), Vol. 9. 661–672.

[4]

Vedran Dunjko, Jacob M. Taylor, and Hans J. Briegel. 2016. Quantum-Enhanced Machine Learning. Physical Review Letters 117, 13 (Sept. 2016).

[5]

Timon Gehr, Sasa Misailovic, and Martin Vechev. 2016. Psi: Exact symbolic inference for probabilistic programs. In CAV’16. 62–83.

[6]

Alexander S. Green, Peter LeFanu Lumsdaine, Neil J. Ross, Peter Selinger, and Benoît Valiron. 2013. Quipper: a scalable quantum programming language. In PLDI’13. ACM Press, Seattle, Washington, USA.

Digital Library

[7]

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. ACM, 212–219.

Digital Library

[8]

Aram W. Harrow, Avinatan Hassidim, and Seth Lloyd. 2009. Quantum Algorithm for Linear Systems of Equations. Phys. Rev. Lett. 103 (Oct 2009), 150502. Issue 15. 150502

[9]

Steve Klabnik and Carol Nichols. 2018. The Rust programming language. No Starch Press, San Francisco.

[10]

Emmanuel Knill. 1996. Conventions for quantum pseudocode. Technical Report. Citeseer.

[11]

Seth Lloyd, Masoud Mohseni, and Patrick Rebentrost. 2014. Quantum principal component analysis. Nature Physics 10, 9 (July 2014), 631–633.

[12]

Guang Hao Low, Theodore J. Yoder, and Isaac L. Chuang. 2014. Quantum inference on Bayesian networks. Phys. Rev. A 89, 6 (June 2014), 062315.

[13]

F. Magniez, M. Santha, and M. Szegedy. 2007. Quantum Algorithms for the Triangle Problem. 37, 2 (2007), 413–424. 1137/050643684

Digital Library

[14]

Microsoft. 2018. Public submissions of the Microsoft Q# Coding Contest - Summer 2018. (2018).

[15]

https://codeforces.com/contest/1002/

[16]

Microsoft. 2019. Public submissions of the Microsoft Q# Coding Contest - Winter 2019. (2019).

[17]

https://codeforces.com/contest/1116/

[18]

Mariia Mykhailova and Martin Roetteler. 2018. Microsoft Q# Coding Contest - Summer 2018 - Main Contest July 6-9, 2018. (2018).

[19]

https: //assets.codeforces.com/rounds/997-998/main-contest-editorial.pdf

[20]

Mariia Mykhailova and Martin Roetteler. 2019. Microsoft Q# Coding Contest - Winter 2019 - Main Contest March 1-4, 2019. (2019).

[21]

https: //assets.codeforces.com/rounds/1116/contest-editorial.pdf

[22]

Peter Müller and Arnd Poetzsch-Heffter. 1999. Universes: a type system for controlling representation exposure.

[23]

Daniel Nagaj, Or Sattath, Aharon Brodutch, and Dominique Unruh. 2016. An Adaptive Attack on Wiesner’s Quantum Money. Quantum Info. Comput. 16, 11-12 (Sept. 2016), 1048–1070. http://dl.acm.org/ citation.cfm?id=3179330.3179337

[24]

Michael A. Nielsen and Isaac L. Chuang. 2010. Quantum computation and quantum information (10th anniversary ed ed.). Cambridge University Press, Cambridge ; New York.

Digital Library

[25]

Jennifer Paykin, Robert Rand, and Steve Zdancewic. 2017. QWIRE: a core language for quantum circuits. In POPL’17. ACM Press, Paris, France.

Digital Library

[26]

Robert Rand, Jennifer Paykin, Dong-Ho Lee, and Steve Zdancewic. 2019. ReQWIRE: Reasoning about Reversible Quantum Circuits. Electronic Proceedings in Theoretical Computer Science 287 (Jan. 2019), 299– 312. arXiv: 1901.10118.

[27]

Patrick Rebentrost, M Mohseni, and Seth Lloyd. 2013. Quantum Support Vector Machine for Big Data Classification. Physical Review Letters 113 (2013).

[28]

Steven Roman. 2008. Advanced Linear Algebra. New York, NY. http: //site.ebrary.com/id/10230315 OCLC: 730328666.

[29]

Neil J. Ross and Peter LeFanu Lumsdaine. 2015. Algorithms.TF.Main. https://www.mathstat.dal.ca/~selinger/quipper/doc/Algorithms-TFMain.html.

[30]

Peter Selinger. 2004. Towards a Quantum Programming Language. Mathematical. Structures in Comp. Sci. 14, 4 (Aug. 2004), 527–586.

Digital Library

[31]

Peter Selinger and Benoit Valiron. 2006. A lambda calculus for quantum computation with classical control. Mathematical Structures in Computer Science 16, 03 (June 2006), 527. S0960129506005238

Digital Library

[32]

Damian S. Steiger, Thomas Häner, and Matthias Troyer. 2018. ProjectQ: an open source software framework for quantum computing. Quantum 2 (Jan. 2018), 49.

[33]

Krysta Svore, Martin Roetteler, Alan Geller, Matthias Troyer, John Azariah, Christopher Granade, Bettina Heim, Vadym Kliuchnikov, Mariia Mykhailova, and Andres Paz. 2018. Q#: Enabling Scalable Quantum Computing and Development with a High-level DSL. In Proceedings of the Real World Domain Specific Languages Workshop 2018 on - RWDSL2018. ACM Press, Vienna, Austria. 1145/3183895.3183901

Digital Library

[34]

Google AI Quantum Team. 2017. Cirq. (2017). https://github.com/ quantumlib/Cirq

[35]

Dave Wecker and Krysta M Svore. 2014. LIQUi|>: A software design architecture and domain-specific language for quantum computing. arXiv preprint arXiv:1402.4467 (2014).

[36]

Nathan Wiebe, Daniel Braun, and Seth Lloyd. 2012. Quantum Algorithm for Data Fitting. Physical Review Letters 109, 5 (Aug. 2012).

[37]

Stephen Wiesner. 1983. Conjugate Coding. SIGACT News 15, 1 (Jan. 1983), 78–88.

Digital Library

Cited By

Venev HGehr TDimitrov DVechev M(2024)Modular Synthesis of Efficient Quantum UncomputationProceedings of the ACM on Programming Languages10.1145/36897858:OOPSLA2(2097-2124)Online publication date: 8-Oct-2024
https://dl.acm.org/doi/10.1145/3689785
Jeon SCho KKang CLee JOh HKang J(2024)Quantum Probabilistic Model Checking for Time-Bounded PropertiesProceedings of the ACM on Programming Languages10.1145/36897318:OOPSLA2(557-587)Online publication date: 8-Oct-2024
https://dl.acm.org/doi/10.1145/3689731
Kang CLee JOh H(2024)Statistical Testing of Quantum Programs via Fixed-Point Amplitude AmplificationProceedings of the ACM on Programming Languages10.1145/36897168:OOPSLA2(140-164)Online publication date: 8-Oct-2024
https://dl.acm.org/doi/10.1145/3689716
Show More Cited By

Index Terms

Silq: a high-level quantum language with safe uncomputation and intuitive semantics
1. Computer systems organization
  1. Architectures
    1. Other architectures
      1. Quantum computing
2. Software and its engineering
  1. Software notations and tools
    1. Formal language definitions
    2. General programming languages
      1. Language features

Recommendations

Unqomp: synthesizing uncomputation in Quantum circuits
PLDI 2021: Proceedings of the 42nd ACM SIGPLAN International Conference on Programming Language Design and Implementation

A key challenge when writing quantum programs is the need for uncomputation: temporary values produced during the computation must be reset to zero before they can be safely discarded. Unfortunately, most existing quantum languages require tedious ...
A program transformation and architecture support for quantum uncomputation
ASPLOS XII: Proceedings of the 12th international conference on Architectural support for programming languages and operating systems

Quantum computing's power comes from new algorithms that exploit quantum mechanical phenomena for computation. Quantum algorithms are different from their classical counterparts in that quantum algorithms rely on algorithmic structures that are simply ...
A program transformation and architecture support for quantum uncomputation
Proceedings of the 2006 ASPLOS Conference

Quantum computing's power comes from new algorithms that exploit quantum mechanical phenomena for computation. Quantum algorithms are different from their classical counterparts in that quantum algorithms rely on algorithmic structures that are simply ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

PLDI 2020: Proceedings of the 41st ACM SIGPLAN Conference on Programming Language Design and Implementation

June 2020

1174 pages

ISBN:9781450376136

DOI:10.1145/3385412

General Chair:
Alastair F. Donaldson
Imperial College London, UK
,
Program Chair:
Emina Torlak
University of Washington, USA

Copyright © 2020 ACM.

Permission to make digital or hard copies of all or part 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 components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].

Sponsors

SIGPLAN: ACM Special Interest Group on Programming Languages

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 11 June 2020

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Badges

Author Tags

Qualifiers

Research-article

Conference

PLDI '20

Sponsor:

SIGPLAN

PLDI '20: 41st ACM SIGPLAN International Conference on Programming Language Design and Implementation

June 15 - 20, 2020

London, UK

Acceptance Rates

Overall Acceptance Rate 406 of 2,067 submissions, 20%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

100
Total Citations
View Citations
3,303
Total Downloads

Downloads (Last 12 months)202
Downloads (Last 6 weeks)31

Reflects downloads up to 10 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Venev HGehr TDimitrov DVechev M(2024)Modular Synthesis of Efficient Quantum UncomputationProceedings of the ACM on Programming Languages10.1145/36897858:OOPSLA2(2097-2124)Online publication date: 8-Oct-2024
https://dl.acm.org/doi/10.1145/3689785
Jeon SCho KKang CLee JOh HKang J(2024)Quantum Probabilistic Model Checking for Time-Bounded PropertiesProceedings of the ACM on Programming Languages10.1145/36897318:OOPSLA2(557-587)Online publication date: 8-Oct-2024
https://dl.acm.org/doi/10.1145/3689731
Kang CLee JOh H(2024)Statistical Testing of Quantum Programs via Fixed-Point Amplitude AmplificationProceedings of the ACM on Programming Languages10.1145/36897168:OOPSLA2(140-164)Online publication date: 8-Oct-2024
https://dl.acm.org/doi/10.1145/3689716
Wright CLuján MPetoumenos PGoodacre JErtl MKirsch C(2024)Quff: A Dynamically Typed Hybrid Quantum-Classical Programming LanguageProceedings of the 21st ACM SIGPLAN International Conference on Managed Programming Languages and Runtimes10.1145/3679007.3685063(65-81)Online publication date: 13-Sep-2024
https://dl.acm.org/doi/10.1145/3679007.3685063
Carette JHeunen CKaarsgaard RSabry A(2024)How to Bake a Quantum ΠProceedings of the ACM on Programming Languages10.1145/36746258:ICFP(1-29)Online publication date: 15-Aug-2024
https://dl.acm.org/doi/10.1145/3674625
Paltenghi MPradel M(2024)Analyzing Quantum Programs with LintQ: A Static Analysis Framework for QiskitProceedings of the ACM on Software Engineering10.1145/36608021:FSE(2144-2166)Online publication date: 12-Jul-2024
https://dl.acm.org/doi/10.1145/3660802
Yuan CCarbin M(2024)The T-Complexity Costs of Error Correction for Control Flow in Quantum ComputationProceedings of the ACM on Programming Languages10.1145/36563978:PLDI(492-517)Online publication date: 20-Jun-2024
https://dl.acm.org/doi/10.1145/3656397
Long PZhao J(2024)Testing Multi-Subroutine Quantum Programs: From Unit Testing to Integration TestingACM Transactions on Software Engineering and Methodology10.1145/365633933:6(1-61)Online publication date: 27-Jun-2024
https://dl.acm.org/doi/10.1145/3656339
Yuan CVillanyi ACarbin M(2024)Quantum Control Machine: The Limits of Control Flow in Quantum ProgrammingProceedings of the ACM on Programming Languages10.1145/36498118:OOPSLA1(1-28)Online publication date: 29-Apr-2024
https://dl.acm.org/doi/10.1145/3649811
Varga TAragonés-Soria YOriol M(2024)Quantum types: going beyond qubits and quantum gatesProceedings of the 5th ACM/IEEE International Workshop on Quantum Software Engineering10.1145/3643667.3648225(49-52)Online publication date: 16-Apr-2024
https://dl.acm.org/doi/10.1145/3643667.3648225
Show More Cited By

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