quantum-computing

Efficient Simulation of High-Level Quantum Gates

Quantum Journal

17 min read

0 likes

⚡ Quantum Brief

Researchers from Aarhus University and CWI Amsterdam introduced a gadget-based quantum simulator that directly processes high-level gates like oracles and multi-controlled X gates without compiling them into low-level operations. The new approach uses stabilizer decompositions of magic states to reduce the exponential overhead caused by traditional compilation methods, significantly improving simulation efficiency for circuits with few high-level gates. The team established tight stabilizer rank bounds for common algorithmic gates, proving some gates have asymptotically tight exponential lower bounds under standard complexity assumptions. Benchmark tests show the simulator outperforms IBM’s Qiskit Aer in both theoretical complexity and practical runtime for circuits containing high-level operations. The work provides a framework for optimizing quantum algorithm verification while advancing understanding of stabilizer rank limitations in quantum computation.

Efficient Simulation of High-Level Quantum Gates

Summarize this article with:

AbstractQuantum circuit simulation is paramount to the verification and optimization of quantum algorithms, and considerable research efforts have been made towards efficient simulators. While circuits often contain high-level gates such as oracles and multi-controlled $X$ ($C^kX$) gates, existing simulation methods require compilation to a low-level gate-set before simulation. This, however, increases circuit size and incurs a considerable (typically exponential) overhead, even when the number of high-level gates is small. Here we present a gadget-based simulator which simulates high-level gates directly, thereby allowing to avoid or reduce the blowup of compilation. Our simulator uses a stabilizer decomposition of the magic state of non-stabilizer gates, with improvements in the rank of the magic state directly improving performance. We then proceed to establish a small stabilizer rank for a range of high-level gates that are common in various quantum algorithms. Using these bounds in our simulator, we improve both the theoretical complexity of simulating circuits containing such gates, and the practical running time compared to standard simulators found in IBM's Qiskit Aer library. We also derive exponential lower-bounds for the stabilizer rank of some gates under common complexity-theoretic hypotheses. In certain cases, our lower-bounds are asymptotically tight on the exponent.► BibTeX data@article{Kjelstrom2026efficientsimulation, doi = {10.22331/q-2026-05-05-2093}, url = {https://doi.org/10.22331/q-2026-05-05-2093}, title = {Efficient {S}imulation of {H}igh-{L}evel {Q}uantum {G}ates}, author = {Kjelstr{\o{}}m, Adam Husted and Pavlogiannis, Andreas and Pol, Jaco van de}, journal = {{Quantum}}, issn = {2521-327X}, publisher = {{Verein zur F{\"{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}}, volume = {10}, pages = {2093}, month = may, year = {2026} }► References [1] Leonidas Lampropoulos, Zoe Paraskevopoulou, and Benjamin C. Pierce. ``Generating good generators for inductive relations''. Proc. ACM Program. Lang. 2 (2017). https://doi.org/10.1145/3158133 [2] Jiyuan Wang, Qian Zhang, Guoqing Harry Xu, and Miryung Kim. ``QDiff: Differential Testing of Quantum Software Stacks''. In 2021 36th IEEE/ACM International Conference on Automated Software Engineering (ASE). Pages 692–704. (2021). https://doi.org/10.1109/ASE51524.2021.9678792 [3] Tom Peham, Nina Brandl, Richard Kueng, Robert Wille, and Lukas Burgholzer. ``Depth-Optimal Synthesis of Clifford Circuits with SAT Solvers''. In 2023 IEEE International Conference on Quantum Computing and Engineering (QCE). Volume 1, pages 802–813. IEEE (2023). https://doi.org/10.1109/QCE57702.2023.00095 [4] Sarah Schneider, Lukas Burgholzer, and Robert Wille. ``A SAT Encoding for Optimal Clifford Circuit Synthesis''. In Proceedings of the 28th Asia and South Pacific Design Automation Conference. ASPDAC ’23. ACM (2023). https://doi.org/10.1145/3566097.3567929 [5] Richard P Feynman. ``Simulating Physics with Computers''. International Journal of Theoretical Physics 21, 467–488 (1982). https://doi.org/10.1007/BF02650179 [6] Scott Aaronson and Daniel Gottesman. ``Improved simulation of stabilizer circuits''. Physical Review A 70 (2004). https://doi.org/10.1103/physreva.70.052328 [7] Sergey Bravyi, Graeme Smith, and John A. Smolin. ``Trading Classical and Quantum Computational Resources''. Physical Review X 6 (2016). https://doi.org/10.1103/physrevx.6.021043 [8] Sergey Bravyi, Dan Browne, Padraic Calpin, Earl Campbell, David Gosset, and Mark Howard. ``Simulation of quantum circuits by low-rank stabilizer decompositions''. Quantum 3, 181 (2019). https://doi.org/10.22331/q-2019-09-02-181 [9] Xinlan Zhou, Debbie W. Leung, and Isaac L. Chuang. ``Methodology for quantum logic gate construction''. Physical Review A 62 (2000). https://doi.org/10.1103/physreva.62.052316 [10] Hammam Qassim, Hakop Pashayan, and David Gosset. ``Improved upper bounds on the stabilizer rank of magic states''. Quantum 5, 606 (2021). https://doi.org/10.22331/q-2021-12-20-606 [11] Tiago M. L. de Veras, Leon D. da Silva, and Adenilton J. da Silva. ``Double sparse quantum state preparation''.

