Pith. sign in

REVIEW 45 references

Automated Auxiliary Qubit Allocation in High-Level Quantum Programming

Not yet reviewed by Pith; the record is open.

Re-run · record.json Download PDF Read on arXiv ↗

This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.

SPECIMEN: schema-true, not a live event

T0 review · schema-true

One-sentence machine reading of the paper's core claim.

pith:XXXXXXXX · record.json · timestamp

arxiv 2412.20543 v1 pith:MQYVT3EZ submitted 2024-12-29 quant-ph cs.PL

Evandro C. R. Rosa , Jerusa Marchi , Eduardo I. Duzzioni , Rafael de Santiago This is my paper · ORCID
classification quant-phcs.PL
keywords quantumauxiliarygatesprogrammingqubitsallocationcircuitcnot
verification ladder T0 review T1 audit T2 compute T3 formal
0 comments
abstract

We present a method for optimizing quantum circuit compilation by automating the allocation of auxiliary qubits for multi-qubit gate decompositions. This approach is implemented and evaluated within the high-level quantum programming platform Ket. Our results indicate that the decomposition of multi-qubit gates is more effectively handled by the compiler, which has access to all circuit parameters, rather than through a quantum programming API. To evaluate the approach, we compared our implementation against Qiskit, a widely used quantum programming platform, by analyzing two quantum algorithms. Using a 16-qubit QPU, we observed a reduction of 87% in the number of CNOT gates in Grover's algorithm for 9 qubits. For a state preparation algorithm with 7 qubits, the number of CNOT gates was reduced from $2.8\times10^7$ to $5.7\times10^3$, leveraging additional Ket optimizations for high-level quantum program constructions. Overall, a quadratic reduction in the number of CNOT gates in the final circuit was observed, with greater improvements achieved when more auxiliary qubits were available. These findings underscore the importance of automatic resource management, such as auxiliary qubit allocation, in optimizing quantum applications and improving their suitability for near-term quantum hardware.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

45 extracted references · 3 canonical work pages

  1. [1]

    Morgan Kaufmann/Elsevier, Amsterdam Boston Heidelberg London New York Oxford Paris San Diego San Fran- cisco Singapore Sydney Tokyo, fourth edition edition, 2016

    Michael Lee Scott.Programming Language Pragmatics. Morgan Kaufmann/Elsevier, Amsterdam Boston Heidelberg London New York Oxford Paris San Diego San Fran- cisco Singapore Sydney Tokyo, fourth edition edition, 2016. ISBN 978-0-12-410409-9

    2016

  2. [2]

    Q#: Enabling Scalable Quantum Computing and Development with a High- level DSL

    Krysta Svore, Alan Geller, Matthias Troyer, John Azariah, Christopher Granade, Bet- tina Heim, Vadym Kliuchnikov, Mariia Mykhailova, Andres Paz, and Martin Roet- teler. Q#: Enabling Scalable Quantum Computing and Development with a High- level DSL. In Proceedings of the Real World Domain Specific Languages Workshop 20 2018, pages 1–10, Vienna Austria, Feb...

    arXiv 2018

  3. [3]

    Qubit allocation

    Marcos Yukio Siraichi, Vinícius Fernandes Dos Santos, Caroline Collange, and Fer- nando Magno Quintao Pereira. Qubit allocation. In Proceedings of the 2018 Inter- national Symposium on Code Generation and Optimization, pages 113–125, Vienna Austria, February 2018. ACM. ISBN 978-1-4503-5617-6. DOI: 10.1145/3168822. URL https://dl.acm.org/doi/10.1145/3168822

    doi:10.1145/3168822 2018

  4. [4]

    Ket Quantum Pro- gramming

    Evandro Chagas Ribeiro Da Rosa and Rafael De Santiago. Ket Quantum Pro- gramming. ACM Journal on Emerging Technologies in Computing Systems, 18(1): 1–25, January 2022. ISSN 1550-4832, 1550-4840. DOI: 10.1145/3474224. URL https://dl.acm.org/doi/10.1145/3474224

    doi:10.1145/3474224 2022

  5. [5]

    Aho, editor.Compilers: Principles, Techniques, & Tools

    Alfred V. Aho, editor.Compilers: Principles, Techniques, & Tools. Pearson/Addison Wesley, Boston, 2nd ed edition, 2007. ISBN 978-0-321-48681-3

    2007

  6. [6]

    da Silva and Daniel K

    Adenilton J. da Silva and Daniel K. Park. Linear-depth quantum circuits for mul- tiqubit controlled gates. Physical Review A, 106(4):042602, October 2022. ISSN 2469-9926, 2469-9934. DOI: 10.1103/PhysRevA.106.042602. URL http://arxiv. org/abs/2203.11882

    arXiv 2022

  7. [7]

    Introduction to Uni- versalQCompiler, 2019

    Raban Iten, Oliver Reardon-Smith, Emanuel Malvetti, Luca Mondada, Gabrielle Pau- vert, Ethan Redmond, Ravjot Singh Kohli, and Roger Colbeck. Introduction to Uni- versalQCompiler, 2019. URLhttps://arxiv.org/abs/1904.01072

    arXiv 2019

  8. [8]

    Evandro C. R. Rosa, Eduardo I. Duzzioni, and Rafael de Santiago. Optimizing Gate Decomposition for High-Level Quantum Programming, June 2024. URL http:// arxiv.org/abs/2406.05581

    arXiv 2024

