Efficient variational synthesis of quantum circuits with coherent multi-start optimization

Nikita A. Nemkov, Evgeniy O. Kiktenko, Ilia A. Luchnikov, and Aleksey K. Fedorov

Russian Quantum Center, Skolkovo, Moscow 143026, Russia
National University of Science and Technology “MISIS”, Moscow 119049, Russia

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


We consider the problem of the variational quantum circuit synthesis into a gate set consisting of the CNOT gate and arbitrary single-qubit (1q) gates with the primary target being the minimization of the CNOT count. First we note that along with the discrete architecture search suffering from the combinatorial explosion of complexity, optimization over 1q gates can also be a crucial roadblock due to the omnipresence of local minimums (well known in the context of variational quantum algorithms but apparently underappreciated in the context of the variational compiling). Taking the issue seriously, we make an extensive search over the initial conditions an essential part of our approach. Another key idea we propose is to use parametrized two-qubit (2q) controlled phase gates, which can interpolate between the identity gate and the CNOT gate, and allow a continuous relaxation of the discrete architecture search, which can be executed jointly with the optimization over 1q gates. This coherent optimization of the architecture together with 1q gates appears to work surprisingly well in practice, sometimes even outperforming optimization over 1q gates alone (for fixed optimal architectures). As illustrative examples and applications we derive 8 CNOT and T depth 3 decomposition of the 3q Toffoli gate on the nearest-neighbor topology, rediscover known best decompositions of the 4q Toffoli gate on all 4q topologies including a 1 CNOT gate improvement on the star-shaped topology, and propose decomposition of the 5q Toffoli gate on the nearest-neighbor topology with 48 CNOT gates. We also benchmark the performance of our approach on a number of 5q quantum circuits from the ibm_qx_mapping database showing that it is highly competitive with the existing software. The algorithm developed in this work is available as a Python package CPFlow.

🇺🇦 Quantum strongly condemns the 2022 invasion of Ukraine, the loss of life and war crimes inflicted by Russian forces. For more information on our policy on publishing articles by authors based in Russian institutions, see this post

► BibTeX data

► References

[1] Peter W. Shor. ``Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer''. SIAM Journal on Computing 26, 1484–1509 (1997). arXiv:9508027.

[2] Lov K. Grover. ``Quantum mechanics helps in searching for a needle in a haystack''. Physical Review Letters 79, 325–328 (1997).

[3] Aram W. Harrow, Avinatan Hassidim, and Seth Lloyd. ``Quantum algorithm for linear systems of equations''. Physical Review Letters 103, 1–15 (2009). arXiv:0811.3171v3.

[4] A. K. Fedorov, N. Gisin, S. M. Beloussov, and A. I. Lvovsky. ``Quantum computing at the quantum advantage threshold: a down-to-business review'' (2022). arXiv:2203.17181.

[5] John Preskill. ``Quantum computing in the NISQ era and beyond''. Quantum 2, 1–20 (2018). arXiv:1801.00862.

[6] Mohammadsadegh Khazali and Klaus Mølmer. ``Fast multi-qubit gates by adiabatic evolution in interacting excited state manifolds'' (2020).

[7] Qiskit contributors (2023). code: https:/​/​doi.org/​10.5281/​zenodo.2573505.

[8] Seyon Sivarajah, Silas Dilkes, Alexander Cowtan, Will Simmons, Alec Edgington, and Ross Duncan. ``t|ket: a retargetable compiler for NISQ devices''. Quantum Science and Technology 6 (2021). arXiv:2003.10611v3.

[9] Adriano Barenco, Charles H. Bennett, Richard Cleve, David P. Divincenzo, Norman Margolus, Peter Shor, Tycho Sleator, John A. Smolin, and Harald Weinfurter. ``Elementary gates for quantum computation''. Physical Review A 52, 3457–3467 (1995). arXiv:9503016.

[10] Y. Kharkov, A. Ivanova, E. Mikhantiev, and A. Kotelnikov. ``Arline Benchmarks: Automated Benchmarking Platform for Quantum Compilers'' (2022). arXiv:2202.14025.

