Initial-State Dependent Optimization of Controlled Gate Operations with Quantum Computer

Wonho Jang1, Koji Terashi2, Masahiko Saito2, Christian W. Bauer3, Benjamin Nachman3, Yutaro Iiyama2, Ryunosuke Okubo1, and Ryu Sawada2

1Department of Physics, The University of Tokyo, 7-3-1 Hongo, Bunkyo-ku, Tokyo 113-0033, Japan
2International Center for Elementary Particle Physics (ICEPP), The University of Tokyo, 7-3-1 Hongo, Bunkyo-ku, Tokyo 113-0033, Japan
3Physics Division, Lawrence Berkeley National Laboratory, Berkeley, CA 94720, USA

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

Updated version: The authors have uploaded version v2 of this work to the arXiv which may contain updates or corrections not contained in the published version v1. The authors left the following comment on the arXiv:
17 pages, 7 figures. arXiv admin note: substantial text overlap with arXiv:2102.10008


There is no unique way to encode a quantum algorithm into a quantum circuit. With limited qubit counts, connectivity, and coherence times, a quantum circuit optimization is essential to make the best use of near-term quantum devices. We introduce a new circuit optimizer called AQCEL, which aims to remove redundant controlled operations from controlled gates, depending on initial states of the circuit. Especially, the AQCEL can remove unnecessary qubit controls from multi-controlled gates in polynomial computational resources, even when all the relevant qubits are entangled, by identifying zero-amplitude computational basis states using a quantum computer. As a benchmark, the AQCEL is deployed on a quantum algorithm designed to model final state radiation in high energy physics. For this benchmark, we have demonstrated that the AQCEL-optimized circuit can produce equivalent final states with much smaller number of gates. Moreover, when deploying AQCEL with a noisy intermediate scale quantum computer, it efficiently produces a quantum circuit that approximates the original circuit with high fidelity by truncating low-amplitude computational basis states below certain thresholds. Our technique is useful for a wide variety of quantum algorithms, opening up new possibilities to further simplify quantum circuits to be more effective for real devices.

In a circuit-based quantum computation, a quantum algorithm needs to be first encoded into a quantum circuit to execute it on quantum hardware. This step is crucial but there is no unique way of efficiently doing this. In this article, we introduce a new tool called AQCEL, which aims to improve circuit encoding by simplifying a set of quantum gates used to implement a quantum algorithm. The AQCEL is an “initial-state dependent” circuit optimizer: when an original algorithm is designed to work with different initial states of a quantum circuit, the AQCEL attempts to optimize the circuit by removing unnecessary quantum gates or qubit controls, depending on a specific initial state at run time. The AQCEL performs this by focusing on multi-controlled gates in the circuit, decomposing them and eliminating unnecessary operations in polynomial time, based on the measurement of computational basis states with quantum hardware. The AQCEL is deployed on a quantum algorithm to model a fundamental process in high-energy physics called parton shower. We have demonstrated that the AQCEL efficiently produces a shorter-depth quantum circuit from the original one. Moreover, the AQCEL can approximate the original final state with high fidelity, resulting in significantly improved accuracy of the produced final state, when deploying with a noisy intermediate scale superconducting quantum computer. This technique is applicable for a wide range of quantum algorithms, opening up new possibilities to further improve the encoding of quantum algorithm into quantum circuit for real devices.

► BibTeX data

► References

[1] John Preskill. ``Quantum Computing in the NISQ era and beyond''. Quantum 2, 79 (2018).

[2] Alex Mott, Joshua Job, Jean Roch Vlimant, Daniel Lidar, and Maria Spiropulu. ``Solving a Higgs optimization problem with quantum annealing for machine learning''. Nature 550, 375–379 (2017).

[3] Alexander Zlokapa, Alex Mott, Joshua Job, Jean-Roch Vlimant, Daniel Lidar, and Maria Spiropulu. ``Quantum adiabatic machine learning by zooming into a region of the energy surface''. Phys. Rev. A 102, 062405 (2020).

[4] Jay Chan, Wen Guan, Shaojun Sun, Alex Zeng Wang, Sau Lan Wu, Chen Zhou, Miron Livny, Federico Carminati, and Alberto Di Meglio. ``Application of Quantum Machine Learning to High Energy Physics Analysis at LHC using IBM Quantum Computer Simulators and IBM Quantum Computer Hardware''. PoS LeptonPhoton2019, 049 (2019).

[5] Koji Terashi, Michiru Kaneda, Tomoe Kishimoto, Masahiko Saito, Ryu Sawada, and Junichi Tanaka. ``Event Classification with Quantum Machine Learning in High-Energy Physics''. Comput. Softw. Big Sci. 5, 2 (2021).

