Reqomp: Space-constrained Uncomputation for Quantum Circuits

Reqomp: Space-constrained Uncomputation for Quantum Circuits

Time Stamp: February 19, 2024 5:26 AM
Reqomp: Space-constrained Uncomputation for Quantum Circuits PlatoBlockchain Data Intelligence. Vertical Search. Ai.

Anouk Paradis, Benjamin Bichsel, and Martin Vechev

ETH Zurich, Switzerland

Find this paper interesting or want to discuss? Scite or leave a comment on SciRate.

Abstract

Quantum circuits must run on quantum computers with tight limits on qubit and gate counts. To generate circuits respecting both limits, a promising opportunity is exploiting $uncomputation$ to trade qubits for gates. We present Reqomp, a method to automatically synthesize correct and efficient uncomputation of ancillae while respecting hardware constraints. For a given circuit, Reqomp can offer a wide range of trade-offs between tightly constraining qubit count or gate count. Our evaluation demonstrates that Reqomp can significantly reduce the number of required ancilla qubits by up to 96%. On 80% of our benchmarks, the ancilla qubits required can be reduced by at least 25% while never incurring a gate count increase beyond 28%.

► BibTeX data

► References

[1] Anouk Paradis, Benjamin Bichsel, Samuel Steffen, and Martin Vechev. “Unqomp: synthesizing uncomputation in Quantum circuits”. In Proceedings of the 42nd ACM SIGPLAN International Conference on Programming Language Design and Implementation. Pages 222–236. Association for Computing Machinery, New York, NY, USA (2021).
https:/​/​doi.org/​10.1145/​3453483.3454040

[2] Yongshan Ding, Xin-Chuan Wu, Adam Holmes, Ash Wiseth, Diana Franklin, Margaret Martonosi, and Frederic T. Chong. “Square: Strategic quantum ancilla reuse for modular quantum programs via cost-effective uncomputation”. In 2020 ACM/​IEEE 47th Annual International Symposium on Computer Architecture (ISCA). Pages 570–583. IEEE (2020).
https:/​/​doi.org/​10.1109/​ISCA45697.2020.00054

[3] Benjamin Bichsel, Maximilian Baader, Timon Gehr, and Martin Vechev. “Silq: A High-level Quantum Language with Safe Uncomputation and Intuitive Semantics”. In Proceedings of the 41st ACM SIGPLAN Conference on Programming Language Design and Implementation. Pages 286–300. PLDI 2020New York, NY, USA (2020). Association for Computing Machinery.
https:/​/​doi.org/​10.1145/​3385412.3386007

[4] Robert Rand, Jennifer Paykin, Dong-Ho Lee, and Steve Zdancewic. “ReQWIRE: Reasoning about Reversible Quantum Circuits”. Electronic Proceedings in Theoretical Computer Science 287, 299–312 (2019).
https:/​/​doi.org/​10.4204/​EPTCS.287.17

[5] Emanuel Knill. “An analysis of Bennett’s pebble game”. Technical Report arXiv:math/​9508218. arXiv (1995).
https:/​/​doi.org/​10.48550/​arXiv.math/​9508218
arXiv:math/9508218

[6] Siu Man Chan, Massimo Lauria, Jakob Nordstrom, and Marc Vinyals. “Hardness of approximation in pspace and separation results for pebble games”. In 2015 IEEE 56th Annual Symposium on Foundations of Computer Science. Pages 466–485. (2015).
https:/​/​doi.org/​10.1109/​focs.2015.36

[7] Alexander S. Green, Peter LeFanu Lumsdaine, Neil J. Ross, Peter Selinger, and Benoît Valiron. “Quipper: A scalable quantum programming language”. In Proceedings of the 34th ACM SIGPLAN Conference on Programming Language Design and Implementation. Page 333–342. PLDI ’13New York, NY, USA (2013). Association for Computing Machinery.
https:/​/​doi.org/​10.1145/​2491956.2462177

[8] Alex Parent, Martin Roetteler, and Krysta M. Svore. “Reversible circuit compilation with space constraints”. Technical Report arXiv:1510.00377. arXiv (2015).
https:/​/​doi.org/​10.48550/​arXiv.1510.00377
arXiv:1510.00377

[9] Alex Parent, Martin Roetteler, and Krysta M. Svore. “REVS: A Tool for Space-Optimized Reversible Circuit Synthesis”. In Iain Phillips and Hafizur Rahaman, editors, Reversible Computation. Pages 90–101. Lecture Notes in Computer ScienceCham (2017). Springer International Publishing.
https:/​/​doi.org/​10.1007/​978-3-319-59936-6_7

[10] Debjyoti Bhattacharjee, Mathias Soeken, Srijit Dutta, Anupam Chattopadhyay, and Giovanni De Micheli. “Reversible Pebble Games for Reducing Qubits in Hierarchical Quantum Circuit Synthesis”. In 2019 IEEE 49th International Symposium on Multiple-Valued Logic (ISMVL). Pages 102–107. (2019).
https:/​/​doi.org/​10.1109/​ISMVL.2019.00026

[11] Giulia Meuli, Mathias Soeken, Martin Roetteler, Nikolaj Bjorner, and Giovanni De Micheli. “Reversible pebbling game for quantum memory management”. In 2019 Design, Automation & Test in Europe Conference & Exhibition (DATE). Pages 288–291. IEEE (2019).
https:/​/​doi.org/​10.23919/​date.2019.8715092

[12] Charles H. Bennett. “Time/​Space Trade-Offs for Reversible Computation”. SIAM Journal on Computing 18, 766–776 (1989).
https:/​/​doi.org/​10.1137/​0218053

[13] Krysta Svore, Alan Geller, Matthias Troyer, John Azariah, Christopher Granade, Bettina Heim, Vadym Kliuchnikov, Mariia Mykhailova, Andres Paz, and Martin Roetteler. “Q#: Enabling scalable quantum computing and development with a high-level dsl”. In Proceedings of the Real World Domain Specific Languages Workshop 2018. RWDSL2018New York, NY, USA (2018). Association for Computing Machinery.
https:/​/​doi.org/​10.1145/​3183895.3183901

[14] Matthew Amy, Martin Roetteler, and Krysta M. Svore. “Verified Compilation of Space-Efficient Reversible Circuits”. In Rupak Majumdar and Viktor Kunčak, editors, Computer Aided Verification. Volume 10427, pages 3–21. Springer International Publishing, Cham (2017).
https:/​/​doi.org/​10.1007/​978-3-319-63390-9_1

Cited by

This Paper is published in Quantum under the Creative Commons Attribution 4.0 International (CC BY 4.0) license. Copyright remains with the original copyright holders such as the authors or their institutions.

Time Stamp:

More from Quantum Journal