[11] Panagiotis Kl Barkoutsos, Jerome F. Gonthier, Igor Sokolov, Nikolaj Moll, Gian Salis, Andreas Fuhrer, Marc Ganzhorn, Daniel J. Egger, Matthias Troyer, Antonio Mezzacapo, Stefan Filipp, and Ivano Tavernelli. ``Quantum algorithms for electronic structure calculations: Particle-hole Hamiltonian and optimized wave-function expansions''. Physical Review A 98, 022322 (2018). arXiv:1805.04340.

[12] Chufan Lyu, Victor Montenegro, and Abolfazl Bayat. ``Accelerated variational algorithms for digital quantum simulation of many-body ground states''. Quantum 4, 324 (2020). arXiv:2006.09415v3.

[13] Sergey Bravyi, Alexander Kliesch, Robert Koenig, and Eugene Tang. ``Obstacles to Variational Quantum Optimization from Symmetry Protection''. Physical Review Letters 125, 260505 (2020).

[14] Chufan Lyu, Xusheng Xu, Man-Hong Yung, and Abolfazl Bayat. ``Symmetry enhanced variational quantum spin eigensolver''. Quantum 7, 899 (2023). arXiv:2203.02444.

[15] Lukasz Cincio, Kenneth Rudinger, Mohan Sarovar, and Patrick J. Coles. ``Machine Learning of Noise-Resilient Quantum Circuits''. PRX Quantum 2, 010324 (2021). arXiv:2007.01210.

[16] Yuhan Huang, Qingyu Li, Xiaokai Hou, Rebing Wu, Man-Hong Yung, Abolfazl Bayat, and Xiaoting Wang. ``Robust resource-efficient quantum variational ansatz through evolutionary algorithm''. Physical Review A 105, 052414 (2022). arXiv:2202.13714.

[17] Yuxuan Du, Tao Huang, Shan You, Min Hsiu Hsieh, and Dacheng Tao. ``Quantum circuit architecture search for variational quantum algorithms''. npj Quantum Information 2022 8:1 8, 1–8 (2022). arXiv:2010.10217.

[18] Hanrui Wang, Yongshan Ding, Jiaqi Gu, Yujun Lin, David Z. Pan, Frederic T. Chong, and Song Han. ``QuantumNAS: Noise-Adaptive Search for Robust Quantum Circuits''. Proceedings - International Symposium on High-Performance Computer Architecture 2022-April, 692–708 (2021). arXiv:2107.10845.

[19] Sophia Fuhui Lin, Sara Sussman, Casey Duckering, Pranav S Mundada, Jonathan M Baker, Rohan S Kumar, Andrew A Houck, and Frederic T Chong. ``Let Each Quantum Bit Choose Its Basis Gates'' (2022). arXiv:2208.13380.

[20] D. P. Divincenzo and J. Smolin. ``Results on two-bit gate design for quantum computers''. Proceedings Workshop on Physics and Computation, PhysComp 1994Pages 14–23 (1994). arXiv:9409111.

[21] Matthew Amy, Dmitri Maslov, Michele Mosca, and Martin Roetteler. ``A Meet-in-the-Middle Algorithm for Fast Synthesis of Depth-Optimal Quantum Circuits''. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems 32, 818–830 (2013). arXiv:1206.0758.

[22] Harsha Nagarajan, Owen Lockwood, and Carleton Coffrin. ``QuantumCircuitOpt: An Open-source Framework for Provably Optimal Quantum Circuit Design''. Proceedings of QCS 2021: 2nd International Workshop on Quantum Computing Software, Held in conjunction with SC 2021: The International Conference for High Performance Computing, Networking, Storage and AnalysisPages 55–63 (2021). arXiv:2111.11674.

[23] Yunseong Nam, Neil J. Ross, Yuan Su, Andrew M. Childs, and Dmitri Maslov. ``Automated optimization of large quantum circuits with continuous parameters''. npj Quantum Information 4 (2018). arXiv:1710.07345.

[24] Sumeet Khatri, Ryan LaRose, Alexander Poremba, Lukasz Cincio, Andrew T. Sornborger, and Patrick J. Coles. ``Quantum-assisted quantum compiling''. Quantum 3 (2019). arXiv:1807.00800.

[25] Harper R. Grimsley, Sophia E. Economou, Edwin Barnes, and Nicholas J. Mayhall. ``An adaptive variational algorithm for exact molecular simulations on a quantum computer''. Nature Communications 2019 10:1 10, 1–9 (2019). arXiv:1812.11173.

