16.6 C
New York

Approaching the theoretical limit in quantum gate decomposition

Date:

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-12 03:00:12). 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-12 03:00:11).

  • Coinsmart. Europe’s Best Bitcoin and Crypto Exchange.Click Here
  • Platoblockchain. Web3 Metaverse Intelligence. Knowledge Amplified. Access Here.
  • Source: https://quantum-journal.org/papers/q-2022-05-11-710/

This Post was originally published on Quantum Journal

Related articles

spot_img

Recent articles

spot_img