[6] Wen Guan, Gabriel Perdue, Arthur Pesah, Maria Schuld, Koji Terashi, Sofia Vallecorsa, and Jean-Roch Vlimant. ``Quantum machine learning in high energy physics''. Mach. Learn.: Sci. Technol. 2, 011003 (2021).

[7] Vasilis Belis, Samuel González-Castillo, Christina Reissel, Sofia Vallecorsa, Elías F. Combarro, Günther Dissertori, and Florentin Reiter. ``Higgs analysis with quantum classifiers''. EPJ Web Conf. 251, 03070 (2021).

[8] Alexander Zlokapa, Abhishek Anand, Jean-Roch Vlimant, Javier M. Duarte, Joshua Job, Daniel Lidar, and Maria Spiropulu. ``Charged particle tracking with quantum annealing-inspired optimization''. Quantum Mach. Intell. 3, 27 (2021).

[9] Cenk Tüysüz, Federico Carminati, Bilge Demirköz, Daniel Dobos, Fabio Fracas, Kristiane Novotny, Karolos Potamianos, Sofia Vallecorsa, and Jean-Roch Vlimant. ``Particle Track Reconstruction with Quantum Algorithms''. EPJ Web Conf. 245, 09013 (2020).

[10] Illya Shapoval and Paolo Calafiura. ``Quantum Associative Memory in HEP Track Pattern Recognition''. EPJ Web Conf. 214, 01012 (2019).

[11] Frederic Bapst, Wahid Bhimji, Paolo Calafiura, Heather Gray, Wim Lavrijsen, and Lucy Linder. ``A Pattern Recognition Algorithm for Quantum Annealers''. Comput. Softw. Big Sci. 4, 1 (2020).

[12] Annie Y. Wei, Preksha Naik, Aram W. Harrow, and Jesse Thaler. ``Quantum algorithms for jet clustering''. Phys. Rev. D 101, 094015 (2020).

[13] Souvik Das, Andrew J. Wildridge, Sachin B. Vaidya, and Andreas Jung. ``Track clustering with a quantum annealer for primary vertex reconstruction at hadron colliders''. arXiv:1903.08879 [hep-ex] (2019) arXiv:1903.08879.

[14] Kyle Cormier, Riccardo Di Sipio, and Peter Wittek. ``Unfolding measurement distributions via quantum annealing''. JHEP 11, 128 (2019).

[15] Davide Provasoli, Benjamin Nachman, Christian Bauer, and Wibe A de Jong. ``A quantum algorithm to efficiently sample from interfering binary trees''. Quantum Sci. Technol. 5, 035004 (2020).

[16] Benjamin Nachman, Davide Provasoli, Wibe A. de Jong, and Christian W. Bauer. ``Quantum algorithm for high energy physics simulations''. Phys. Rev. Lett. 126 (2021).

[17] Christian W. Bauer, Wibe A. De Jong, Benjamin Nachman, and Miroslav Urbanek. ``Unfolding quantum computer readout noise''. npj Quantum Inf. 6, 84 (2020).

[18] Yanzhu Chen, Maziar Farahzad, Shinjae Yoo, and Tzu-Chieh Wei. ``Detector tomography on IBM 5-qubit quantum computers and mitigation of imperfect measurement''. Phys. Rev. A 100, 052315 (2019).

[19] A. Dewes, F. R. Ong, V. Schmitt, R. Lauro, N. Boulant, P. Bertet, D. Vion, and D. Esteve. ``Characterization of a Two-Transmon Processor with Individual Single-Shot Qubit Readout''. Phys. Rev. Lett. 108, 057002 (2012).

[20] Michael R Geller and Mingyu Sun. ``Toward efficient correction of multiqubit measurement errors: pair correlation method''. Quantum Sci. Technol. 6, 025009 (2021).

[21] Michael R Geller. ``Rigorous measurement error correction''. Quantum Sci. Technol. 5, 03LT01 (2020).

[22] Rebecca Hicks, Christian W. Bauer, and Benjamin Nachman. ``Readout rebalancing for near-term quantum computers''. Phys. Rev. A 103, 022407 (2021).

[23] E. F. Dumitrescu, A. J. McCaskey, G. Hagen, G. R. Jansen, T. D. Morris, T. Papenbrock, R. C. Pooser, D. J. Dean, and P. Lougovski. ``Cloud Quantum Computing of an Atomic Nucleus''. Phys. Rev. Lett. 120, 210501 (2018).

