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.

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

► 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] Péter Rakyta and Zoltán Zimborás, "Efficient quantum gate decomposition via adaptive circuit compression", arXiv:2203.04426.

[2] Liam Madden and Andrea Simonetto, "Best Approximate Quantum Compiling Problems", arXiv:2106.05649.

[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", arXiv:2205.01121.

[4] Sahel Ashhab, Naoki Yamamoto, Fumiki Yoshihara, and Kouichi Semba, "Numerical analysis of quantum circuits for state preparation and unitary operator synthesis", arXiv:2204.13524.

The above citations are from SAO/NASA ADS (last updated successfully 2022-05-28 18:05:50). The list may be incomplete as not all publishers provide suitable and complete citation data.

On Crossref's cited-by service no data on citing works was found (last attempt 2022-05-28 18:05:49).