Approaching the theoretical limit in quantum gate decomposition

Péter Rakyta; Zoltán Zimborás

doi:10.22331/q-2022-05-11-710

Approaching the theoretical limit in quantum gate decomposition

Péter Rakyta^1,2 and Zoltán Zimborás^3,4

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

Published:	2022-05-11, volume 6, page 710
Eprint:	arXiv:2109.06770v4
Doi:	https://doi.org/10.22331/q-2022-05-11-710
Citation:	Quantum 6, 710 (2022).

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

Abstract

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

@article{Rakyta2022approaching,
  doi = {10.22331/q-2022-05-11-710},
  url = {https://doi.org/10.22331/q-2022-05-11-710},
  title = {Approaching the theoretical limit in quantum gate decomposition},
  author = {Rakyta, P{\'{e}}ter and Zimbor{\'{a}}s, Zolt{\'{a}}n},
  journal = {{Quantum}},
  issn = {2521-327X},
  publisher = {{Verein zur F{\"{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}},
  volume = {6},
  pages = {710},
  month = may,
  year = {2022}
}

► 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://doi.org/10.1137/S0097539795293172 0pt.
https://doi.org/10.1137/S0097539795293172

[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://doi.org/10.1103/PhysRevLett.79.325 0pt.
https://doi.org/10.1103/PhysRevLett.79.325

[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://doi.org/10.1063/1.125846 0pt.
https://doi.org/10.1063/1.125846

[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://doi.org/10.1038/s41467-017-01904-7 0pt.
https://doi.org/10.1038/s41467-017-01904-7

[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://doi.org/10.1038/nphoton.2012.259 0pt.
https://doi.org/10.1038/nphoton.2012.259

[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://science.sciencemag.org/content/351/6277/1068 https://doi.org/10.1126/science.aad9480 0pt.
https://doi.org/10.1126/science.aad9480
https://science.sciencemag.org/content/351/6277/1068

[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://doi.org/10.1103/PhysRevA.100.012305 0pt.
https://doi.org/10.1103/PhysRevA.100.012305

[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://doi.org/10.1038/s41567-020-01105-y.
https://doi.org/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://doi.org/10.1126/science.abb9811.
https://doi.org/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://doi.org/10.1038/s41534-019-0217-0 0pt.
https://doi.org/10.1038/s41534-019-0217-0

[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://doi.org/10.1038/s42005-021-00616-1 0pt.
https://doi.org/10.1038/s42005-021-00616-1

[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://doi.org/10.1063/5.0046930 0pt.
https://doi.org/10.1063/5.0046930

[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://doi.org/10.1063/5.0040477 0pt.
https://doi.org/10.1063/5.0040477

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

[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://doi.org/10.1103/PhysRevA.52.3457 0pt.
https://doi.org/10.1103/PhysRevA.52.3457

[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://doi.org/10.1073/pnas.1618020114 0pt.
https://doi.org/10.1073/pnas.1618020114

[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://doi.org/10.1145/3297858.3304007 0pt.
https://doi.org/10.1145/3297858.3304007

[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://doi.org/10.1103/PhysRevA.69.062321 0pt.
https://doi.org/10.1103/PhysRevA.69.062321

[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://doi.org/10.1103/PhysRevLett.92.177902 0pt.
https://doi.org/10.1103/PhysRevLett.92.177902

[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://doi.org/10.1109/TCAD.2005.855930.
https://doi.org/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://doi.org/10.1016/0024-3795(94)90446-4 0pt.
https://doi.org/10.1016/0024-3795(94)90446-4

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

[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://doi.org/10.1109/DSD.2018.00005.
https://doi.org/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://doi.org/10.1007/978-0-387-30162-4_315 0pt.
https://doi.org/10.1007/978-0-387-30162-4_315

[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://doi.org/10.22331/q-2019-05-13-140 0pt.
https://doi.org/10.22331/q-2019-05-13-140

[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.
arXiv:2003.04462

[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://doi.ieeecomputersociety.org/10.1109/QCE52317.2021.00041 0pt.
https://doi.ieeecomputersociety.org/10.1109/QCE52317.2021.00041

[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.
arXiv:2106.11246

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

[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://doi.org/10.1088/2058-9565/abe519 0pt.
https://doi.org/10.1088/2058-9565/abe519

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

[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://doi.org/10.1103/PhysRevLett.93.130502 0pt.
https://doi.org/10.1103/PhysRevLett.93.130502

[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://dx.doi.org/10.1103/PhysRevA.93.032318 0pt.
https://doi.org/10.1103/PhysRevA.93.032318

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

[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://doi.org/10.1103/PhysRevA.69.032315 0pt.
https://doi.org/10.1103/PhysRevA.69.032315

[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://doi.org/10.1145/567806.567807.
https://doi.org/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://doi.org/10.1103/PhysRevLett.107.080502 0pt.
https://doi.org/10.1103/PhysRevLett.107.080502

[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://doi.org/10.1038/nature13171 0pt.
https://doi.org/10.1038/nature13171

[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://doi.org/10.1103/PhysRevApplied.15.064005 0pt.
https://doi.org/10.1103/PhysRevApplied.15.064005

[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://doi.org/10.1103/PhysRevLett.124.120501 0pt.
https://doi.org/10.1103/PhysRevLett.124.120501

[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://doi.org/10.1103/PhysRevApplied.13.034013 0pt.
https://doi.org/10.1103/PhysRevApplied.13.034013

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

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

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

[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://link.springer.com/book/10.1007/978-1-4842-4398-5 0pt.
https://link.springer.com/book/10.1007/978-1-4842-4398-5

Cited by

[1] 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.

[2] 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).

[3] 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).

[4] 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.

[5] 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).

[6] 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).

[7] 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.

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

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

The above citations are from Crossref's cited-by service (last updated successfully 2023-09-30 16:32:38) and SAO/NASA ADS (last updated successfully 2023-09-30 16:32:39). The list may be incomplete as not all publishers provide suitable and complete citation data.

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.