[24] Suguru Endo, Simon C. Benjamin, and Ying Li. ``Practical Quantum Error Mitigation for Near-Future Applications''. Phys. Rev. X 8, 031027 (2018).

[25] Kristan Temme, Sergey Bravyi, and Jay M. Gambetta. ``Error Mitigation for Short-Depth Quantum Circuits''. Phys. Rev. Lett. 119, 180509 (2017).

[26] Abhinav Kandala, Kristan Temme, Antonio D. Córcoles, Antonio Mezzacapo, Jerry M. Chow, and Jay M. Gambetta. ``Error mitigation extends the computational reach of a noisy quantum processor''. Nature 567, 491–495 (2019).

[27] Andre He, Benjamin Nachman, Wibe A. de Jong, and Christian W. Bauer. ``Zero-noise extrapolation for quantum-gate error mitigation with identity insertions''. Phys. Rev. A 102, 012426 (2020).

[28] Matthew Otten and Stephen K. Gray. ``Recovering noise-free quantum observables''. Phys. Rev. A 99, 012338 (2019).

[29] Gadi Aleksandrowicz, et al. ``Qiskit: An Open-source Framework for Quantum Computing''. Zenodo. (2019).

[30] Seyon Sivarajah, Silas Dilkes, Alexander Cowtan, Will Simmons, Alec Edgington, and Ross Duncan. ``t|ket$\rangle$: a retargetable compiler for NISQ devices''. Quantum Sci. Technol. 6, 014003 (2020).

[31] Thomas Häner, Damian S Steiger, Krysta Svore, and Matthias Troyer. ``A software methodology for compiling quantum programs''. Quantum Sci. Technol. 3, 020501 (2018).

[32] Alexander S. Green, Peter LeFanu Lumsdaine, Neil J. Ross, Peter Selinger, and Benoı̂t Valiron. ``Quipper: a scalable quantum programming language''. SIGPLAN Not. 48, 333–342 (2013).

[33] Ali JavadiAbhari, Shruti Patil, Daniel Kudrow, Jeff Heckey, Alexey Lvov, Frederic T. Chong, and Margaret Martonosi. ``ScaffCC: Scalable compilation and analysis of quantum programs''. Parallel Comput. 45, 2–17 (2015).

[34] Krysta Svore, Martin Roetteler, Alan Geller, Matthias Troyer, John Azariah, Christopher Granade, Bettina Heim, Vadym Kliuchnikov, Mariia Mykhailova, and Andres Paz. ``Q#: Enabling Scalable Quantum Computing and Development with a High-level DSL''. In Proceedings of the Real World Domain Specific Languages Workshop 2018. Pages 1–10. Association for Computing Machinery (2018).

[35] Nathan Killoran, Josh Izaac, Nicolás Quesada, Ville Bergholm, Matthew Amy, and Christian Weedbrook. ``Strawberry Fields: A Software Platform for Photonic Quantum Computing''. Quantum 3, 129 (2019).

[36] Robert S. Smith, Michael J. Curtis, and William J. Zeng. ``A Practical Quantum Instruction Set Architecture''. arXiv:1608.03355 [quant-ph] (2016) arXiv:1608.03355.

[37] Damian S. Steiger, Thomas Häner, and Matthias Troyer. ``ProjectQ: an open source software framework for quantum computing''. Quantum 2, 49 (2018).

[38] Cirq Developers. ``Cirq''. Zenodo. (2021).

[39] Alexander J. McCaskey, Eugene F. Dumitrescu, Dmitry Liakh, Mengsu Chen, Wu-chun Feng, and Travis S. Humble. ``A language and hardware independent approach to quantum–classical computing''. SoftwareX 7, 245–254 (2018).

[40] Prakash Murali, Norbert Matthias Linke, Margaret Martonosi, Ali Javadi Abhari, Nhung Hong Nguyen, and Cinthia Huerta Alderete. ``Full-stack, real-system quantum computer studies: architectural comparisons and design insights''. In Proceedings of the 46th International Symposium on Computer Architecture. Pages 527–540. (2019).

[41] Robert S Smith, Eric C Peterson, Erik J Davis, and Mark G Skilbeck. ``quilc: An Optimizing Quil Compiler''. Zenodo. (2020).

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

[43] Davide Venturelli, Minh Do, Bryan O'Gorman, Jeremy Frank, Eleanor Rieffel, Kyle E. C. Booth, Thanh Nguyen, Parvathi Narayan, and Sasha Nanda. ``Quantum Circuit Compilation: An Emerging Application for Automated Reasoning''. In Proceedings of the Scheduling and Planning Applications Workshop (SPARK2019). (2019). url:​CorpusID:115143379.