Show all 45 references
  1. [9]

    Azevedo, Ismael C

    Rafaella Vale, Thiago Melo D. Azevedo, Ismael C. S. Araújo, Israel F. Araujo, and Adenilton J. Da Silva. Circuit Decomposition of Multicontrolled Special Uni- tary Single-Qubit Gates. IEEE Transactions on Computer-Aided Design of Inte- grated Circuits and Systems, 43(3):802–81...

    2024

  2. [10]

    Bennett, Richard Cleve, David P

    Adriano Barenco, Charles H. Bennett, Richard Cleve, David P. DiVincenzo, Nor- man Margolus, Peter Shor, Tycho Sleator, John A. Smolin, and Harald Weinfurter. Elementary gates for quantum computation. Physical Review A, 52(5):3457–3467, November 1995. ISSN 1050-2947, 1094-1622....

    1995 doi

  3. [11]

    Quantum circuits for isometries.Physical Review A, 93(3):032318, March 2016

    RabanIten, RogerColbeck, IvanKukuljan, JonathanHome, andMatthiasChristandl. Quantum circuits for isometries.Physical Review A, 93(3):032318, March 2016. ISSN 2469-9926, 2469-9934. DOI: 10.1103/PhysRevA.93.032318. URLhttps://link.aps. org/doi/10.1103/PhysRevA.93.032318

    2016 doi

  4. [12]

    Qubit Allocation Strategies in Quantum Computing for Improved Computational Efficiency

    Sohini Chowdhury, Rupali Gill, Arti Badhoutiya, Arun Pratap Srivastava, Akhilesh Kumar Khan, and Rajesh Singh. Qubit Allocation Strategies in Quantum Computing for Improved Computational Efficiency. In 2024 4th In- ternational Conference on Innovative Practices in Technology a...

    2024

  5. [13]

    Tackling the Qubit Mapping Problem for NISQ-Era Quantum Devices

    Gushu Li, Yufei Ding, and Yuan Xie. Tackling the Qubit Mapping Problem for NISQ-Era Quantum Devices. InProceedings of the Twenty-Fourth International Con- ference on Architectural Support for Programming Languages and Operating Systems, 21 pages 1001–1014, Providence RI USA, A...

    2019

  6. [14]

    A Hardware-Aware Heuristic for the Qubit Mapping Problem in the NISQ Era

    Siyuan Niu, Adrien Suau, Gabriel Staffelbach, and Aida Todri-Sanial. A Hardware-Aware Heuristic for the Qubit Mapping Problem in the NISQ Era. IEEE Transactions on Quantum Engineering , 1:1–14, 2020. ISSN 2689-1808. DOI: 10.1109/TQE.2020.3026544. URLhttps://ieeexplore.ieee.org...

    2020

  7. [15]

    MQT QMAP: Efficient Quantum Circuit Map- ping

    Robert Wille and Lukas Burgholzer. MQT QMAP: Efficient Quantum Circuit Map- ping. In Proceedings of the 2023 International Symposium on Physical Design , pages 198–204, Virtual Event USA, March 2023. ACM. ISBN 978-1-4503-9978-4. DOI: 10.1145/3569052.3578928. URLhttps://dl.acm....

    2023

  8. [16]

    A Dynamic Look-Ahead Heuris- tic for the Qubit Mapping Problem of NISQ Computers

    Pengcheng Zhu, Zhijin Guan, and Xueyun Cheng. A Dynamic Look-Ahead Heuris- tic for the Qubit Mapping Problem of NISQ Computers. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 39(12):4721–4735, De- cember 2020. ISSN 0278-0070, 1937-4151. DOI: 10....

    2020

  9. [17]

    A Variation-Aware Quantum Circuit Mapping Approach Based on Multi-Agent Cooperation

    Pengcheng Zhu, Weiping Ding, Lihua Wei, Xueyun Cheng, Zhijin Guan, and Shiguang Feng. A Variation-Aware Quantum Circuit Mapping Approach Based on Multi-Agent Cooperation. IEEE Transactions on Computers, 72(8):2237–2249, August 2023. ISSN 0018-9340, 1557-9956, 2326-3814. DOI: 1...

    2023

  10. [18]

    Calibrating single-qubit gates by a two-dimensional Rabi oscillation

    You Huang, Mohammad T Amawi, Francesco Poggiali, Fazhan Shi, Jiangfeng Du, and Friedemann Reinhard. Calibrating single-qubit gates by a two-dimensional Rabi oscillation. AIP Advances, 13(3):035226, March 2023. ISSN 2158-3226. DOI:10.1063/5.0139454. URL https://pubs.aip.org/adv...

    2023 doi

  11. [19]

    Schuster

    Leandro Stefanazzi, Kenneth Treptow, Neal Wilcer, Chris Stoughton, Collin Brad- ford, Sho Uemura, Silvia Zorzetti, Salvatore Montella, Gustavo Cancelo, Sara Sussman, Andrew Houck, Shefali Saxena, Horacio Arnaldi, Ankur Agrawal, He- lin Zhang, Chunyang Ding, and David I. Schust...

    2022 doi

  12. [20]

    Qiskit pulse: Programming quantum computers through the cloud with pulses.Quantum Science and Technology, 5(4):044006, August 2020

    Thomas Alexander, Naoki Kanazawa, Daniel J Egger, Lauren Capelluto, Christo- pher J Wood, Ali Javadi-Abhari, and David C McKay. Qiskit pulse: Programming quantum computers through the cloud with pulses.Quantum Science and Technology, 5(4):044006, August 2020. ISSN 2058-9565. D...

    2020 doi

  13. [21]

    Lov K. Grover. A fast quantum mechanical algorithm for database search. In Proceedings of the Twenty-Eighth Annual ACM Symposium on Theory of Comput- ing - STOC ’96, pages 212–219, Philadelphia, Pennsylvania, United States, 1996. ACM Press. ISBN 978-0-89791-785-8. DOI: 10.1145...

    1996

  14. [22]

    How to factor 2048 bit RSA integers in 8 hours using 20 million noisy qubits

    Craig Gidney and Martin Ekerå. How to factor 2048 bit RSA integers in 8 hours using 20 million noisy qubits. Quantum, 5:433, April 2021. ISSN 2521-327X. 22 DOI: 10.22331/q-2021-04-15-433. URL https://quantum-journal.org/papers/ q-2021-04-15-433/

    doi

  15. [23]

    Peter W. Shor. Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer. SIAM Journal on Computing, 26(5):1484– 1509, October 1997. ISSN 0097-5397, 1095-7111. DOI: 10.1137/S0097539795293172. URL http://epubs.siam.org/doi/10.1137/S0097539...

    1997 doi

  16. [24]

    Quantum Computing in the NISQ era and beyond

    John Preskill. Quantum Computing in the NISQ era and beyond. Quantum, 2: 79, August 2018. ISSN 2521-327X. DOI: 10.22331/q-2018-08-06-79. URL https: //quantum-journal.org/papers/q-2018-08-06-79/

    2018 doi

  17. [25]

    Steiger, Thomas Häner, and Matthias Troyer

    Damian S. Steiger, Thomas Häner, and Matthias Troyer. ProjectQ: An open source software framework for quantum computing. Quantum, 2:49, January 2018. ISSN 2521-327X. DOI: 10.22331/q-2018-01-31-49. URL https://quantum-journal.org/ papers/q-2018-01-31-49/

    2018 doi

  18. [26]

    Sohaib Alam, Guillermo Alonso-Linaje, B

    Ville Bergholm, Josh Izaac, Maria Schuld, Christian Gogolin, Shahnawaz Ahmed, Vishnu Ajith, M. Sohaib Alam, Guillermo Alonso-Linaje, B. AkashNarayanan, Ali Asadi, Juan Miguel Arrazola, Utkarsh Azad, Sam Banning, Carsten Blank, Thomas R Bromley, Benjamin A. Cordier, Jack Ceroni...

    2018 arXiv

  19. [27]

    Wood, Jake Lishman, Julien Gacon, Simon Martiel, Paul D

    Ali Javadi-Abhari, Matthew Treinish, Kevin Krsulich, Christopher J. Wood, Jake Lishman, Julien Gacon, Simon Martiel, Paul D. Nation, Lev S. Bishop, Andrew W. Cross, Blake R. Johnson, and Jay M. Gambetta. Quantum computing with Qiskit, June 2024. URL http://arxiv.org/abs/2405.08810

    2024 arXiv

  20. [28]

    Yu Kitaev

    A. Yu Kitaev. Quantum measurements and the Abelian Stabilizer Problem, November

  21. [29]

    Harrow, Avinatan Hassidim, and Seth Lloyd

    Aram W. Harrow, Avinatan Hassidim, and Seth Lloyd. Quantum Algorithm for Linear Systems of Equations.Physical Review Letters, 103(15):150502, October 2009. ISSN 0031-9007, 1079-7114. DOI: 10.1103/PhysRevLett.103.150502. URLhttps://link. aps.org/doi/10.1103/PhysRevLett.103.150502

    2009 doi

  22. [30]

    Quantum Circuits for partial differ- ential equations via Schr\"odingerisation, May 2024

    Junpeng Hu, Shi Jin, Nana Liu, and Lei Zhang. Quantum Circuits for partial differ- ential equations via Schr\"odingerisation, May 2024. URLhttp://arxiv.org/abs/ 2403.10032

    2024 arXiv

  23. [31]

    Cormen, Charles Eric Leiserson, Ronald Linn Rivest, and Clifford Stein

    Thomas H. Cormen, Charles Eric Leiserson, Ronald Linn Rivest, and Clifford Stein. Introduction to Algorithms. MIT Press, Cambridge, Massachusetts London, England, third edition edition, 2009. ISBN 978-0-262-03384-8 978-0-262-53305-8

    2009

  24. [32]

    Nielsen and Isaac L

    Michael A. Nielsen and Isaac L. Chuang. Quantum Computation and Quan- tum Information. Cambridge university press, Cambridge, 10th anniversary edi- tion edition, 2010. ISBN 978-1-107-00217-3. URL https://doi.org/10.1017/ CBO9780511976667. 23

    2010

  25. [33]

    A review on Quantum Approximate Optimiza- tion Algorithm and its variants.Physics Reports, 1068:1–66, June 2024

    Kostas Blekos, Dean Brand, Andrea Ceschini, Chiao-Hui Chou, Rui-Hao Li, Komal Pandya, and Alessandro Summer. A review on Quantum Approximate Optimiza- tion Algorithm and its variants.Physics Reports, 1068:1–66, June 2024. ISSN 0370-

    2024

  26. [34]

    Alexei Kitaev and William A. Webb. Wavefunction preparation and resampling using a quantum computer, 2008. URLhttps://arxiv.org/abs/0801.0342

    2008 arXiv

  27. [35]

    Detecting crosstalk errors in quantum information processors

    Mohan Sarovar, Timothy Proctor, Kenneth Rudinger, Kevin Young, Erik Nielsen, and Robin Blume-Kohout. Detecting crosstalk errors in quantum information processors. Quantum, 4:321, September 2020. ISSN 2521-327X. DOI: 10.22331/q-2020-09-11-321. URL https://quantum-journal.org/pa...

    2020 doi

  28. [36]

    A Quantum Algorithm for Finding the Minimum,

    Christoph Durr and Peter Hoyer. A Quantum Algorithm for Finding the Minimum,

  29. [37]

    Quantum lower bounds for the collision and the element distinctness problems.Journal of the ACM, 51(4):595–605, July 2004

    Scott Aaronson and Yaoyun Shi. Quantum lower bounds for the collision and the element distinctness problems.Journal of the ACM, 51(4):595–605, July 2004. ISSN 0004-5411, 1557-735X. DOI: 10.1145/1008731.1008735. URLhttps://dl.acm.org/ doi/10.1145/1008731.1008735

    2004

  30. [38]

    Quantum cryptanalysis of hash and claw-free functions: Invited paper

    Gilles Brassard, Peter HØyer, and Alain Tapp. Quantum cryptanalysis of hash and claw-free functions: Invited paper. In Gerhard Goos, Juris Hartmanis, Jan Van Leeuwen, Cláudio L. Lucchesi, and Arnaldo V. Moura, editors, LATIN’98: Theoretical Informatics, volume 1380, pages 163–...

    1998 doi

  31. [39]

    Cerf, Lov K

    Nicolas J. Cerf, Lov K. Grover, and Colin P. Williams. Nested quantum search and structured problems. Physical Review A, 61(3):032303, February 2000. ISSN 1050- 2947, 1094-1622. DOI: 10.1103/PhysRevA.61.032303. URLhttps://link.aps.org/ doi/10.1103/PhysRevA.61.032303

    doi

  32. [40]

    McKay, Christopher J

    David C. McKay, Christopher J. Wood, Sarah Sheldon, Jerry M. Chow, and Jay M. Gambetta. Efficient Z gates for quantum computing.Physical Review A, 96(2):022330, August 2017. ISSN 2469-9926, 2469-9934. DOI: 10.1103/PhysRevA.96.022330. URL https://link.aps.org/doi/10.1103/PhysRe...

    2017 doi

  33. [41]

    Simu- lating noisy quantum channels via quantum state preparation algorithms.Journal of Physics B: Atomic, Molecular and Optical Physics, 56(11):115501, June 2023

    Marcelo S Zanetti, Douglas F Pinto, Marcos L W Basso, and Jonas Maziero. Simu- lating noisy quantum channels via quantum state preparation algorithms.Journal of Physics B: Atomic, Molecular and Optical Physics, 56(11):115501, June 2023. ISSN 0953-4075, 1361-6455. DOI: 10.1088/...

    2023 doi

  34. [1573]

    URL https://linkinghub.elsevier

    DOI: 10.1016/j.physrep.2024.03.002. URL https://linkinghub.elsevier. com/retrieve/pii/S0370157324001078

    2024 doi

  35. [1995]

    URL http://arxiv.org/abs/quant-ph/9511026

    arXiv

  36. [1996]

    URL https://arxiv.org/abs/quant-ph/9607014

    arXiv

  37. [4151]

    URL https://ieeexplore.ieee.org/ document/10293178/

    DOI: 10.1109/TCAD.2023.3327102. URL https://ieeexplore.ieee.org/ document/10293178/

    2023

Pith tools