Enabling Multi-programming Mechanism for Quantum Computing in the NISQ Era

Siyuan Niu1 and Aida Todri-Sanial2,3

1LIRMM, University of Montpellier, 34095 Montpellier, France
2LIRMM, University of Montpellier, 34095 Montpellier, CNRS, France
3Eindhoven University of Technology, 5612 AE, Eindhoven, Netherlands

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


NISQ devices have several physical limitations and unavoidable noisy quantum operations, and only small circuits can be executed on a quantum machine to get reliable results. This leads to the quantum hardware under-utilization issue. Here, we address this problem and improve the quantum hardware throughput by proposing a Quantum Multi-programming Compiler (QuMC) to execute multiple quantum circuits on quantum hardware simultaneously. This approach can also reduce the total runtime of circuits. We first introduce a parallelism manager to select an appropriate number of circuits to be executed at the same time. Second, we present two different qubit partitioning algorithms to allocate reliable partitions to multiple circuits – a greedy and a heuristic. Third, we use the Simultaneous Randomized Benchmarking protocol to characterize the crosstalk properties and consider them in the qubit partition process to avoid the crosstalk effect during simultaneous executions. Finally, we enhance the mapping transition algorithm to make circuits executable on hardware using a decreased number of inserted gates. We demonstrate the performance of our QuMC approach by executing circuits of different sizes on IBM quantum hardware simultaneously. We also investigate this method on VQE algorithm to reduce its overhead.

► BibTeX data

► References

[1] Abdullah Ash-Saki, Mahabubul Alam, and Swaroop Ghosh. Analysis of crosstalk in nisq devices and security implications in multi-programming regime. In Proceedings of the ACM/​IEEE International Symposium on Low Power Electronics and Design, pages 25–30, 2020a. https:/​/​doi.org/​10.1145/​3370748.3406570.

[2] Abdullah Ash-Saki, Mahabubul Alam, and Swaroop Ghosh. Experimental characterization, modeling, and analysis of crosstalk in a quantum computer. IEEE Transactions on Quantum Engineering, 2020b. https:/​/​doi.org/​10.1109/​TQE.2020.3023338.

[3] Radoslaw C Bialczak, Markus Ansmann, Max Hofheinz, Erik Lucero, Matthew Neeley, AD O’Connell, Daniel Sank, Haohua Wang, James Wenner, Matthias Steffen, et al. Quantum process tomography of a universal entangling gate implemented with josephson phase qubits. Nature Physics, 6 (6): 409–413, 2010. https:/​/​doi.org/​10.1038/​nphys1639.

[4] Carlos Bravo-Prieto, Ryan LaRose, Marco Cerezo, Yigit Subasi, Lukasz Cincio, and Patrick Coles. Variational quantum linear solver: A hybrid algorithm for linear systems. Bulletin of the American Physical Society, 65, 2020.

[5] A Robert Calderbank and Peter W Shor. Good quantum error-correcting codes exist. Physical Review A, 54 (2): 1098, 1996. https:/​/​doi.org/​10.1103/​PhysRevA.54.1098.

[6] Marco Cerezo, Andrew Arrasmith, Ryan Babbush, Simon C Benjamin, Suguru Endo, Keisuke Fujii, Jarrod R McClean, Kosuke Mitarai, Xiao Yuan, Lukasz Cincio, et al. Variational quantum algorithms. Nature Reviews Physics, 3 (9): 625–644, 2021. https:/​/​doi.org/​10.1038/​s42254-021-00348-9.

[7] Ophelia Crawford, Barnaby van Straaten, Daochen Wang, Thomas Parks, Earl Campbell, and Stephen Brierley. Efficient quantum measurement of pauli operators in the presence of finite sampling error. Quantum, 5: 385, 2021. https:/​/​doi.org/​10.22331/​q-2021-01-20-385.

[8] Andrew W Cross, Lev S Bishop, John A Smolin, and Jay M Gambetta. Open quantum assembly language. arXiv preprint arXiv:1707.03429, 2017.

[9] Andrew W Cross, Lev S Bishop, Sarah Sheldon, Paul D Nation, and Jay M Gambetta. Validating quantum computers using randomized model circuits. Physical Review A, 100 (3): 032328, 2019. https:/​/​doi.org/​10.1103/​PhysRevA.100.032328.