[44] Prakash Murali, Jonathan M. Baker, Ali Javadi Abhari, Frederic T. Chong, and Margaret Martonosi. ``Noise-Adaptive Compiler Mappings for Noisy Intermediate-Scale Quantum Computers''. arXiv:1901.11054 [quant-ph] (2019) arXiv:1901.11054.

[45] Prakash Murali, David C. Mckay, Margaret Martonosi, and Ali Javadi-Abhari. ``Software Mitigation of Crosstalk on Noisy Intermediate-Scale Quantum Computers''. In Proceedings of the Twenty-Fifth International Conference on Architectural Support for Programming Languages and Operating Systems. Pages 1001–1016. ASPLOS '20. Association for Computing Machinery (2020).

[46] Eric C. Peterson, Gavin E. Crooks, and Robert S. Smith. ``Fixed-Depth Two-Qubit Circuits and the Monodromy Polytope''. Quantum 4, 247 (2020).

[47] Nelson Leung, Mohamed Abdelhafez, Jens Koch, and David Schuster. ``Speedup for quantum optimal control from automatic differentiation based on graphics processing units''. Phys. Rev. A 95, 042318 (2017).

[48] Pranav Gokhale, Yongshan Ding, Thomas Propson, Christopher Winkler, Nelson Leung, Yunong Shi, David I. Schuster, Henry Hoffmann, and Frederic T. Chong. ``Partial compilation of variational algorithms for noisy intermediate-scale quantum machines''. In Proceedings of the 52nd Annual IEEE/​ACM International Symposium on Microarchitecture. Page 266–278. Association for Computing Machinery (2019).

[49] Ji Liu, Luciano Bello, and Huiyang Zhou. ``Relaxed Peephole Optimization: A Novel Compiler Optimization for Quantum Circuits''. arXiv:2012.07711 [quant-ph] (2020) arXiv:2012.07711.

[50] 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''. Phys. Rev. A 52, 3457 (1995).

[51] Dmitri Maslov. ``Advantages of using relative-phase Toffoli gates with an application to multiple control Toffoli optimization''. Phys. Rev. A 93, 022311 (2016).

[52] D. Michael Miller, Robert Wille, and Rolf Drechsler. ``Reducing reversible circuit cost by adding lines''. In 2010 40th IEEE International Symposium on Multiple-Valued Logic. Pages 217–222. (2010).

[53] Pranav Gokhale, Jonathan M. Baker, Casey Duckering, Natalie C. Brown, Kenneth R. Brown, and Frederic T. Chong. ``Asymptotic improvements to quantum circuits via qutrits''. In Proceedings of the 46th International Symposium on Computer Architecture. Page 554–566. Association for Computing Machinery (2019).

[54] Yushi Wang and Marek Perkowski. ``Improved complexity of quantum oracles for ternary grover algorithm for graph coloring''. In 2011 41st IEEE International Symposium on Multiple-Valued Logic. Pages 294–301. (2011).

[55] Alexey Galda, Michael Cubeddu, Naoki Kanazawa, Prineha Narang, and Nathan Earnest-Noble. ``Implementing a Ternary Decomposition of the Toffoli Gate on Fixed-Frequency Transmon Qutrits''. arXiv:2109.00558 [quant-ph] (2021) arXiv:2109.00558.

[56] Toshiaki Inada, Wonho Jang, Yutaro Iiyama, Koji Terashi, Ryu Sawada, Junichi Tanaka, and Shoji Asai. ``Measurement-Free Ultrafast Quantum Error Correction by Using Multi-Controlled Gates in Higher-Dimensional State Space''. arXiv:2109.00086 [quant-ph] (2021) arXiv:2109.00086.

[57] Yuchen Wang, Zixuan Hu, Barry C. Sanders, and Sabre Kais. ``Qudits and High-Dimensional Quantum Computing''. Front. Phys. 8, 479 (2020).

[58] T. C. Ralph, K. J. Resch, and A. Gilchrist. ``Efficient Toffoli gates using qudits''. Phys. Rev. A 75, 022313 (2007).

[59] E. O. Kiktenko, A. S. Nikolaeva, Peng Xu, G. V. Shlyapnikov, and A. K. Fedorov. ``Scalable quantum computing with qudits on a graph''. Phys. Rev. A 101, 022304 (2020).

[60] Jing Zhong and Jon C. Muzio. ``Using Crosspoint Faults in Simplifying Toffoli Networks''. In 2006 IEEE North-East Workshop on Circuits and Systems. Pages 129–132. (2006).

