Approaching the theoretical limit in quantum gate decomposition

Péter Rakyta1,2 and Zoltán Zimborás3,4

1Department of Physics of Complex Systems, Eötvös Loránd University, Budapest, Hungary
2Wigner Research Center for Physics, 29–33 Konkoly–Thege Miklos Str., H- 1121 Budapest, Hungary
3Wigner Research Center for Physics, 29–33 Konkoly–Thege Miklos Str., H-1121 Budapest, Hungary
4BME-MTA Lendület Quantum Information Theory Research Group, Budapest, Hungary

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


In this work we propose a novel numerical approach to decompose general quantum programs in terms of single- and two-qubit quantum gates with a $CNOT$ gate count very close to the current theoretical lower bounds. In particular, it turns out that $15$ and $63$ $CNOT$ gates are sufficient to decompose a general $3$- and $4$-qubit unitary, respectively, with high numerical accuracy. Our approach is based on a sequential optimization of parameters related to the single-qubit rotation gates involved in a pre-designed quantum circuit used for the decomposition. In addition, the algorithm can be adopted to sparse inter-qubit connectivity architectures provided by current mid-scale quantum computers, needing only a few additional $CNOT$ gates to be implemented in the resulting quantum circuits.

► BibTeX data

► References

[1] 4 P. W. Shor, ``Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer,'' SIAM Journal on Computing, vol. 26, no. 5, pp. 1484–1509, 1997. [Online]. Available: https:/​/​​10.1137/​S0097539795293172 0pt.

[2] 4 L. K. Grover, ``Quantum mechanics helps in searching for a needle in a haystack,'' Phys. Rev. Lett., vol. 79, pp. 325–328, Jul 1997. [Online]. Available: https:/​/​​10.1103/​PhysRevLett.79.325 0pt.

[3] 4 L. M. K. Vandersypen, M. Steffen, M. H. Sherwood, C. S. Yannoni, G. Breyta, and I. L. Chuang, ``Implementation of a three-quantum-bit search algorithm,'' Applied Physics Letters, vol. 76, no. 5, pp. 646–648, 2000. [Online]. Available: https:/​/​​10.1063/​1.125846 0pt.

[4] 4 C. Figgatt, D. Maslov, K. A. Landsman, N. M. Linke, S. Debnath, and C. Monroe, ``Complete 3-qubit grover search on a programmable quantum computer,'' Nature Communications, vol. 8, no. 1, p. 1918, Dec 2017. [Online]. Available: https:/​/​​10.1038/​s41467-017-01904-7 0pt.

[5] 4 E. Martín-López, A. Laing, T. Lawson, R. Alvarez, X.-Q. Zhou, and J. L. O'Brien, ``Experimental realization of shor's quantum factoring algorithm using qubit recycling,'' Nature Photonics, vol. 6, no. 11, pp. 773–776, Nov 2012. [Online]. Available: https:/​/​​10.1038/​nphoton.2012.259 0pt.

[6] 4 T. Monz, D. Nigg, E. A. Martinez, M. F. Brandl, P. Schindler, R. Rines, S. X. Wang, I. L. Chuang, and R. Blatt, ``Realization of a scalable shor algorithm,'' Science, vol. 351, no. 6277, pp. 1068–1070, 2016. [Online]. Available: https:/​/​​content/​351/​6277/​1068 https:/​/​​10.1126/​science.aad9480 0pt.

[7] 4 M. Amico, Z. H. Saleem, and M. Kumph, ``Experimental study of shor's factoring algorithm using the ibm q experience,'' Phys. Rev. A, vol. 100, p. 012305, Jul 2019. [Online]. Available: https:/​/​​10.1103/​PhysRevA.100.012305 0pt.

[8] M. P. Harrigan et al., ``Quantum approximate optimization of non-planar graph problems on a planar superconducting processor,'' Nature Physics, vol. 17, no. 3, pp. 332–336, 2021. https:/​/​​10.1038/​s41567-020-01105-y.