[26] Ho Lun Tang, V. O. Shkolnikov, George S. Barron, Harper R. Grimsley, Nicholas J. Mayhall, Edwin Barnes, and Sophia E. Economou. ``Qubit-ADAPT-VQE: An Adaptive Algorithm for Constructing Hardware-Efficient Ansätze on a Quantum Processor''. PRX Quantum 2, 1–15 (2021). arXiv:1911.10205v2.

[27] Ethan Smith, Marc Grau Davis, Jeffrey Larson, E D Younis, Lindsay Bassman Oftelie, Wim Lavrijsen, Costin Iancu, Marc Grau Davis, Ed Younis, Bassman Lindsay, Wim Oftelie, and Costin Lavrijsen. ``LEAP: Scaling Numerical Optimization Based Synthesis Using an Incremental Approach''. ACM Transactions on Quantum Computing 4, 1–23 (2023). arXiv:2106.11246.

[28] Richard Meister, Cica Gustiani, and Simon C. Benjamin. ``Exploring ab initio machine synthesis of quantum circuits'' (2022). arXiv:2206.11245.

[29] D. Chivilikhin, A. Samarin, V. Ulyantsev, I. Iorsh, A. R. Oganov, and O. Kyriienko. ``MoG-VQE: Multiobjective genetic variational quantum eigensolver'' (2020). arXiv:2007.04424.

[30] Lukas Franken, Bogdan Georgiev, Sascha Mücke, Moritz Wolter, Raoul Heese, Christian Bauckhage, and Nico Piatkowski. ``Quantum Circuit Evolution on NISQ Devices'' (2020).

[31] Thomas Fösel, Murphy Yuezhen Niu, Florian Marquardt, and Li Li. ``Quantum circuit optimization with deep reinforcement learning'' (2021). arXiv:2103.07585.

[32] Mathias Weiden, John Kubiatowicz, Ed Younis, and Costin Iancu. ``Ansatz Learning for Quantum Circuit Optimization''. Bulletin of the American Physical Society (2023). url: https:/​/​meetings.aps.org/​Meeting/​MAR23/​Session/​G70.6.

[33] Ed Younis, Koushik Sen, Katherine Yelick, and Costin Iancu. ``QFAST: Conflating Search and Numerical Optimization for Scalable Quantum Circuit Synthesis''. Proceedings - 2021 IEEE International Conference on Quantum Computing and Engineering, QCE 2021Pages 232–243 (2021). arXiv:2103.07093.

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

[35] Bobak Toussi Kiani, Seth Lloyd, and Reevu Maity. ``Learning Unitaries by Gradient Descent'' (2020). arXiv:2001.11897.

[36] Liam Madden and Andrea Simonetto. ``Best Approximate Quantum Compiling Problems''. ACM Transactions on Quantum Computing 3, 1–29 (2021). arXiv:2106.05649.

[37] Péter Rakyta and Zoltán Zimborás. ``Approaching the theoretical limit in quantum gate decomposition'' (2021).

[38] Ken M. Nakanishi, Takahiko Satoh, and Synge Todo. ``Quantum-gate decomposer'' (2021). arXiv:2109.13223.

[39] Vivek V. Shende, Igor L. Markov, and Stephen S. Bullock. ``Smaller two-qubit circuits for quantum communication and computation''. Proceedings - Design, Automation and Test in Europe Conference and Exhibition 2, 980–985 (2004).

[40] Vivek V. Shende, Stephen S. Bullock, and Igor L. Markov. ``Synthesis of quantum-logic circuits''. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems 25, 1000–1010 (2006). arXiv:0406176.

[41] Adi Botea, Akihiro Kishimoto, and Radu Marinescu. ``On the complexity of quantum circuit compilation''. Proceedings of the 11th International Symposium on Combinatorial Search, SoCS 2018Pages 138–142 (2018).

[42] Jarrod R. McClean, Jonathan Romero, Ryan Babbush, and Alán Aspuru-Guzik. ``The theory of variational hybrid quantum-classical algorithms''. New Journal of Physics 18, 1–20 (2016). arXiv:1509.04279.

[43] Abhinav Kandala, Antonio Mezzacapo, Kristan Temme, Maika Takita, Markus Brink, Jerry M. Chow, and Jay M. Gambetta. ``Hardware-efficient Variational Quantum Eigensolver for Small Molecules and Quantum Magnets''. Nature 549, 242–246 (2017). arXiv:1704.05018.