[10] Poulami Das, Swamit S Tannu, Prashant J Nair, and Moinuddin Qureshi. A case for multi-programming quantum computers. In Proceedings of the 52nd Annual IEEE/​ACM International Symposium on Microarchitecture, pages 291–303, 2019. https:/​/​doi.org/​10.1145/​3352460.3358287.

[11] Eugene F Dumitrescu, Alex J McCaskey, Gaute Hagen, Gustav R Jansen, Titus D Morris, T Papenbrock, Raphael C Pooser, David Jarvis Dean, and Pavel Lougovski. Cloud quantum computing of an atomic nucleus. Physical review letters, 120 (21): 210501, 2018. https:/​/​doi.org/​10.1103/​PhysRevLett.120.210501.

[12] Alexander Erhard, Joel J Wallman, Lukas Postler, Michael Meth, Roman Stricker, Esteban A Martinez, Philipp Schindler, Thomas Monz, Joseph Emerson, and Rainer Blatt. Characterizing large-scale quantum computers via cycle benchmarking. Nature communications, 10 (1): 1–7, 2019. https:/​/​doi.org/​10.1038/​s41467-019-13068-7.

[13] Héctor Abraham et al. Qiskit: An open-source framework for quantum computing. https:/​/​qiskit.org/​, 2019.

[14] Jay M Gambetta, AD Córcoles, Seth T Merkel, Blake R Johnson, John A Smolin, Jerry M Chow, Colm A Ryan, Chad Rigetti, S Poletto, Thomas A Ohki, et al. Characterization of addressability by simultaneous randomized benchmarking. Physical review letters, 109 (24): 240504, 2012. https:/​/​doi.org/​10.1103/​PhysRevLett.109.240504.

[15] Pranav Gokhale, Olivia Angiuli, Yongshan Ding, Kaiwen Gui, Teague Tomesh, Martin Suchara, Margaret Martonosi, and Frederic T Chong. Optimization of simultaneous measurement for variational quantum eigensolver applications. In 2020 IEEE International Conference on Quantum Computing and Engineering (QCE), pages 379–390. IEEE, 2020. https:/​/​doi.org/​10.1109/​QCE49297.2020.00054.

[16] Gian Giacomo Guerreschi and Jongsoo Park. Two-step approach to scheduling quantum circuits. Quantum Science and Technology, 3 (4): 045003, 2018. https:/​/​doi.org/​10.1088/​2058-9565/​aacf0b.

[17] Vojtěch Havlíček, Antonio D Córcoles, Kristan Temme, Aram W Harrow, Abhinav Kandala, Jerry M Chow, and Jay M Gambetta. Supervised learning with quantum-enhanced feature spaces. Nature, 567 (7747): 209–212, 2019. https:/​/​doi.org/​10.1038/​s41586-019-0980-2.

[18] Toshinari Itoko, Rudy Raymond, Takashi Imamichi, and Atsushi Matsuo. Optimization of quantum circuit mapping using gate transformation and commutation. Integration, 70: 43–50, 2020. 10.1016/​j.vlsi.2019.10.004.

[19] 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 (7671): 242–246, 2017. https:/​/​doi.org/​10.1038/​nature23879.

[20] Iordanis Kerenidis and Anupam Prakash. Quantum gradient descent for linear systems and least squares. Physical Review A, 101 (2): 022316, 2020. 10.1103/​PhysRevA.101.022316.

[21] Benjamin P Lanyon, James D Whitfield, Geoff G Gillett, Michael E Goggin, Marcelo P Almeida, Ivan Kassal, Jacob D Biamonte, Masoud Mohseni, Ben J Powell, Marco Barbieri, et al. Towards quantum chemistry on a quantum computer. Nature chemistry, 2 (2): 106–111, 2010. https:/​/​doi.org/​10.1038/​nchem.483.

[22] Gushu Li, Yufei Ding, and Yuan Xie. Tackling the qubit mapping problem for nisq-era quantum devices. In Proceedings of the Twenty-Fourth International Conference on Architectural Support for Programming Languages and Operating Systems, pages 1001–1014, 2019. 10.1145/​3297858.3304023.