[9] F. Arute et al., ``Hartree-fock on a superconducting qubit quantum computer,'' Science, vol. 369, no. 6507, pp. 1084–1089, 2020. https:/​/​​10.1126/​science.abb9811.

[10] 4 A. Smith, M. S. Kim, F. Pollmann, and J. Knolle, ``Simulating quantum many-body dynamics on a current digital quantum computer,'' npj Quantum Information, vol. 5, no. 1, p. 106, Nov 2019. [Online]. Available: https:/​/​​10.1038/​s41534-019-0217-0 0pt.

[11] 4 S. Leontica, F. Tennie, and T. Farrow, ``Simulating molecules on a cloud-based 5-qubit ibm-q universal quantum computer,'' Communications Physics, vol. 4, no. 1, p. 112, Jun 2021. [Online]. Available: https:/​/​​10.1038/​s42005-021-00616-1 0pt.

[12] 4 D. A. Fedorov, M. J. Otten, S. K. Gray, and Y. Alexeev, ``Ab initio molecular dynamics on quantum computers,'' The Journal of Chemical Physics, vol. 154, no. 16, p. 164103, 2021. [Online]. Available: https:/​/​​10.1063/​5.0046930 0pt.

[13] 4 T. Bian and S. Kais, ``Quantum computing for atomic and molecular resonances,'' The Journal of Chemical Physics, vol. 154, no. 19, p. 194107, 2021. [Online]. Available: https:/​/​​10.1063/​5.0040477 0pt.

[14] K. Satzinger et al., ``Realizing topologically ordered states on a quantum processor,'' arXiv preprint arXiv:2104.01180, 2021. https:/​/​​10.1126/​science.abi8378.

[15] 4 A. Barenco, C. H. Bennett, R. Cleve, D. P. DiVincenzo, N. Margolus, P. Shor, T. Sleator, J. A. Smolin, and H. Weinfurter, ``Elementary gates for quantum computation,'' Phys. Rev. A, vol. 52, pp. 3457–3467, Nov 1995. [Online]. Available: https:/​/​​10.1103/​PhysRevA.52.3457 0pt.

[16] 4 N. M. Linke, D. Maslov, M. Roetteler, S. Debnath, C. Figgatt, K. A. Landsman, K. Wright, and C. Monroe, ``Experimental comparison of two quantum computing architectures,'' Proceedings of the National Academy of Sciences, vol. 114, no. 13, pp. 3305–3310, 2017. [Online]. Available: https:/​/​​10.1073/​pnas.1618020114 0pt.

[17] 4 S. S. Tannu and M. K. Qureshi, ``Not all qubits are created equal: A case for variability-aware policies for nisq-era quantum computers,'' in Proceedings of the Twenty-Fourth International Conference on Architectural Support for Programming Languages and Operating Systems, ser. ASPLOS '19. New York, NY, USA: Association for Computing Machinery, 2019, p. 987–999. [Online]. Available: https:/​/​​10.1145/​3297858.3304007 0pt.

[18] 4 V. V. Shende, I. L. Markov, and S. S. Bullock, ``Minimal universal two-qubit controlled-not-based circuits,'' Phys. Rev. A, vol. 69, p. 062321, Jun 2004. [Online]. Available: https:/​/​​10.1103/​PhysRevA.69.062321 0pt.

[19] W. H. Press, S. A. Teukolsky, W. T. Vetterling, and B. P. Flannery, Numerical recipes in FORTRAN. The art of scientific computing, 1992.

[20] 4 J. J. Vartiainen, M. Möttönen, and M. M. Salomaa, ``Efficient decomposition of quantum gates,'' Phys. Rev. Lett., vol. 92, p. 177902, Apr 2004. [Online]. Available: https:/​/​​10.1103/​PhysRevLett.92.177902 0pt.