[44] Jarrod R. McClean, Sergio Boixo, Vadim N. Smelyanskiy, Ryan Babbush, and Hartmut Neven. ``Barren plateaus in quantum neural network training landscapes''. Nature Communications 9, 1–7 (2018). arXiv:1803.11173.

[45] Lennart Bittel and Martin Kliesch. ``Training Variational Quantum Algorithms Is NP-Hard''. Physical Review Letters 127, 120502 (2021). arXiv:2101.07267.

[46] Martin Larocca, Nathan Ju, Diego García-Martín, Patrick J. Coles, and M. Cerezo. ``Theory of overparametrization in quantum neural networks'' (2021). arXiv:2109.11676.

[47] Xiaozhen Ge, Re-bing Wu, and Herschel Rabitz. ``The Optimization Landscape of Hybrid Quantum-Classical Algorithms: from Quantum Control to NISQ Applications'' (2022). arXiv:2201.07448.

[48] Eric R. Anschuetz. ``Critical Points in Quantum Generative Models'' (2021). arXiv:2109.06957.

[49] Eric R. Anschuetz and Bobak T. Kiani. ``Quantum variational algorithms are swamped with traps''. Nature Communications 13, 7760 (2022). arXiv:2205.05786.

[50] Yiqing Zhou, E. Miles Stoudenmire, and Xavier Waintal. ``What Limits the Simulation of Quantum Computers?''. Physical Review X 10, 1–14 (2020). arXiv:2002.07730.

[51] Andrea Skolik, Jarrod R. McClean, Masoud Mohseni, Patrick van der Smagt, and Martin Leib. ``Layerwise learning for quantum neural networks''. Quantum Machine Intelligence 3 (2020). arXiv:2006.14904v1.

[52] E. Campos, D. Rabinovich, V. Akshay, and J. Biamonte. ``Training Saturation in Layerwise Quantum Approximate Optimisation''. Physical Review A 104, L030401 (2021). arXiv:2106.13814.

[53] David Wierichs, Christian Gogolin, and Michael Kastoryano. ``Avoiding local minima in variational quantum eigensolvers with the natural gradient optimizer''. Physical Review Research 2 (2020). arXiv:2004.14666.

[54] Javier Rivera-Dean, Patrick Huembeli, Antonio Acín, and Joseph Bowles. ``Avoiding local minima in Variational Quantum Algorithms with Neural Networks'' (2021). arXiv:2104.02955.

[55] Diederik P. Kingma and Jimmy Lei Ba. ``Adam: A method for stochastic optimization''. 3rd International Conference on Learning Representations, ICLR 2015 - Conference Track ProceedingsPages 1–15 (2015). arXiv:1412.6980.

[56] James Stokes, Josh Izaac, Nathan Killoran, and Giuseppe Carleo. ``Quantum Natural Gradient''. Quantum 4 (2020). arXiv:1909.02108.

[57] Tyson Jones and Simon C Benjamin. ``Robust quantum compilation and circuit optimisation via energy minimisation''. Quantum 6, 628 (2022). arXiv:1811.03147.

[58] Owen Lockwood. ``An Empirical Review of Optimization Techniques for Quantum Variational Circuits'' (2022). arXiv:2202.01389.

[59] Robert Tibshirani. ``Regression Shrinkage and Selection Via the Lasso''. Journal of the Royal Statistical Society: Series B (Methodological) 58, 267–288 (1996).

[60] David Donoho. ``Donoho, d.l.: For most large underdetermined systems of linear equations the minimal l(1)-norm solution is also the sparsest solution. communications on pure and applied mathematics 59(6), 797-829''. Communications on Pure and Applied Mathematics 59, 797 – 829 (2006).

[61] Emmanuel Candes, Justin Romberg, and Terence Tao. ``Robust Uncertainty Principles: Exact Signal Reconstruction from Highly Incomplete Frequency Information''. IEEE Transactions on Information Theory 52, 489–509 (2004). arXiv:0409186.

[62] Emmanuel J. Candès, Xiaodong Li, Yi Ma, and John Wright. ``Robust principal component analysis?''. Journal of the ACM 58, 1–37 (2011).