[23] Lei Liu and Xinglei Dou. Qucloud: A new qubit mapping mechanism for multi-programming quantum computing in cloud environment. In 2021 IEEE International Symposium on High-Performance Computer Architecture (HPCA), pages 167–178. IEEE, 2021. https:/​/​doi.org/​10.1109/​HPCA51647.2021.00024.

[24] Pranav Mundada, Gengyan Zhang, Thomas Hazard, and Andrew Houck. Suppression of qubit crosstalk in a tunable coupling superconducting circuit. Physical Review Applied, 12 (5): 054023, 2019. https:/​/​doi.org/​10.1103/​PhysRevApplied.12.054023.

[25] Prakash Murali, Jonathan M Baker, Ali Javadi-Abhari, Frederic T Chong, and Margaret Martonosi. Noise-adaptive compiler mappings for noisy intermediate-scale quantum computers. In Proceedings of the Twenty-Fourth International Conference on Architectural Support for Programming Languages and Operating Systems, pages 1015–1029, 2019. 10.1145/​3297858.3304075.

[26] 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, 2020. https:/​/​doi.org/​10.1145/​3373376.3378477.

[27] Siyuan Niu and Aida Todri-Sanial. Analyzing crosstalk error in the nisq era. In 2021 IEEE Computer Society Annual Symposium on VLSI (ISVLSI), pages 428–430, 2021. https:/​/​doi.org/​10.1109/​ISVLSI51109.2021.00084.

[28] Siyuan Niu, Adrien Suau, Gabriel Staffelbach, and Aida Todri-Sanial. A hardware-aware heuristic for the qubit mapping problem in the nisq era. IEEE Transactions on Quantum Engineering, 1: 1–14, 2020. 10.1109/​TQE.2020.3026544.

[29] Yasuhiro Ohkura, Takahiko Satoh, and Rodney Van Meter. Simultaneous quantum circuits execution on current and near-future nisq systems. arXiv preprint arXiv:2112.07091 https:/​/​doi.org/​10.1109/​TQE.2022.3164716, 2021.

[30] Elijah Pelofske, Georg Hahn, and Hristo N Djidjev. Parallel quantum annealing. Scientific Reports, 12 (1): 1–11, 2022. https:/​/​doi.org/​10.1038/​s41598-022-08394-8.

[31] Alberto Peruzzo, Jarrod McClean, Peter Shadbolt, Man-Hong Yung, Xiao-Qi Zhou, Peter J Love, Alán Aspuru-Guzik, and Jeremy L O’brien. A variational eigenvalue solver on a photonic quantum processor. Nature communications, 5: 4213, 2014. https:/​/​doi.org/​10.1038/​ncomms5213 (2014).

[32] John Preskill. Quantum Computing in the NISQ era and beyond. Quantum, 2: 79, August 2018. ISSN 2521-327X. 10.22331/​q-2018-08-06-79.

[33] Timothy J Proctor, Arnaud Carignan-Dugas, Kenneth Rudinger, Erik Nielsen, Robin Blume-Kohout, and Kevin Young. Direct randomized benchmarking for multiqubit devices. Physical review letters, 123 (3): 030503, 2019. https:/​/​doi.org/​10.1103/​PhysRevLett.123.030503.

[34] Salonik Resch, Anthony Gutierrez, Joon Suk Huh, Srikant Bharadwaj, Yasuko Eckert, Gabriel Loh, Mark Oskin, and Swamit Tannu. Accelerating variational quantum algorithms using circuit concurrency. arXiv preprint arXiv:2109.01714, 2021.

[35] Mohan Sarovar, Timothy Proctor, Kenneth Rudinger, Kevin Young, Erik Nielsen, and Robin Blume-Kohout. Detecting crosstalk errors in quantum information processors. Quantum, 4: 321, 2020. https:/​/​doi.org/​10.22331/​q-2020-09-11-321.

[36] Peter W. Shor. Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM Journal on Computing, 26 (5): 1484–1509, 1997. 10.1137/​S0097539795293172.

[37] Bochen Tan and Jason Cong. Optimality study of existing quantum computing layout synthesis tools. IEEE Transactions on Computers, 70 (9): 1363–1373, 2021. https:/​/​doi.org/​10.1109/​TC.2020.3009140.

[38] Swamit S Tannu and Moinuddin 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, pages 987–999, 2019. https:/​/​doi.org/​10.1145/​3297858.3304007.