[21] V. Shende, S. Bullock, and I. Markov, ``Synthesis of quantum-logic circuits,'' IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 25, no. 6, pp. 1000–1010, 2006. https:/​/​​10.1109/​TCAD.2005.855930.

[22] R. R. Tucci, ``A rudimentary quantum compiler(2cnd ed.),'' 1999.

[23] M. Möttönen and J. J. Vartiainen, ``Decompositions of general quantum gates,'' 2005.

[24] 4 C. Paige and M. Wei, ``History and generality of the cs decomposition,'' Linear Algebra and its Applications, vol. 208-209, pp. 303–326, 1994. [Online]. Available: https:/​/​​10.1016/​0024-3795(94)90446-4 0pt.

[25] 4 R. T. H. Dekant, H. Tregillus and T. Yin, ``Qubiter at github,'' 2020. [Online]. Available: https:/​/​​artiste-qb-net/​qubiter 0pt.

[26] N. Khammassi, I. Ashraf, J. v. Someren, R. Nane, A. M. Krol, M. A. Rol, L. Lao, K. Bertels, and C. G. Almudever, ``Openql : A portable quantum programming framework for quantum accelerators,'' 2020.

[27] A. M. Krol, A. Sarkar, I. Ashraf, Z. Al-Ars, and K. Bertels, ``Efficient decomposition of unitary matrices in quantum circuit compilers,'' 2021.

[28] G. W. Dueck, A. Pathak, M. M. Rahman, A. Shukla, and A. Banerjee, ``Optimization of circuits for ibm's five-qubit quantum computers,'' in 2018 21st Euromicro Conference on Digital System Design (DSD), 2018, pp. 680–684. https:/​/​​10.1109/​DSD.2018.00005.

[29] M. Sisodia, A. Shukla, A. A. A. de Almeida, G. Dueck, and A. Pathak, ``Circuit optimization for ibm processors: A way to get higher fidelity and higher values of nonclassicality witnesses,'' arXiv: Quantum Physics, 2018.

[30] 4 M. Rötteler, Quantum Error Correction. Boston, MA: Springer US, 2008, pp. 705–708. [Online]. Available: https:/​/​​10.1007/​978-0-387-30162-4_315 0pt.

[31] 4 S. Khatri, R. LaRose, A. Poremba, L. Cincio, A. T. Sornborger, and P. J. Coles, ``Quantum-assisted quantum compiling,'' Quantum, vol. 3, p. 140, May 2019. [Online]. Available: https:/​/​​10.22331/​q-2019-05-13-140 0pt.

[32] E. Younis, K. Sen, K. Yelick, and C. Iancu, ``QFAST: Quantum Synthesis Using a Hierarchical Continuous Circuit Space,'' arXiv e-prints, p. arXiv:2003.04462, Mar. 2020.

[33] 4 E. Younis, K. Sen, K. Yelick, and C. Iancu, ``Qfast: Conflating search and numerical optimization for scalable quantum circuit synthesis,'' in 2021 IEEE International Conference on Quantum Computing and Engineering (QCE). Los Alamitos, CA, USA: IEEE Computer Society, oct 2021, pp. 232–243. [Online]. Available: https:/​/​​10.1109/​QCE52317.2021.00041 0pt.

[34] L. Madden and A. Simonetto, ``Best approximate quantum compiling problems,'' 2021.

[35] E. Smith, M. G. Davis, J. Larson, E. Younis, C. Iancu, and W. Lavrijsen, ``Leap: Scaling numerical optimization based synthesis using an incremental approach,'' 2021, arXiv:2106.11246.

[36] 4 ``Ibm q5 yorktown.'' [Online]. Available: https:/​/​​Qiskit/​ibmq-device-information/​tree/​master/​backends/​yorktown/​V1 0pt.