[61] Ketan N. Patel, Igor L. Markov, and John P. Hayes. ``Optimal synthesis of linear reversible circuits''. Quantum Inf. Comput. 8, 282–294 (2008).

[62] Matthew Amy, Parsiad Azimzadeh, and Michele Mosca. ``On the controlled-NOT complexity of controlled-NOT–phase circuits''. Quantum Sci. Technol. 4, 015002 (2018).

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

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

[65] Bob Coecke and Ross Duncan. ``Interacting quantum observables: categorical algebra and diagrammatics''. New J. Phys. 13, 043016 (2011).

[66] Ross Duncan, Aleks Kissinger, Simon Perdrix, and John van de Wetering. ``Graph-theoretic Simplification of Quantum Circuits with the ZX-calculus''. Quantum 4, 279 (2020).

[67] Miriam Backens. ``The ZX-calculus is complete for stabilizer quantum mechanics''. New J. Phys. 16, 093021 (2014).

[68] Guido Van Rossum and Fred L. Drake. ``Python 3 Reference Manual''. CreateSpace. Scotts Valley, CA (2009). url:.

[69] UTokyo-ICEPP. ``AQCEL''. GitHub. (2022). url:​UTokyo-ICEPP/​aqcel.

[70] David C. McKay, Christopher J. Wood, Sarah Sheldon, Jerry M. Chow, and Jay M. Gambetta. ``Efficient Z gates for quantum computing''. Phys. Rev. A 96, 022330 (2017).

[71] Michael A. Nielsen and Isaac L. Chuang. ``Quantum Computation and Quantum Information''. Cambridge University Press. (2000).

[72] Chao Song, Kai Xu, Wuxin Liu, Chui-ping Yang, Shi-Biao Zheng, Hui Deng, Qiwei Xie, Keqiang Huang, Qiujiang Guo, Libo Zhang, Pengfei Zhang, Da Xu, Dongning Zheng, Xiaobo Zhu, H. Wang, Y.-A. Chen, C.-Y. Lu, Siyuan Han, and Jian-Wei Pan. ``10-Qubit Entanglement and Parallel Logic Operations with a Superconducting Circuit''. Phys. Rev. Lett. 119, 180511 (2017).

[73] Ming Gong, Ming-Cheng Chen, Yarui Zheng, Shiyu Wang, Chen Zha, Hui Deng, Zhiguang Yan, Hao Rong, Yulin Wu, Shaowei Li, Fusheng Chen, Youwei Zhao, Futian Liang, Jin Lin, Yu Xu, Cheng Guo, Lihua Sun, Anthony D. Castellano, Haohua Wang, Chengzhi Peng, Chao-Yang Lu, Xiaobo Zhu, and Jian-Wei Pan. ``Genuine 12-Qubit Entanglement on a Superconducting Quantum Processor''. Phys. Rev. Lett. 122, 110501 (2019).

[74] Ken X. Wei, Isaac Lauer, Srikanth Srinivasan, Neereja Sundaresan, Douglas T. McClure, David Toyli, David C. McKay, Jay M. Gambetta, and Sarah Sheldon. ``Verifying multipartite entangled Greenberger-Horne-Zeilinger states via multiple quantum coherences''. Phys. Rev. A 101, 032343 (2020).

[75] Kathleen E. Hamilton, Tyler Kharazi, Titus Morris, Alexander J. McCaskey, Ryan S. Bennink, and Raphael C. Pooser. ``Scalable quantum processor noise characterization''. arXiv:2006.01805 [quant-ph] (2020) arXiv:2006.01805.

Cited by

[1] Anthony N. Ciavarella, Stephan Caspar, Marc Illa, and Martin J. Savage, "State Preparation in the Heisenberg Model through Adiabatic Spiraling", Quantum 7, 970 (2023).

[2] Anthony N. Ciavarella, Stephan Caspar, Hersh Singh, and Martin J. Savage, "Preparation for quantum simulation of the (1+1) -dimensional O(3) nonlinear σ model using cold atoms", Physical Review A 107 4, 042404 (2023).

[3] Roland C. Farrell, Ivan A. Chernyshev, Sarah J. M. Powell, Nikita A. Zemlevskiy, Marc Illa, and Martin J. Savage, "Preparations for quantum simulations of quantum chromodynamics in 1+1 dimensions. II. Single-baryon β -decay in real time", Physical Review D 107 5, 054513 (2023).

[4] Yanbin Chen and Yannick Stade, Lecture Notes in Computer Science 14284, 164 (2023) ISBN:978-3-031-44244-5.

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