Quantum Information Processing 21 (2022). https://doi.org/10.1007/s11128-022-03549-y [12] Aram W. Harrow, Avinatan Hassidim, and Seth Lloyd. ``Quantum Algorithm for Linear Systems of Equations''.

Physical Review Letters 103 (2009). https://doi.org/10.1103/physrevlett.103.150502 [13] Mingchao Guo, Hailing Liu, Yongmei Li, Wenmin Li, Fei Gao, Sujuan Qin, and Qiaoyan Wen. ``Quantum algorithms for anomaly detection using amplitude estimation''. Physica A: Statistical Mechanics and its Applications 604, 127936 (2022). https://doi.org/10.1016/j.physa.2022.127936 [14] Jing Li, Fei Gao, Song Lin, Mingchao Guo, Yongmei Li, Hailing Liu, Sujuan Qin, and QiaoYan Wen. ``Quantum k-fold cross-validation for nearest neighbor classification algorithm''. Physica A: Statistical Mechanics and its Applications 611, 128435 (2023). https://doi.org/10.1016/j.physa.2022.128435 [15] Lov K. Grover. ``A fast quantum mechanical algorithm for database search''. In Proceedings of the Twenty-Eighth Annual ACM Symposium on Theory of Computing. Page 212–219. STOC '96 New York, NY, USA (1996). Association for Computing Machinery. https://doi.org/10.1145/237814.237866 [16] David Deutsch and Richard Jozsa. ``Rapid solution of problems by quantum computation''. Proceedings of the Royal Society of London. Series A: Mathematical and Physical Sciences 439, 553–558 (1992). https://doi.org/10.1098/rspa.1992.0167 [17] Ethan Bernstein and Umesh Vazirani. ``Quantum Complexity Theory''. In Proceedings of the Twenty-Fifth Annual ACM Symposium on Theory of Computing. Page 11–20. STOC '93 New York, NY, USA (1993). Association for Computing Machinery. https://doi.org/10.1145/167088.167097 [18] Peter W. Shor. ``Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer''. SIAM Journal on Computing 26, 1484–1509 (1997). https://doi.org/10.1137/S0097539795293172 [19] Daniel R. Simon. ``On the Power of Quantum Computation''. SIAM Journal on Computing 26, 1474–1483 (1997). https://doi.org/10.1137/S0097539796298637 [20] Ben Zindorf and Sougato Bose. ``Efficient Implementation of Multi-Controlled Quantum Gates''. Phys. Rev. Appl. 24, 044030 (2025). https://doi.org/10.1103/8blx-nfcr [21] Rafaella Vale, Thiago Melo D. Azevedo, Ismael C. S. Araújo, Israel F. Araujo, and Adenilton J. da Silva. ``Circuit Decomposition of Multicontrolled Special Unitary Single-Qubit Gates''. Trans. Comp.-Aided Des. Integ. Cir. Sys. 43, 802–811 (2024). https://doi.org/10.1109/TCAD.2023.3327102 [22] András Gilyén, Yuan Su, Guang Hao Low, and Nathan Wiebe. ``Quantum singular value transformation and beyond: exponential improvements for quantum matrix arithmetics''. In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing. Page 193–204. STOC 2019 New York, NY, USA (2019). Association for Computing Machinery. https://doi.org/10.1145/3313276.3316366 [23] John M. Martyn, Zane M. Rossi, Andrew K. Tan, and Isaac L. Chuang. ``Grand Unification of Quantum Algorithms''. PRX Quantum 2, 040203 (2021). https://doi.org/10.1103/PRXQuantum.2.040203 [24] Mark Koch, Richie Yeung, and Quanlong Wang. ``Contraction of ZX diagrams with triangles via stabiliser decompositions''. Physica Scripta 99, 105122 (2024). https://doi.org/10.1088/1402-4896/ad6fd8 [25] Maxime Remaud. ``Optimizing T and CNOT Gates in Quantum Ripple-Carry Adders and Comparators''. In Proceedings of Recent Advances in Quantum Computing and Technology. Pages 56–61. Association for Computing Machinery (2024). https://doi.org/10.1145/3665870.3665875 [26] Mingyoung Jeng, Alvir Nobel, Vinayak Jha, David Levy, Dylan Kneidel, Manu Chaudhary, Ishraq Islam, Muhammad Momin Rahman, and Esam El-Araby. ``Generalized Quantum Convolution for Multidimensional Data''. Entropy 25 (2023). https://doi.org/10.3390/e25111503 [27] Di Fang, Lin Lin, and Yu Tong. ``Time-marching based quantum solvers for time-dependent linear differential equations''. Quantum 7, 955 (2023). https://doi.org/10.22331/q-2023-03-20-955 [28] Brendan L Douglas and JB Wang. ``Efficient quantum circuit implementation of quantum walks''. Physical Review A—Atomic, Molecular, and Optical Physics 79, 052335 (2009). https://doi.org/10.48550/arXiv.0706.0304 [29] Craig Gidney. ``Constructing Large Increment Gates'' (2015). Accessed: 2025-03-27 at https://algassert.com/circuits/2015/06/12/Constructing-Large-Increment-Gates.html. https://algassert.com/circuits/2015/06/12/Constructing-Large-Increment-Gates.html [30] Man-Duen Choi. ``Completely positive linear maps on complex matrices''. Linear Algebra and its Applications 10, 285–290 (1975). https://doi.org/10.1016/0024-3795(75)90075-0 [31] A. Jamiołkowski. ``Linear transformations which preserve trace and positive semidefiniteness of operators''. Reports on Mathematical Physics 3, 275–278 (1972). https://doi.org/10.1016/0034-4877(72)90011-0 [32] Russell Impagliazzo and Ramamohan Paturi. ``On the complexity of k-SAT''. Journal of Computer and System Sciences 62, 367–375 (2001). https://doi.org/10.1006/jcss.2000.1727 [33] Qiskit Development Team. ``Qiskit Aer Documentation''. (2024). url: https://qiskit.github.io/qiskit-aer/. https://qiskit.github.io/qiskit-aer/ [34] Daniel Gottesman. ``Class of quantum error-correcting codes saturating the quantum hamming bound''. Phys. Rev. A 54, 1862–1868 (1996). https://doi.org/10.1103/PhysRevA.54.1862 [35] Christopher M. Dawson and Michael A. Nielsen. ``The Solovay-Kitaev algorithm''. Quantum Info. Comput. 6, 81–95 (2006). https://doi.org/10.48550/arXiv.quant-ph/0505030 arXiv:quant-ph/0505030 [36] Michael A. Nielsen and Isaac L. Chuang. ``Quantum Computation and Quantum Information''.