[37] 4 P. Jurcevic, A. Javadi-Abhari, L. S. Bishop, I. Lauer, D. F. Bogorin, M. Brink, L. Capelluto, O. Günlük, T. Itoko, N. Kanazawa, A. Kandala, G. A. Keefe, K. Krsulich, W. Landers, E. P. Lewandowski, D. T. McClure, G. Nannicini, A. Narasgond, H. M. Nayfeh, E. Pritchett, M. B. Rothwell, S. Srinivasan, N. Sundaresan, C. Wang, K. X. Wei, C. J. Wood, J.-B. Yau, E. J. Zhang, O. E. Dial, J. M. Chow, and J. M. Gambetta, ``Demonstration of quantum volume 64 on a superconducting quantum computing system,'' Quantum Science and Technology, vol. 6, no. 2, p. 025020, mar 2021. [Online]. Available: https:/​/​​10.1088/​2058-9565/​abe519 0pt.

[38] 4 ``Sequential quantum gate decomposer,'' 2021. [Online]. Available: https:/​/​​rakytap/​sequential-quantum-gate-decomposer 0pt.

[39] 4 M. Möttönen, J. J. Vartiainen, V. Bergholm, and M. M. Salomaa, ``Quantum circuits for general multiqubit gates,'' Phys. Rev. Lett., vol. 93, p. 130502, Sep 2004. [Online]. Available: https:/​/​​10.1103/​PhysRevLett.93.130502 0pt.

[40] 4 R. Iten, R. Colbeck, I. Kukuljan, J. Home, and M. Christandl, ``Quantum circuits for isometries,'' Physical Review A, vol. 93, no. 3, Mar 2016. [Online]. Available: http:/​/​​10.1103/​PhysRevA.93.032318 0pt.

[41] 4 C. Kelley, Iterative Methods for Optimization, ser. Frontiers in Applied Mathematics. Society for Industrial and Applied Mathematics, 1999. [Online]. Available: https:/​/​​books?id=Bq6VcmzOe1IC 0pt.

[42] 4 F. Vatan and C. Williams, ``Optimal quantum circuits for general two-qubit gates,'' Phys. Rev. A, vol. 69, p. 032315, Mar 2004. [Online]. Available: https:/​/​​10.1103/​PhysRevA.69.032315 0pt.

[43] L. S. Blackford, A. Petitet, R. Pozo, K. Remington, R. C. Whaley, J. Demmel, J. Dongarra, I. Duff, S. Hammarling, G. Henry et al., ``An updated set of basic linear algebra subprograms (blas),'' ACM Transactions on Mathematical Software, vol. 28, no. 2, pp. 135–151, 2002. https:/​/​​10.1145/​567806.567807.

[44] 4 J. M. Chow, A. D. Córcoles, J. M. Gambetta, C. Rigetti, B. R. Johnson, J. A. Smolin, J. R. Rozen, G. A. Keefe, M. B. Rothwell, M. B. Ketchen, and M. Steffen, ``Simple all-microwave entangling gate for fixed-frequency superconducting qubits,'' Phys. Rev. Lett., vol. 107, p. 080502, Aug 2011. [Online]. Available: https:/​/​​10.1103/​PhysRevLett.107.080502 0pt.

[45] 4 R. Barends, J. Kelly, A. Megrant, A. Veitia, D. Sank, E. Jeffrey, T. C. White, J. Mutus, A. G. Fowler, B. Campbell, Y. Chen, Z. Chen, B. Chiaro, A. Dunsworth, C. Neill, P. O'Malley, P. Roushan, A. Vainsencher, J. Wenner, A. N. Korotkov, A. N. Cleland, and J. M. Martinis, ``Superconducting quantum circuits at the surface code threshold for fault tolerance,'' Nature, vol. 508, no. 7497, pp. 500–503, Apr 2014. [Online]. Available: https:/​/​​10.1038/​nature13171 0pt.