[39] R. Wille, D. Große, L. Teuber, G. W. Dueck, and R. Drechsler. RevLib: An online resource for reversible functions and reversible circuits. In Int'l Symp. on Multi-Valued Logic, pages 220–225, 2008. URL http:/​/​www.revlib.org.

[40] Robert Wille, Lukas Burgholzer, and Alwin Zulehner. Mapping quantum circuits to ibm qx architectures using the minimal number of swap and h operations. In 2019 56th ACM/​IEEE Design Automation Conference (DAC), pages 1–6. IEEE, 2019. https:/​/​doi.org/​10.1145/​3316781.3317859.

[41] Feng Zhang, Niladri Gomes, Noah F Berthusen, Peter P Orth, Cai-Zhuang Wang, Kai-Ming Ho, and Yong-Xin Yao. Shallow-circuit variational quantum eigensolver based on symmetry-inspired hilbert space partitioning for quantum chemical calculations. Physical Review Research, 3 (1): 013039, 2021. https:/​/​doi.org/​10.1103/​PhysRevResearch.3.013039.

[42] Peng Zhao, Peng Xu, Dong Lan, Ji Chu, Xinsheng Tan, Haifeng Yu, and Yang Yu. High-contrast z z interaction using superconducting qubits with opposite-sign anharmonicity. Physical Review Letters, 125 (20): 200503, 2020. https:/​/​doi.org/​10.1103/​PhysRevLett.125.200503.

Cited by

[1] Elijah Pelofske, Georg Hahn, and Hristo N Djidjev, "Noise dynamics of quantum annealers: estimating the effective noise using idle qubits", Quantum Science and Technology 8 3, 035005 (2023).

[2] Elijah Pelofske, Georg Hahn, and Hristo N. Djidjev, "Solving larger maximum clique problems using parallel quantum annealing", Quantum Information Processing 22 5, 219 (2023).

[3] Lana Mineh and Ashley Montanaro, "Accelerating the variational quantum eigensolver using parallelism", Quantum Science and Technology 8 3, 035012 (2023).

[4] Andrew Eddins, Mario Motta, Tanvi P. Gujarati, Sergey Bravyi, Antonio Mezzacapo, Charles Hadfield, and Sarah Sheldon, "Doubling the Size of Quantum Simulators by Entanglement Forging", PRX Quantum 3 1, 010309 (2022).

[5] Jack S. Baker, Gilchan Park, Kwangmin Yu, Ara Ghukasyan, Oktay Goktas, and Santosh Kumar Radha, "Massively parallel hybrid quantum-classical machine learning for kernelized time-series classification", arXiv:2305.05881, (2023).

[6] James Mills, Debasis Sadhukhan, and Elham Kashefi, "Simplifying errors by symmetry and randomisation", arXiv:2303.02712, (2023).

[7] Siyuan Niu and Aida Todri-Sanial, "Effects of Dynamical Decoupling and Pulse-level Optimizations on IBM Quantum Computers", arXiv:2204.01471, (2022).

[8] Gilchan Park, Kun Zhang, Kwangmin Yu, and Vladimir Korepin, "Quantum multi-programming for Grover's search", Quantum Information Processing 22 1, 54 (2023).

[9] Siyuan Niu and Aida Todri-Sanial, "Multi-programming Cross Platform Benchmarking for Quantum Computing Hardware", arXiv:2206.03144, (2022).

[10] Yasuhiro Ohkura, Takahiko Satoh, and Rodney Van Meter, "Simultaneous execution of quantum circuits on current and near-future NISQ systems", arXiv:2112.07091, (2021).

[11] Siyuan Niu and Aida Todri-Sanial, "How Parallel Circuit Execution Can Be Useful for NISQ Computing?", arXiv:2112.00387, (2021).

[12] Evan E. Dobbs, Robert Basmadjian, Alexandru Paler, and Joseph S. Friedman, "Fast Swapping in a Quantum Multiplier Modelled as a Queuing Network", arXiv:2106.13998, (2021).

The above citations are from Crossref's cited-by service (last updated successfully 2023-12-07 08:24:40) and SAO/NASA ADS (last updated successfully 2023-12-07 08:24:41). The list may be incomplete as not all publishers provide suitable and complete citation data.