Cambridge University Press. (2009). 10th Anniversary edition. https://doi.org/10.1017/cbo9780511976667 [37] Oliver Reardon-Smith. ``PSCS: Phase-sensitive Clifford simulator''. (2020). url: https://github.com/or1426/pscs. https://github.com/or1426/pscs [38] Giulia Meuli, Mathias Soeken, and Giovanni De Micheli. ``SAT-based $\{$CNOT, T$\}$ Quantum Circuit Synthesis''.

In Reversible Computation: 10th International Conference, RC 2018, Leicester, UK, September 12-14, 2018, Proceedings 10. Pages 175–188. Springer (2018). https://doi.org/10.1007/978-3-319-99498-7_12 [39] Guifré Vidal. ``Efficient Classical Simulation of Slightly Entangled Quantum Computations''.

Physical Review Letters 91 (2003). https://doi.org/10.1103/physrevlett.91.147902 [40] Ulrich Schollwöck. ``The density-matrix renormalization group in the age of matrix product states''. Annals of Physics 326, 96–192 (2011). https://doi.org/10.1016/j.aop.2010.09.012 [41] Xiao-Ming Zhang, Tongyang Li, and Xiao Yuan. ``Quantum State Preparation with Optimal Circuit Depth: Implementations and Applications''. Phys. Rev. Lett. 129, 230504 (2022). https://doi.org/10.1103/PhysRevLett.129.230504 [42] Daniel K. Park, Francesco Petruccione, and June-Koo Kevin Rhee. ``Circuit-Based Quantum Random Access Memory for Classical Data''. Scientific Reports 9 (2019). https://doi.org/10.1038/s41598-019-40439-3 [43] Tiago M. L. de Veras, Ismael C. S. de Araujo, Daniel K. Park, and Adenilton J. da Silva. ``Circuit-Based Quantum Random Access Memory for Classical Data With Continuous Amplitudes''. IEEE Transactions on Computers 70, 2125–2135 (2021). https://doi.org/10.1109/TC.2020.3037932 [44] Giulia Meuli, Mathias Soeken, Martin Roetteler, and Giovanni De Micheli. ``Enumerating Optimal Quantum Circuits using Spectral Classification''. In 2020 IEEE International Symposium on Circuits and Systems (ISCAS). Pages 1–5. IEEE (2020). https://doi.org/10.1109/ISCAS45731.2020.9180792 [45] Mathias Soeken Giulia Meuli. ``The Single-Target Gate (STG) benchmark suite''. (2020). url: https://github.com/gmeuli/stg-benchmark. https://github.com/gmeuli/stg-benchmark [46] Shan-zhi Li. ``Design of Quantum Comparator Based on Extended General Toffoli Gates with Multiple Targets''. Computer Science 39, 302–306 (2012). url: https://api.semanticscholar.org/CorpusID:63956655. https://api.semanticscholar.org/CorpusID:63956655 [47] Aleks Kissinger, John van de Wetering, and Renaud Vilmart. ``Classical Simulation of Quantum Circuits with Partial and Graphical Stabiliser Decompositions''. In François Le Gall and Tomoyuki Morimae, editors, 17th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2022). Volume 232 of Leibniz International Proceedings in Informatics (LIPIcs), pages 5:1–5:13. Dagstuhl, Germany (2022). Schloss Dagstuhl – Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.TQC.2022.5 [48] Wira Azmoon Ahmad and Matthew Sutcliffe. ``Dynamic T-decomposition for classical simulation of quantum circuits''. arXiv:2412.17182 (2024). https://doi.org/10.48550/arXiv.2412.17182 arXiv:2412.17182 [49] Matthew Sutcliffe. ``Smarter k-Partitioning of ZX-Diagrams for Improved Quantum Circuit Simulation''. arXiv:2409.00828 (2024). https://doi.org/10.48550/arXiv.2409.00828 arXiv:2409.00828 [50] Fedor Kuyanov and Aleks Kissinger. ``Efficient Classical Simulation of Low-Rank-Width Quantum Circuits Using ZX-Calculus''. arXiv:2603.06764 (2026). https://doi.org/10.48550/arXiv.2603.06764 arXiv:2603.06764 [51] Julien Codsi and Tuomas Laakkonen. ``Unifying Graph Measures and Stabilizer Decompositions for the Classical Simulation of Quantum Circuits''. arXiv:2603.06377 (2026). https://doi.org/10.48550/arXiv.2603.06377 arXiv:2603.06377 [52] Hammam Qassim, Joel J Wallman, and Joseph Emerson. ``Clifford recompilation for faster classical simulation of quantum circuits''. Quantum 3, 170 (2019). https://doi.org/10.22331/q-2019-08-05-170Cited byCould not fetch Crossref cited-by data during last attempt 2026-05-05 11:05:51: Could not fetch cited-by data for 10.22331/q-2026-05-05-2093 from Crossref. This is normal if the DOI was registered recently. Could not fetch ADS cited-by data during last attempt 2026-05-05 11:05:51: No response from ADS or unable to decode the received json data when getting the list of citing works.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. AbstractQuantum circuit simulation is paramount to the verification and optimization of quantum algorithms, and considerable research efforts have been made towards efficient simulators. While circuits often contain high-level gates such as oracles and multi-controlled $X$ ($C^kX$) gates, existing simulation methods require compilation to a low-level gate-set before simulation. This, however, increases circuit size and incurs a considerable (typically exponential) overhead, even when the number of high-level gates is small. Here we present a gadget-based simulator which simulates high-level gates directly, thereby allowing to avoid or reduce the blowup of compilation. Our simulator uses a stabilizer decomposition of the magic state of non-stabilizer gates, with improvements in the rank of the magic state directly improving performance. We then proceed to establish a small stabilizer rank for a range of high-level gates that are common in various quantum algorithms. Using these bounds in our simulator, we improve both the theoretical complexity of simulating circuits containing such gates, and the practical running time compared to standard simulators found in IBM's Qiskit Aer library. We also derive exponential lower-bounds for the stabilizer rank of some gates under common complexity-theoretic hypotheses. In certain cases, our lower-bounds are asymptotically tight on the exponent.► BibTeX data@article{Kjelstrom2026efficientsimulation, doi = {10.22331/q-2026-05-05-2093}, url = {https://doi.org/10.22331/q-2026-05-05-2093}, title = {Efficient {S}imulation of {H}igh-{L}evel {Q}uantum {G}ates}, author = {Kjelstr{\o{}}m, Adam Husted and Pavlogiannis, Andreas and Pol, Jaco van de}, journal = {{Quantum}}, issn = {2521-327X}, publisher = {{Verein zur F{\"{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}}, volume = {10}, pages = {2093}, month = may, year = {2026} }► References [1] Leonidas Lampropoulos, Zoe Paraskevopoulou, and Benjamin C. Pierce. ``Generating good generators for inductive relations''. Proc. ACM Program. Lang. 2 (2017). https://doi.org/10.1145/3158133 [2] Jiyuan Wang, Qian Zhang, Guoqing Harry Xu, and Miryung Kim. ``QDiff: Differential Testing of Quantum Software Stacks''. In 2021 36th IEEE/ACM International Conference on Automated Software Engineering (ASE). Pages 692–704. (2021). https://doi.org/10.1109/ASE51524.2021.9678792 [3] Tom Peham, Nina Brandl, Richard Kueng, Robert Wille, and Lukas Burgholzer. ``Depth-Optimal Synthesis of Clifford Circuits with SAT Solvers''. In 2023 IEEE International Conference on Quantum Computing and Engineering (QCE). Volume 1, pages 802–813. IEEE (2023). https://doi.org/10.1109/QCE57702.2023.00095 [4] Sarah Schneider, Lukas Burgholzer, and Robert Wille. ``A SAT Encoding for Optimal Clifford Circuit Synthesis''. In Proceedings of the 28th Asia and South Pacific Design Automation Conference. ASPDAC ’23. ACM (2023). https://doi.org/10.1145/3566097.3567929 [5] Richard P Feynman. ``Simulating Physics with Computers''. International Journal of Theoretical Physics 21, 467–488 (1982). https://doi.org/10.1007/BF02650179 [6] Scott Aaronson and Daniel Gottesman. ``Improved simulation of stabilizer circuits''. Physical Review A 70 (2004). https://doi.org/10.1103/physreva.70.052328 [7] Sergey Bravyi, Graeme Smith, and John A. Smolin. ``Trading Classical and Quantum Computational Resources''. Physical Review X 6 (2016). https://doi.org/10.1103/physrevx.6.021043 [8] Sergey Bravyi, Dan Browne, Padraic Calpin, Earl Campbell, David Gosset, and Mark Howard. ``Simulation of quantum circuits by low-rank stabilizer decompositions''. Quantum 3, 181 (2019). https://doi.org/10.22331/q-2019-09-02-181 [9] Xinlan Zhou, Debbie W. Leung, and Isaac L. Chuang. ``Methodology for quantum logic gate construction''. Physical Review A 62 (2000). https://doi.org/10.1103/physreva.62.052316 [10] Hammam Qassim, Hakop Pashayan, and David Gosset. ``Improved upper bounds on the stabilizer rank of magic states''. Quantum 5, 606 (2021). https://doi.org/10.22331/q-2021-12-20-606 [11] Tiago M. L. de Veras, Leon D. da Silva, and Adenilton J. da Silva. ``Double sparse quantum state preparation''.

Quantum Information Processing 21 (2022). https://doi.org/10.1007/s11128-022-03549-y [12] Aram W. Harrow, Avinatan Hassidim, and Seth Lloyd. ``Quantum Algorithm for Linear Systems of Equations''.

Read Original

Source Information

Source: Quantum Journal

Website: https://quantum-journal.org/feed/

Efficient Simulation of High-Level Quantum Gates

Tags

Source Information