[46] 4 Z. Zong, Z. Sun, Z. Dong, C. Run, L. Xiang, Z. Zhan, Q. Wang, Y. Fei, Y. Wu, W. Jin, C. Xiao, Z. Jia, P. Duan, J. Wu, Y. Yin, and G. Guo, ``Optimization of a controlled-$z$ gate with data-driven gradient-ascent pulse engineering in a superconducting-qubit system,'' Phys. Rev. Applied, vol. 15, p. 064005, Jun 2021. [Online]. Available: https:/​/​​10.1103/​PhysRevApplied.15.064005 0pt.

[47] 4 Y. Xu, Y. Ma, W. Cai, X. Mu, W. Dai, W. Wang, L. Hu, X. Li, J. Han, H. Wang, Y. P. Song, Z.-B. Yang, S.-B. Zheng, and L. Sun, ``Demonstration of controlled-phase gates between two error-correctable photonic qubits,'' Phys. Rev. Lett., vol. 124, p. 120501, Mar 2020. [Online]. Available: https:/​/​​10.1103/​PhysRevLett.124.120501 0pt.

[48] 4 H.-P. Lo, T. Ikuta, N. Matsuda, T. Honjo, W. J. Munro, and H. Takesue, ``Quantum process tomography of a controlled-phase gate for time-bin qubits,'' Phys. Rev. Applied, vol. 13, p. 034013, Mar 2020. [Online]. Available: https:/​/​​10.1103/​PhysRevApplied.13.034013 0pt.

[49] 4 ``Tutorial materials to use sequential quantum gate decomposer,'' 2021. [Online]. Available: https:/​/​​rakytap/​sequential-quantum-gate-decomposer/​ 0pt.

[50] 4 ``Ibm quantum solutions.'' [Online]. Available: https:/​/​​quantum-computing/​ 0pt.

[51] 4 ``Ibm q5 tenerife.'' [Online]. Available: https:/​/​​Qiskit/​ibmq-device-information/​tree/​master/​backends/​tenerife/​V1 0pt.

[52] 4 M. Voss, R. Asenjo, and J. Reinders, Pro TBB: C++ parallel programming with threading building blocks. New York: Apress Open, 2019. [Online]. Available: https:/​/​​book/​10.1007/​978-1-4842-4398-5 0pt.

Cited by

[1] Jake Xuereb, Paul Erker, Florian Meier, Mark T. Mitchison, and Marcus Huber, "Impact of Imperfect Timekeeping on Quantum Control", Physical Review Letters 131 16, 160204 (2023).

[2] Liam Madden, Albert Akhriev, and Andrea Simonetto, 2022 IEEE International Conference on Quantum Computing and Engineering (QCE) 492 (2022) ISBN:978-1-6654-9113-6.

[3] Siwei Tan, Congliang Lang, Liang Xiang, Shudi Wang, Xinghui Jia, Ziqi Tan, Tingting Li, Jieming Yin, Yongheng Shang, Andre Python, Liqiang Lu, and Jianwei Yin, 56th Annual IEEE/ACM International Symposium on Microarchitecture 494 (2023) ISBN:9798400703294.

[4] Evan McKinney, Michael Hatridge, and Alex K. Jones, 2024 IEEE International Symposium on High-Performance Computer Architecture (HPCA) 704 (2024) ISBN:979-8-3503-9313-2.

[5] Péter Rakyta, Gregory Morse, Jakab Nádori, Zita Majnay-Takács, Oskar Mencer, and Zoltán Zimborás, "Highly optimized quantum circuits synthesized via data-flow engines", Journal of Computational Physics 500, 112756 (2024).

[6] Sahel Ashhab, Naoki Yamamoto, Fumiki Yoshihara, and Kouichi Semba, Optica Quantum 2.0 Conference and Exhibition QM4B.7 (2023) ISBN:978-1-957171-27-2.

[7] Alon Kukliansky, Ed Younis, Lukasz Cincio, and Costin Iancu, 2023 IEEE International Conference on Quantum Computing and Engineering (QCE) 814 (2023) ISBN:979-8-3503-4323-6.