[63] James Bergstra, Daniel Yamins, and David Cox. ``Making a science of model search: Hyperparameter optimization in hundreds of dimensions for vision architectures''. In Sanjoy Dasgupta and David McAllester, editors, Proceedings of the 30th International Conference on Machine Learning. Volume 28 of Proceedings of Machine Learning Research, pages 115–123. Atlanta, Georgia, USA (2013). PMLR. url: https:/​/​proceedings.mlr.press/​v28/​bergstra13.html.

[64] Nikita Nemkov, Ilia Luchnikov, Evgeniy Kiktenko, and Aleksey Fedorov. ``cpflow''. https:/​/​github.com/​idnm/​cpflow (2022).

[65] James Bradbury, Roy Frostig, Peter Hawkins, Matthew James Johnson, Chris Leary, Dougal Maclaurin, George Necula, Adam Paszke, Jake VanderPlas, Skye Wanderman-Milne, and Qiao Zhang (2018). url: http:/​/​github.com/​google/​jax.

[66] Guang Song and Andreas Klappenecker. ``The simplified Toffoli gate implementation by Margolus is optimal'' (2003). arXiv:quant-ph/​0312225.

[67] Dmitri Maslov. ``Advantages of using relative-phase Toffoli gates with an application to multiple control Toffoli optimization''. Physical Review A 93, 022311 (2016). arXiv:1508.03273.

[68] Vivek V. Shende and Igor L. Markov. ``On the cnot-cost of toffoli gates''. Quantum Information and Computation 9, 461–486 (2009). arXiv:0803.2316.

[69] Norbert Schuch. ``Implementation of quantum algorithms with josephson charge qubits''. PhD thesis. Universität Regensburg. (2002). url: https:/​/​epub.uni-regensburg.de/​1511/​.

[70] Ken M. Nakanishi, Keisuke Fujii, and Synge Todo. ``Sequential minimal optimization for quantum-classical hybrid algorithms''. Physical Review Research 2, 1–11 (2020). arXiv:1903.12166.

[71] Alwin Zulehner, Stefan Hillmich, Alexandru Paler, and Robert Wille. ``ibm_qx_mapping''. https:/​/​github.com/​iic-jku/​ibm_qx_mapping (2017).

[72] Alwin Zulehner, Alexandru Paler, and Robert Wille. ``An Efficient Methodology for Mapping Quantum Circuits to the IBM QX Architectures''. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems 38, 1226–1236 (2019). arXiv:1712.04722.

[73] Harper R. Grimsley, George S. Barron, Edwin Barnes, Sophia E. Economou, and Nicholas J. Mayhall. ``Adaptive, problem-tailored variational quantum eigensolver mitigates rough parameter landscapes and barren plateaus''. npj Quantum Information 9, 19 (2023). arXiv:2204.07179.

Cited by

[1] Ryo Watanabe, Keisuke Fujii, and Hiroshi Ueda, "Variational quantum eigensolver with embedded entanglement using a tensor-network ansatz", Physical Review Research 6 2, 023009 (2024).

[2] Carolina Allende, André Fonseca de Olivera, and Efrain Buksman, "Synthesis of quantum circuits based on supervised learning and correlations", Quantum Information Processing 23 6, 204 (2024).

[3] Pedro M. Q. Cruz and Bruno Murta, "Shallow unitary decompositions of quantum Fredkin and Toffoli gates for connectivity-aware equivalent circuit averaging", APL Quantum 1 1, 016105 (2024).

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

[5] Ryo Watanabe, Keisuke Fujii, and Hiroshi Ueda, "Entangled embedding variational quantum eigensolver with tensor network ansatz", arXiv:2305.06536, (2023).

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

[7] Alon Kukliansky, Ed Younis, Lukasz Cincio, and Costin Iancu, "QFactor: A Domain-Specific Optimizer for Quantum Circuit Instantiation", arXiv:2306.08152, (2023).

[8] Arunava Majumder, Dylan Lewis, and Sougato Bose, "Variational Quantum Circuits for Multi-Qubit Gate Automata", arXiv:2209.00139, (2022).

[9] Nikita A. Nemkov, Evgeniy O. Kiktenko, and Aleksey K. Fedorov, "Barren plateaus are swamped with traps", arXiv:2405.05332, (2024).

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