Quantum Gate Decomposition: A Study of Compilation Time vs. Execution Time Trade-offs
Resumo
Similar to classical programming, high-level quantum programming languages generate code that cannot be executed directly by quantum hardware and must be compiled. However, unlike classical code, quantum programs must be compiled before each execution, making the trade-off between compilation time and execution time particularly significant. In this paper, we address the first step of quantum compilation: multi-qubit gate decomposition. We analyze the trade-offs of state-of-the-art decomposition algorithms by implementing them in the Ket quantum programming platform and collecting numerical performance data. This is the first study to both implement and analyze the current state-of-the-art decomposition methods within a single platform. Based on our findings, we propose two compilation profiles: one optimized for minimizing compilation time and another for minimizing quantum execution time. Our results provide valuable insights for both quantum compiler developers and quantum programmers, helping them make informed decisions about gate decomposition strategies and their impact on overall performance.
Palavras-chave:
Quantum Computing, Quantum Programming, Quantum Compiler, Gate Decomposition, Ket
Referências
Scott Aaronson and Daniel Gottesman. 2004. Improved Simulation of Stabilizer Circuits. Physical Review A 70, 5 (Nov. 2004), 052328. DOI: 10.1103/PhysRevA.70.052328
Thomas Alexander, Naoki Kanazawa, Daniel J Egger, Lauren Capelluto, Christopher JWood, Ali Javadi-Abhari, and David C McKay. 2020. Qiskit Pulse: Programming Quantum Computers through the Cloud with Pulses. Quantum Science and Technology 5, 4 (Aug. 2020), 044006. DOI: 10.1088/2058-9565/aba404
Adriano Barenco, Charles H. Bennett, Richard Cleve, David P. DiVincenzo, Norman Margolus, Peter Shor, Tycho Sleator, John A. Smolin, and Harald Weinfurter. 1995. Elementary Gates for Quantum Computation. Physical Review A 52, 5 (Nov. 1995), 3457–3467. DOI: 10.1103/PhysRevA.52.3457
Sohini Chowdhury, Rupali Gill, Arti Badhoutiya, Arun Pratap Srivastava, Akhilesh Kumar Khan, and Rajesh Singh. 2024. Qubit Allocation Strategies in Quantum Computing for Improved Computational Efficiency. In 2024 4th International Conference on Innovative Practices in Technology and Management (ICIPTM). IEEE, Noida, India, 1–6. DOI: 10.1109/ICIPTM59628.2024.10563524
Baptiste Claudon, Julien Zylberman, César Feniou, Fabrice Debbasch, Alberto Peruzzo, and Jean-Philip Piquemal. 2024. Polylogarithmic-Depth Controlled-NOT Gates without Ancilla Qubits. Nature Communications 15, 1 (July 2024), 5886. DOI: 10.1038/s41467-024-50065-x
Bob Coecke and Ross Duncan. 2011. Interacting Quantum Observables: Categorical Algebra and Diagrammatics. New Journal of Physics 13, 4 (April 2011), 043016. DOI: 10.1088/1367-2630/13/4/043016
Evandro Chagas Ribeiro Da Rosa and Rafael De Santiago. 2022. Ket Quantum Programming. ACM Journal on Emerging Technologies in Computing Systems 18, 1 (Jan. 2022), 1–25. DOI: 10.1145/3474224
Adenilton J. Da Silva and Daniel K. Park. 2022. Linear-Depth Quantum Circuits for Multiqubit Controlled Gates. Physical Review A 106, 4 (Oct. 2022), 042602. DOI: 10.1103/PhysRevA.106.042602
Simon J Devitt, William J Munro, and Kae Nemoto. 2013. Quantum Error Correction for Beginners. Reports on Progress in Physics 76, 7 (July 2013), 076001. DOI: 10.1088/0034-4885/76/7/076001
Craig Gidney and Martin Ekerå. 2021. How to Factor 2048 Bit RSA Integers in 8 Hours Using 20 Million Noisy Qubits. Quantum 5 (April 2021), 433. DOI: 10.22331/q-2021-04-15-433
Google Quantum AI and Collaborators, Rajeev Acharya, Dmitry A. Abanin, Laleh Aghababaie-Beni, Igor Aleiner, Trond I. Andersen, Markus Ansmann, Frank Arute, Kunal Arya, Abraham Asfaw, Nikita Astrakhantsev, Juan Atalaya, Ryan Babbush, Dave Bacon, Brian Ballard, Joseph C. Bardin, Johannes Bausch, Andreas Bengtsson, Alexander Bilmes, Sam Blackwell, Sergio Boixo, Gina Bortoli, Alexandre Bourassa, Jenna Bovaird, Leon Brill, Michael Broughton, David A. Browne, Brett Buchea, Bob B. Buckley, David A. Buell, Tim Burger, Brian Burkett, Nicholas Bushnell, Anthony Cabrera, Juan Campero, Hung-Shen Chang, Yu Chen, Zijun Chen, Ben Chiaro, Desmond Chik, Charina Chou, Jahan Claes, Agnetta Y. Cleland, Josh Cogan, Roberto Collins, Paul Conner, William Courtney, Alexander L. Crook, Ben Curtin, Sayan Das, Alex Davies, Laura De Lorenzo, Dripto M. Debroy, Sean Demura, Michel Devoret, Agustin Di Paolo, Paul Donohoe, Ilya Drozdov, Andrew Dunsworth, Clint Earle, Thomas Edlich, Alec Eickbusch, Aviv Moshe Elbag, Mahmoud Elzouka, Catherine Erickson, Lara Faoro, Edward Farhi, Vinicius S. Ferreira, Leslie Flores Burgos, Ebrahim Forati, Austin G. Fowler, Brooks Foxen, Suhas Ganjam, Gonzalo Garcia, Robert Gasca, Elie Genois, William Giang, Craig Gidney, Dar Gilboa, Raja Gosula, Alejandro Grajales Dau, Dietrich Graumann, Alex Greene, Jonathan A. Gross, Steve Habegger, John Hall, Michael C. Hamilton, Monica Hansen, Matthew P. Harrigan, Sean D. Harrington, Francisco J. H. Heras, Stephen Heslin, Paula Heu, Oscar Higgott, Gordon Hill, Jeremy Hilton, George Holland, Sabrina Hong, Hsin-Yuan Huang, Ashley Huff, William J. Huggins, Lev B. Ioffe, Sergei V. Isakov, Justin Iveland, Evan Jeffrey, Zhang Jiang, Cody Jones, Stephen Jordan, Chaitali Joshi, Pavol Juhas, Dvir Kafri, Hui Kang, Amir H. Karamlou, Kostyantyn Kechedzhi, Julian Kelly, Trupti Khaire, Tanuj Khattar, Mostafa Khezri, Seon Kim, Paul V. Klimov, Andrey R. Klots, Bryce Kobrin, Pushmeet Kohli, Alexander N. Korotkov, Fedor Kostritsa, Robin Kothari, Borislav Kozlovskii, John Mark Kreikebaum, Vladislav D. Kurilovich, Nathan Lacroix, David Landhuis, Tiano Lange-Dei, Brandon W. Langley, Pavel Laptev, Kim-Ming Lau, Loïck Le Guevel, Justin Ledford, Joonho Lee, Kenny Lee, Yuri D. Lensky, Shannon Leon, Brian J. Lester, Wing Yan Li, Yin Li, Alexander T. Lill, Wayne Liu, William P. Livingston, Aditya Locharla, Erik Lucero, Daniel Lundahl, Aaron Lunt, Sid Madhuk, Fionn D. Malone, Ashley Maloney, Salvatore Mandrà, James Manyika, Leigh S. Martin, Orion Martin, Steven Martin, Cameron Maxfield, Jarrod R. McClean, Matt McEwen, Seneca Meeks, Anthony Megrant, Xiao Mi, Kevin C. Miao, Amanda Mieszala, Reza Molavi, Sebastian Molina, Shirin Montazeri, Alexis Morvan, Ramis Movassagh, Wojciech Mruczkiewicz, Ofer Naaman, Matthew Neeley, Charles Neill, Ani Nersisyan, Hartmut Neven, Michael Newman, Jiun How Ng, Anthony Nguyen, Murray Nguyen, Chia-Hung Ni, Murphy Yuezhen Niu, Thomas E. O’Brien, William D. Oliver, Alex Opremcak, Kristoffer Ottosson, Andre Petukhov, Alex Pizzuto, John Platt, Rebecca Potter, Orion Pritchard, Leonid P. Pryadko, Chris Quintana, Ganesh Ramachandran, Matthew J. Reagor, John Redding, David M. Rhodes, Gabrielle Roberts, Eliott Rosenberg, Emma Rosenfeld, Pedram Roushan, Nicholas C. Rubin, Negar Saei, Daniel Sank, Kannan Sankaragomathi, Kevin J. Satzinger, Henry F. Schurkus, Christopher Schuster, Andrew W. Senior, Michael J. Shearn, Aaron Shorter, Noah Shutty, Vladimir Shvarts, Shraddha Singh, Volodymyr Sivak, Jindra Skruzny, Spencer Small, Vadim Smelyanskiy, W. Clarke Smith, Rolando D. Somma, Sofia Springer, George Sterling, Doug Strain, Jordan Suchard, Aaron Szasz, Alex Sztein, Douglas Thor, Alfredo Torres, M. Mert Torunbalci, Abeer Vaishnav, Justin Vargas, Sergey Vdovichev, Guifre Vidal, Benjamin Villalonga, Catherine Vollgraff Heidweiller, Steven Waltman, Shannon X. Wang, Brayden Ware, Kate Weber, Travis Weidel, Theodore White, Kristi Wong, Bryan W. K. Woo, Cheng Xing, Z. Jamie Yao, Ping Yeh, Bicheng Ying, Juhwan Yoo, Noureldin Yosri, Grayson Young, Adam Zalcman, Yaxing Zhang, Ningfeng Zhu, and Nicholas Zobrist. 2025. Quantum Error Correction below the Surface Code Threshold. Nature 638, 8052 (Feb. 2025), 920–926. DOI: 10.1038/s41586-024-08449-y
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. ACM Press, Philadelphia, Pennsylvania, United States, 212–219. DOI: 10.1145/237814.237866
You Huang, Mohammad T Amawi, Francesco Poggiali, Fazhan Shi, Jiangfeng Du, and Friedemann Reinhard. 2023. Calibrating Single-Qubit Gates by a Two- Dimensional Rabi Oscillation. AIP Advances 13, 3 (March 2023), 035226. DOI: 10.1063/5.0139454
Raban Iten, Roger Colbeck, Ivan Kukuljan, Jonathan Home, and Matthias Christandl. 2016. Quantum Circuits for Isometries. Physical Review A 93, 3 (March 2016), 032318. DOI: 10.1103/PhysRevA.93.032318
Raban Iten, Oliver Reardon-Smith, Emanuel Malvetti, Luca Mondada, Gabrielle Pauvert, Ethan Redmond, Ravjot Singh Kohli, and Roger Colbeck. 2021. Introduction to UniversalQCompiler. arXiv:1904.01072 [quant-ph] DOI: 10.48550/arXiv.1904.01072
Gushu Li, Yufei Ding, and Yuan Xie. 2019. Tackling the Qubit Mapping Problem for NISQ-Era Quantum Devices. In Proceedings of the Twenty-Fourth International Conference on Architectural Support for Programming Languages and Operating Systems. ACM, Providence RI USA, 1001–1014. DOI: 10.1145/3297858.3304023
Dmitri Maslov. 2016. Advantages of Using Relative-Phase Toffoli Gates with an Application to Multiple Control Toffoli Optimization. Physical Review A 93, 2 (Feb. 2016), 022311. DOI: 10.1103/PhysRevA.93.022311
David C. McKay, Christopher J. Wood, Sarah Sheldon, Jerry M. Chow, and Jay M. Gambetta. 2017. Efficient Z Gates for Quantum Computing. Physical Review A 96, 2 (Aug. 2017), 022330. DOI: 10.1103/PhysRevA.96.022330
Michael A. Nielsen and Isaac L. Chuang. 2010. Quantum Computation and Quantum Information (10th anniversary edition ed.). Cambridge university press, Cambridge. DOI: 10.1017/CBO9780511976667
Siyuan Niu, Adrien Suau, Gabriel Staffelbach, and Aida Todri-Sanial. 2020. A Hardware-Aware Heuristic for the Qubit Mapping Problem in the NISQ Era. IEEE Transactions on Quantum Engineering 1 (2020), 1–14. DOI: 10.1109/TQE.2020.3026544
Christophe Piveteau, David Sutter, Sergey Bravyi, Jay M. Gambetta, and Kristan Temme. 2021. Error Mitigation for Universal Gates on Encoded Qubits. Physical Review Letters 127, 20 (Nov. 2021), 200505. DOI: 10.1103/PhysRevLett.127.200505
Evandro C. R. Rosa, Eduardo I. Duzzioni, and Rafael De Santiago. 2025. Optimizing Gate Decomposition for High-Level Quantum Programming. Quantum 9 (March 2025), 1659. DOI: 10.22331/q-2025-03-12-1659
Evandro C. R. Rosa, Jerusa Marchi, Eduardo I. Duzzioni, and Rafael de Santiago. 2024. Automated Auxiliary Qubit Allocation in High-Level Quantum Programming. arXiv:2412.20543 [quant-ph] DOI: 10.48550/arXiv.2412.20543
Peter W. Shor. 1997. Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer. SIAM J. Comput. 26, 5 (Oct. 1997), 1484–1509. DOI: 10.1137/S0097539795293172
Leandro Stefanazzi, Kenneth Treptow, Neal Wilcer, Chris Stoughton, Collin Bradford, Sho Uemura, Silvia Zorzetti, Salvatore Montella, Gustavo Cancelo, Sara Sussman, Andrew Houck, Shefali Saxena, Horacio Arnaldi, Ankur Agrawal, Helin Zhang, Chunyang Ding, and David I. Schuster. 2022. The QICK (Quantum Instrumentation Control Kit): Readout and Control for Qubits and Detectors. Review of Scientific Instruments 93, 4 (April 2022), 044709. DOI: 10.1063/5.0076249
Krysta Svore, Alan Geller, Matthias Troyer, John Azariah, Christopher Granade, Bettina Heim, Vadym Kliuchnikov, Mariia Mykhailova, Andres Paz, and Martin Roetteler. 2018. Q#: Enabling Scalable Quantum Computing and Development with a High-level DSL. In Proceedings of the RealWorld Domain Specific Languages Workshop 2018. ACM, Vienna Austria, 1–10. DOI: 10.1145/3183895.3183901
Rafaella Vale, Thiago Melo D. Azevedo, Ismael C. S. Araújo, Israel F. Araujo, and Adenilton J. Da Silva. 2024. Circuit Decomposition of Multicontrolled Special Unitary Single-Qubit Gates. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems 43, 3 (March 2024), 802–811. DOI: 10.1109/TCAD.2023.3327102
Robert Wille and Lukas Burgholzer. 2023. MQT QMAP: Efficient Quantum Circuit Mapping. In Proceedings of the 2023 International Symposium on Physical Design. ACM, Virtual Event USA, 198–204. DOI: 10.1145/3569052.3578928
W. K. Wootters and W. H. Zurek. 1982. A Single Quantum Cannot Be Cloned. Nature 299, 5886 (Oct. 1982), 802–803. DOI: 10.1038/299802a0
Pengcheng Zhu, Weiping Ding, Lihua Wei, Xueyun Cheng, Zhijin Guan, and Shiguang Feng. 2023. A Variation-Aware Quantum Circuit Mapping Approach Based on Multi-Agent Cooperation. IEEE Trans. Comput. 72, 8 (Aug. 2023), 2237– 2249. DOI: 10.1109/TC.2023.3242208
Pengcheng Zhu, Zhijin Guan, and Xueyun Cheng. 2020. A Dynamic Look-Ahead Heuristic for the Qubit Mapping Problem of NISQ Computers. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems 39, 12 (Dec. 2020), 4721–4735. DOI: 10.1109/TCAD.2020.2970594
Ben Zindorf and Sougato Bose. 2024. Efficient Implementation of Multi- Controlled Quantum Gates. arXiv:2404.02279 [quant-ph] DOI: 10.48550/arXiv.2404.02279
Thomas Alexander, Naoki Kanazawa, Daniel J Egger, Lauren Capelluto, Christopher JWood, Ali Javadi-Abhari, and David C McKay. 2020. Qiskit Pulse: Programming Quantum Computers through the Cloud with Pulses. Quantum Science and Technology 5, 4 (Aug. 2020), 044006. DOI: 10.1088/2058-9565/aba404
Adriano Barenco, Charles H. Bennett, Richard Cleve, David P. DiVincenzo, Norman Margolus, Peter Shor, Tycho Sleator, John A. Smolin, and Harald Weinfurter. 1995. Elementary Gates for Quantum Computation. Physical Review A 52, 5 (Nov. 1995), 3457–3467. DOI: 10.1103/PhysRevA.52.3457
Sohini Chowdhury, Rupali Gill, Arti Badhoutiya, Arun Pratap Srivastava, Akhilesh Kumar Khan, and Rajesh Singh. 2024. Qubit Allocation Strategies in Quantum Computing for Improved Computational Efficiency. In 2024 4th International Conference on Innovative Practices in Technology and Management (ICIPTM). IEEE, Noida, India, 1–6. DOI: 10.1109/ICIPTM59628.2024.10563524
Baptiste Claudon, Julien Zylberman, César Feniou, Fabrice Debbasch, Alberto Peruzzo, and Jean-Philip Piquemal. 2024. Polylogarithmic-Depth Controlled-NOT Gates without Ancilla Qubits. Nature Communications 15, 1 (July 2024), 5886. DOI: 10.1038/s41467-024-50065-x
Bob Coecke and Ross Duncan. 2011. Interacting Quantum Observables: Categorical Algebra and Diagrammatics. New Journal of Physics 13, 4 (April 2011), 043016. DOI: 10.1088/1367-2630/13/4/043016
Evandro Chagas Ribeiro Da Rosa and Rafael De Santiago. 2022. Ket Quantum Programming. ACM Journal on Emerging Technologies in Computing Systems 18, 1 (Jan. 2022), 1–25. DOI: 10.1145/3474224
Adenilton J. Da Silva and Daniel K. Park. 2022. Linear-Depth Quantum Circuits for Multiqubit Controlled Gates. Physical Review A 106, 4 (Oct. 2022), 042602. DOI: 10.1103/PhysRevA.106.042602
Simon J Devitt, William J Munro, and Kae Nemoto. 2013. Quantum Error Correction for Beginners. Reports on Progress in Physics 76, 7 (July 2013), 076001. DOI: 10.1088/0034-4885/76/7/076001
Craig Gidney and Martin Ekerå. 2021. How to Factor 2048 Bit RSA Integers in 8 Hours Using 20 Million Noisy Qubits. Quantum 5 (April 2021), 433. DOI: 10.22331/q-2021-04-15-433
Google Quantum AI and Collaborators, Rajeev Acharya, Dmitry A. Abanin, Laleh Aghababaie-Beni, Igor Aleiner, Trond I. Andersen, Markus Ansmann, Frank Arute, Kunal Arya, Abraham Asfaw, Nikita Astrakhantsev, Juan Atalaya, Ryan Babbush, Dave Bacon, Brian Ballard, Joseph C. Bardin, Johannes Bausch, Andreas Bengtsson, Alexander Bilmes, Sam Blackwell, Sergio Boixo, Gina Bortoli, Alexandre Bourassa, Jenna Bovaird, Leon Brill, Michael Broughton, David A. Browne, Brett Buchea, Bob B. Buckley, David A. Buell, Tim Burger, Brian Burkett, Nicholas Bushnell, Anthony Cabrera, Juan Campero, Hung-Shen Chang, Yu Chen, Zijun Chen, Ben Chiaro, Desmond Chik, Charina Chou, Jahan Claes, Agnetta Y. Cleland, Josh Cogan, Roberto Collins, Paul Conner, William Courtney, Alexander L. Crook, Ben Curtin, Sayan Das, Alex Davies, Laura De Lorenzo, Dripto M. Debroy, Sean Demura, Michel Devoret, Agustin Di Paolo, Paul Donohoe, Ilya Drozdov, Andrew Dunsworth, Clint Earle, Thomas Edlich, Alec Eickbusch, Aviv Moshe Elbag, Mahmoud Elzouka, Catherine Erickson, Lara Faoro, Edward Farhi, Vinicius S. Ferreira, Leslie Flores Burgos, Ebrahim Forati, Austin G. Fowler, Brooks Foxen, Suhas Ganjam, Gonzalo Garcia, Robert Gasca, Elie Genois, William Giang, Craig Gidney, Dar Gilboa, Raja Gosula, Alejandro Grajales Dau, Dietrich Graumann, Alex Greene, Jonathan A. Gross, Steve Habegger, John Hall, Michael C. Hamilton, Monica Hansen, Matthew P. Harrigan, Sean D. Harrington, Francisco J. H. Heras, Stephen Heslin, Paula Heu, Oscar Higgott, Gordon Hill, Jeremy Hilton, George Holland, Sabrina Hong, Hsin-Yuan Huang, Ashley Huff, William J. Huggins, Lev B. Ioffe, Sergei V. Isakov, Justin Iveland, Evan Jeffrey, Zhang Jiang, Cody Jones, Stephen Jordan, Chaitali Joshi, Pavol Juhas, Dvir Kafri, Hui Kang, Amir H. Karamlou, Kostyantyn Kechedzhi, Julian Kelly, Trupti Khaire, Tanuj Khattar, Mostafa Khezri, Seon Kim, Paul V. Klimov, Andrey R. Klots, Bryce Kobrin, Pushmeet Kohli, Alexander N. Korotkov, Fedor Kostritsa, Robin Kothari, Borislav Kozlovskii, John Mark Kreikebaum, Vladislav D. Kurilovich, Nathan Lacroix, David Landhuis, Tiano Lange-Dei, Brandon W. Langley, Pavel Laptev, Kim-Ming Lau, Loïck Le Guevel, Justin Ledford, Joonho Lee, Kenny Lee, Yuri D. Lensky, Shannon Leon, Brian J. Lester, Wing Yan Li, Yin Li, Alexander T. Lill, Wayne Liu, William P. Livingston, Aditya Locharla, Erik Lucero, Daniel Lundahl, Aaron Lunt, Sid Madhuk, Fionn D. Malone, Ashley Maloney, Salvatore Mandrà, James Manyika, Leigh S. Martin, Orion Martin, Steven Martin, Cameron Maxfield, Jarrod R. McClean, Matt McEwen, Seneca Meeks, Anthony Megrant, Xiao Mi, Kevin C. Miao, Amanda Mieszala, Reza Molavi, Sebastian Molina, Shirin Montazeri, Alexis Morvan, Ramis Movassagh, Wojciech Mruczkiewicz, Ofer Naaman, Matthew Neeley, Charles Neill, Ani Nersisyan, Hartmut Neven, Michael Newman, Jiun How Ng, Anthony Nguyen, Murray Nguyen, Chia-Hung Ni, Murphy Yuezhen Niu, Thomas E. O’Brien, William D. Oliver, Alex Opremcak, Kristoffer Ottosson, Andre Petukhov, Alex Pizzuto, John Platt, Rebecca Potter, Orion Pritchard, Leonid P. Pryadko, Chris Quintana, Ganesh Ramachandran, Matthew J. Reagor, John Redding, David M. Rhodes, Gabrielle Roberts, Eliott Rosenberg, Emma Rosenfeld, Pedram Roushan, Nicholas C. Rubin, Negar Saei, Daniel Sank, Kannan Sankaragomathi, Kevin J. Satzinger, Henry F. Schurkus, Christopher Schuster, Andrew W. Senior, Michael J. Shearn, Aaron Shorter, Noah Shutty, Vladimir Shvarts, Shraddha Singh, Volodymyr Sivak, Jindra Skruzny, Spencer Small, Vadim Smelyanskiy, W. Clarke Smith, Rolando D. Somma, Sofia Springer, George Sterling, Doug Strain, Jordan Suchard, Aaron Szasz, Alex Sztein, Douglas Thor, Alfredo Torres, M. Mert Torunbalci, Abeer Vaishnav, Justin Vargas, Sergey Vdovichev, Guifre Vidal, Benjamin Villalonga, Catherine Vollgraff Heidweiller, Steven Waltman, Shannon X. Wang, Brayden Ware, Kate Weber, Travis Weidel, Theodore White, Kristi Wong, Bryan W. K. Woo, Cheng Xing, Z. Jamie Yao, Ping Yeh, Bicheng Ying, Juhwan Yoo, Noureldin Yosri, Grayson Young, Adam Zalcman, Yaxing Zhang, Ningfeng Zhu, and Nicholas Zobrist. 2025. Quantum Error Correction below the Surface Code Threshold. Nature 638, 8052 (Feb. 2025), 920–926. DOI: 10.1038/s41586-024-08449-y
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. ACM Press, Philadelphia, Pennsylvania, United States, 212–219. DOI: 10.1145/237814.237866
You Huang, Mohammad T Amawi, Francesco Poggiali, Fazhan Shi, Jiangfeng Du, and Friedemann Reinhard. 2023. Calibrating Single-Qubit Gates by a Two- Dimensional Rabi Oscillation. AIP Advances 13, 3 (March 2023), 035226. DOI: 10.1063/5.0139454
Raban Iten, Roger Colbeck, Ivan Kukuljan, Jonathan Home, and Matthias Christandl. 2016. Quantum Circuits for Isometries. Physical Review A 93, 3 (March 2016), 032318. DOI: 10.1103/PhysRevA.93.032318
Raban Iten, Oliver Reardon-Smith, Emanuel Malvetti, Luca Mondada, Gabrielle Pauvert, Ethan Redmond, Ravjot Singh Kohli, and Roger Colbeck. 2021. Introduction to UniversalQCompiler. arXiv:1904.01072 [quant-ph] DOI: 10.48550/arXiv.1904.01072
Gushu Li, Yufei Ding, and Yuan Xie. 2019. Tackling the Qubit Mapping Problem for NISQ-Era Quantum Devices. In Proceedings of the Twenty-Fourth International Conference on Architectural Support for Programming Languages and Operating Systems. ACM, Providence RI USA, 1001–1014. DOI: 10.1145/3297858.3304023
Dmitri Maslov. 2016. Advantages of Using Relative-Phase Toffoli Gates with an Application to Multiple Control Toffoli Optimization. Physical Review A 93, 2 (Feb. 2016), 022311. DOI: 10.1103/PhysRevA.93.022311
David C. McKay, Christopher J. Wood, Sarah Sheldon, Jerry M. Chow, and Jay M. Gambetta. 2017. Efficient Z Gates for Quantum Computing. Physical Review A 96, 2 (Aug. 2017), 022330. DOI: 10.1103/PhysRevA.96.022330
Michael A. Nielsen and Isaac L. Chuang. 2010. Quantum Computation and Quantum Information (10th anniversary edition ed.). Cambridge university press, Cambridge. DOI: 10.1017/CBO9780511976667
Siyuan Niu, Adrien Suau, Gabriel Staffelbach, and Aida Todri-Sanial. 2020. A Hardware-Aware Heuristic for the Qubit Mapping Problem in the NISQ Era. IEEE Transactions on Quantum Engineering 1 (2020), 1–14. DOI: 10.1109/TQE.2020.3026544
Christophe Piveteau, David Sutter, Sergey Bravyi, Jay M. Gambetta, and Kristan Temme. 2021. Error Mitigation for Universal Gates on Encoded Qubits. Physical Review Letters 127, 20 (Nov. 2021), 200505. DOI: 10.1103/PhysRevLett.127.200505
Evandro C. R. Rosa, Eduardo I. Duzzioni, and Rafael De Santiago. 2025. Optimizing Gate Decomposition for High-Level Quantum Programming. Quantum 9 (March 2025), 1659. DOI: 10.22331/q-2025-03-12-1659
Evandro C. R. Rosa, Jerusa Marchi, Eduardo I. Duzzioni, and Rafael de Santiago. 2024. Automated Auxiliary Qubit Allocation in High-Level Quantum Programming. arXiv:2412.20543 [quant-ph] DOI: 10.48550/arXiv.2412.20543
Peter W. Shor. 1997. Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer. SIAM J. Comput. 26, 5 (Oct. 1997), 1484–1509. DOI: 10.1137/S0097539795293172
Leandro Stefanazzi, Kenneth Treptow, Neal Wilcer, Chris Stoughton, Collin Bradford, Sho Uemura, Silvia Zorzetti, Salvatore Montella, Gustavo Cancelo, Sara Sussman, Andrew Houck, Shefali Saxena, Horacio Arnaldi, Ankur Agrawal, Helin Zhang, Chunyang Ding, and David I. Schuster. 2022. The QICK (Quantum Instrumentation Control Kit): Readout and Control for Qubits and Detectors. Review of Scientific Instruments 93, 4 (April 2022), 044709. DOI: 10.1063/5.0076249
Krysta Svore, Alan Geller, Matthias Troyer, John Azariah, Christopher Granade, Bettina Heim, Vadym Kliuchnikov, Mariia Mykhailova, Andres Paz, and Martin Roetteler. 2018. Q#: Enabling Scalable Quantum Computing and Development with a High-level DSL. In Proceedings of the RealWorld Domain Specific Languages Workshop 2018. ACM, Vienna Austria, 1–10. DOI: 10.1145/3183895.3183901
Rafaella Vale, Thiago Melo D. Azevedo, Ismael C. S. Araújo, Israel F. Araujo, and Adenilton J. Da Silva. 2024. Circuit Decomposition of Multicontrolled Special Unitary Single-Qubit Gates. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems 43, 3 (March 2024), 802–811. DOI: 10.1109/TCAD.2023.3327102
Robert Wille and Lukas Burgholzer. 2023. MQT QMAP: Efficient Quantum Circuit Mapping. In Proceedings of the 2023 International Symposium on Physical Design. ACM, Virtual Event USA, 198–204. DOI: 10.1145/3569052.3578928
W. K. Wootters and W. H. Zurek. 1982. A Single Quantum Cannot Be Cloned. Nature 299, 5886 (Oct. 1982), 802–803. DOI: 10.1038/299802a0
Pengcheng Zhu, Weiping Ding, Lihua Wei, Xueyun Cheng, Zhijin Guan, and Shiguang Feng. 2023. A Variation-Aware Quantum Circuit Mapping Approach Based on Multi-Agent Cooperation. IEEE Trans. Comput. 72, 8 (Aug. 2023), 2237– 2249. DOI: 10.1109/TC.2023.3242208
Pengcheng Zhu, Zhijin Guan, and Xueyun Cheng. 2020. A Dynamic Look-Ahead Heuristic for the Qubit Mapping Problem of NISQ Computers. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems 39, 12 (Dec. 2020), 4721–4735. DOI: 10.1109/TCAD.2020.2970594
Ben Zindorf and Sougato Bose. 2024. Efficient Implementation of Multi- Controlled Quantum Gates. arXiv:2404.02279 [quant-ph] DOI: 10.48550/arXiv.2404.02279
Publicado
22/09/2025
Como Citar
ROSA, Evandro C. R.; MARCHI, Jerusa; DUZZIONI, Eduardo I.; SANTIAGO, Rafael de.
Quantum Gate Decomposition: A Study of Compilation Time vs. Execution Time Trade-offs. In: SIMPÓSIO BRASILEIRO DE LINGUAGENS DE PROGRAMAÇÃO (SBLP), 29. , 2025, Recife/PE.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2025
.
p. 10-18.
DOI: https://doi.org/10.5753/sblp.2025.10459.