[8] Wenyang Qian, Robert A. M. Basili, Mary Mehrnoosh Eshaghian-Wilner, Ashfaq Khokhar, Glenn Luecke, and James P. Vary, "Comparative Study of Variations in Quantum Approximate Optimization Algorithms for the Traveling Salesman Problem", Entropy 25 8, 1238 (2023).

[9] Nikita A. Nemkov, Evgeniy O. Kiktenko, Ilia A. Luchnikov, and Aleksey K. Fedorov, "Efficient variational synthesis of quantum circuits with coherent multi-start optimization", Quantum 7, 993 (2023).

[10] Jianxin Chen, Dawei Ding, Weiyuan Gong, Cupjin Huang, and Qi Ye, Proceedings of the 29th ACM International Conference on Architectural Support for Programming Languages and Operating Systems, Volume 2 779 (2024) ISBN:9798400703850.

[11] Sahel Ashhab, Fumiki Yoshihara, Miwako Tsuji, Mitsuhisa Sato, and Kouichi Semba, "Quantum circuit synthesis via a random combinatorial search", Physical Review A 109 5, 052605 (2024).

[12] Evan McKinney, Chao Zhou, Mingkang Xia, Michael Hatridge, and Alex K. Jones, Proceedings of the 50th Annual International Symposium on Computer Architecture 1 (2023) ISBN:9798400700958.

[13] Daniel Malz, Georgios Styliaris, Zhi-Yuan Wei, and J. Ignacio Cirac, "Preparation of Matrix Product States with Log-Depth Quantum Circuits", Physical Review Letters 132 4, 040404 (2024).

[14] Sahel Ashhab, Naoki Yamamoto, Fumiki Yoshihara, and Kouichi Semba, "Numerical analysis of quantum circuits for state preparation and unitary operator synthesis", Physical Review A 106 2, 022426 (2022).

[15] Smit Chaudhary, Patrick Huembeli, Ian MacCormack, Taylor L Patti, Jean Kossaifi, and Alexey Galda, "Towards a scalable discrete quantum generative adversarial neural network", Quantum Science and Technology 8 3, 035002 (2023).

[16] Áron Rozgonyi, Gábor Széchenyi, Orsolya Kálmán, and Tamás Kiss, "Training iterated protocols for distillation of GHZ states with variational quantum algorithms", Physics Letters A 499, 129349 (2024).

[17] Claudio Sanavio and Sauro Succi, "Lattice Boltzmann–Carleman quantum algorithm and circuit for fluid flows at moderate Reynolds number", AVS Quantum Science 6 2, 023802 (2024).

[18] Bowen Li, Ting Li, and Fei Li, "A design method for efficient variational quantum models based on specific Pauli axis", Quantum Information Processing 22 10, 387 (2023).

[19] Run-Hong He, Xu-Sheng Xu, Mark S Byrd, and Zhao-Ming Wang, "Modularized and scalable compilation for double quantum dot quantum computing", Quantum Science and Technology 9 1, 015004 (2024).

[20] Péter Rakyta and Zoltán Zimborás, "Efficient quantum gate decomposition via adaptive circuit compression", arXiv:2203.04426, (2022).

[21] Liam Madden and Andrea Simonetto, "Best Approximate Quantum Compiling Problems", arXiv:2106.05649, (2021).

[22] Anna M. Krol and Zaid Al-Ars, "Beyond Quantum Shannon: Circuit Construction for General n-Qubit Gates Based on Block ZXZ-Decomposition", arXiv:2403.13692, (2024).

[23] Alon Kukliansky, Lukasz Cincio, Ed Younis, and Costin Iancu, "Leveraging Quantum Machine Learning Generalization to Significantly Speed-up Quantum Compilation", arXiv:2405.12866, (2024).

The above citations are from Crossref's cited-by service (last updated successfully 2024-07-15 15:10:13) and SAO/NASA ADS (last updated successfully 2024-07-15 15:10:14). The list may be incomplete as not all publishers provide suitable and complete citation data.