Research progress of distributed quantum computing

doi:10.3969/j.issn.1007-5461.2024.01.001

Abstract

Abstract: Efficient qubit extension is a fundamental problem that needs to be solved to obtain quantum speedup advantage for quantum computing. Due to its high feasibility and flexibility, distributed quantum computing (DQC) has become one of the key techniques for solving the qubit extension problem. According to different inter-chip communication modes, DQC can be divided into two types, teleportation-based and circuit-cutting-based DQC. The former mainly plays for the fault-tolerant quantum computing, while the latter is considered to effectively enhance the computing power of quantum computers in the noisy intermediate scale quantum (NISQ) era. In the long run, as one of the main applications of quantum network, DQC can efficiently harness the huge number of quantum computers connected to quantum networks to solve non-trivial problems. First, the origin and types of DQC are introduced. Then, the fundamentals and development of the two types of DQC, as well as widely studied application algorithms and compiling optimization methods, are provided.

Key words: quantum information, distributed quantum computing, quantum teleportation, quantum circuit cutting

CLC Number:

O413.1

WANG Shengbin , DOU Menghan , WU Yuchun , GUO Guoping , GUO Guangcan . Research progress of distributed quantum computing[J]. Chinese Journal of Quantum Electronics, 2024, 41(1): 1-25.

References

[1] Shor P W. Algorithms for quantum computation: discrete logarithms and factoring [C]. Proceedings 35th annual symposium on foundations of computer science. IEEE, 1994: 124-134.
[2] Grover L K. Quantum mechanics helps in searching for a needle in a haystack [J]. Physical Review Letters, 1997, 79(2): 325.
[3] Harrow A W, Hassidim A, Lloyd S. Quantum algorithm for linear systems of equations [J]. Physical Review Letters, 2009, 103(15): 150502.
[4] Lambert N, Chen Y N, Cheng Y C, et al. Quantum biology [J]. Nature Physics, 2013, 9(1): 10-18.
[5] Nielsen M A, Chuang I L. Quantum computation and quantum information [M]. Cambridge university press, 2010.
[6] Biamonte J, Wittek P, Pancotti N, et al. Quantum machine learning [J]. Nature, 2017, 549(7671): 195-202.
[7] Daley A J, Bloch I, Kokail C, et al. Practical quantum advantage in quantum simulation [J]. Nature, 2022, 607(7920): 667-676.
[8] Babbush R, Huggins W J, Berry D W, et al. Quantum simulation of exact electron dynamics can be more efficient than classical mean-field methods [J]. Nature Communications, 2023, 14(1): 4058.
[9] Herman D, Googin C, Liu X, et al. Quantum computing for finance [J]. Nature Reviews Physics, 2023: 1-16.
[10] Fowler A G, Mariantoni M, Martinis J M, et al. Surface codes: Towards practical large-scale quantum computation [J]. Physical Review A, 2012, 86(3): 032324.
[11] Kivlichan I D, Gidney C, Berry D W, et al. Improved fault-tolerant quantum simulation of condensed-phase correlated electrons via trotterization [J]. Quantum, 2020, 4: 296.
[12] Lee J, Berry D W, Gidney C, et al. Even more efficient quantum computations of chemistry through tensor hypercontraction [J]. PRX Quantum, 2021, 2(3): 030305.
[13] Gidney C, Eker? M. How to factor 2048 bit RSA integers in 8 hours using 20 million noisy qubits [J]. Quantum, 2021, 5: 433.
[14] Higgott O, Breuckmann N P. Subsystem codes with high thresholds by gauge fixing and reduced qubit overhead [J]. Physical Review X, 2021, 11(3): 031039.
[15] Zwanenburg F A, Dzurak A S, Morello A, et al. Silicon quantum electronics [J]. Reviews of Modern Physics, 2013, 85(3): 961.
[16] Van Meter R, Devitt S J. Local and distributed quantum computation [OL]. 2016, arXiv:1605.06951, https://arxiv.org/abs/1605.06951.
[17] Zhang X, Li H O, Cao G, et al. Semiconductor quantum computation [J]. National Science Review, 2019, 6(1): 32-54.
[18] Gibney E. Underdog tech makes gains in quantum computer race [J]. Nature, 2020, 587(7834): 342-343.
[19] Wang P, Luan C Y, Qiao M, et al. Single ion qubit with estimated coherence time exceeding one hour [J]. Nature Communications, 2021, 12(1): 233.
[20] Li X W, Fu X, Yan F, et al. Current Status and Future Development of Quantum Computation [J]. Strategic Study of CAE, 2022, 24(4): 133-144(in Chinese).
李晓巍, 付祥, 燕飞, 等. 量子计算研究现状与未来发展 [J]. 中国工程科学, 2022, 24(4): 133-144.
[21] Pelofske E, B?rtschi A, Eidenbenz S. Quantum volume in practice: What users can expect from nisq devices [J]. IEEE Transactions on Quantum Engineering, 2022, 3: 1-19.
[22] Philips S G J, M?dzik M T, Amitonov S V, et al. Universal control of a six-qubit quantum processor in silicon [J]. Nature, 2022, 609(7929): 919-924.
[23] Benhelm J, Kirchmair G, Roos C F, et al. Towards fault-tolerant quantum computing with trapped ions [J]. Nature Physics, 2008, 4(6): 463-466.
[24] Linke N M, Gutierrez M, Landsman K A, et al. Fault-tolerant quantum error detection [J]. Science Advances, 2017, 3(10): e1701074.
[25] Barends R, Kelly J, Megrant A, et al. Superconducting quantum circuits at the surface code threshold for fault tolerance [J]. Nature, 2014, 508(7497): 500-503.
[26] Takita M, Cross A W, Córcoles A D, et al. Experimental demonstration of fault-tolerant state preparation with superconducting qubits [J]. Physical Review Letters, 2017, 119(18): 180501.
[27] IBM quantum, https://quantum-computing.ibm.com/services/resources?system=ibm_seattle
[28] quafu, https://quafu.baqis.ac.cn/#/computerDetail/mapView?system_id=2&type=ScQ-P136
[29] Malinowski M, Allcock D T C, Ballance C J. How to wire a 1000-qubit trapped ion quantum computer [OL]. 2023, arXiv:2305.12773, https://arxiv.org/abs/2305.12773.
[30] Ovide A, Rodrigo S, Bandic M, et al. Mapping quantum algorithms to multi-core quantum computing architectures [OL]. 2023, arXiv:2303.16125, https://arxiv.org/abs/2303.16125.
[31] Kimble H J. The quantum internet [J]. Nature, 2008, 453(7198): 1023-1030.
[32] Wehner S, Elkouss D, Hanson R. Quantum internet: A vision for the road ahead [J]. Science, 2018, 362(6412): eaam9288.
[33] Cacciapuoti A S, Caleffi M, Tafuri F, et al. Quantum internet: Networking challenges in distributed quantum computing [J]. IEEE Network, 2019, 34(1): 137-143.
[34] Avis G, Rozp?dek F, Wehner S. Analysis of multipartite entanglement distribution using a central quantum-network node [J]. Physical Review A, 2023, 107(1): 012609.
[35] Yepez J. Type-II quantum computers [J]. International Journal of Modern Physics C, 2001, 12(09): 1273-1284.
[36] Caleffi M, Amoretti M, Ferrari D, et al. Distributed quantum computing: a survey [OL]. 2022, arXiv:2212.10609, https://arxiv.org/abs/2212.10609.
[37] Cleve R, Buhrman H. Substituting quantum entanglement for communication [J]. Physical Review A, 1997, 56(2): 1201.
[38] Cuomo D, Caleffi M, Cacciapuoti A S. Towards a distributed quantum computing ecosystem [J]. IET Quantum Communication, 2020, 1(1): 3-8.
[39] Van Meter R, Ladd T D, Fowler A G, et al. Distributed quantum computation architecture using semiconductor nanophotonics [J]. International Journal of Quantum Information, 2010, 8(01n02): 295-323.
[40] Bravyi S, Smith G, Smolin J A. Trading classical and quantum computational resources [J]. Physical Review X, 2016, 6(2): 021043.
[41] Fujii K, Mizuta K, Ueda H, et al. Deep Variational Quantum Eigensolver: a divide-and-conquer method for solving a larger problem with smaller size quantum computers [J]. PRX Quantum, 2022, 3(1): 010346.
[42] Dunjko V, Ge Y, Cirac J I. Computational speedups using small quantum devices [J]. Physical Review Letters, 2018, 121(25): 250501.
[43] Ge Y, Dunjko V. A hybrid algorithm framework for small quantum computers with application to finding Hamiltonian cycles [J]. Journal of Mathematical Physics, 2020, 61(1).
[44] Li J, Alam M, Ghosh S. Large-scale quantum approximate optimization via divide-and-conquer [J]. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2022.
[45] Hua F, Jin Y, Chen Y, et al. Exploiting qubit reuse through mid-circuit measurement and reset [OL]. 2022, arXiv:2211.01925, https://arxiv.org/abs/2211.01925.
[46] Bennett C H, Brassard G, Crépeau C, et al. Teleporting an unknown quantum state via dual classical and Einstein-Podolsky-Rosen channels [J]. Physical Review Letters, 1993, 70(13): 1895.
[47] Einstein A, Podolsky B, Rosen N. Can quantum-mechanical description of physical reality be considered complete? [J]. Physical Review, 1935, 47(10): 777.
[48] Wootters W K, Zurek W H. A single quantum cannot be cloned [J]. Nature, 1982, 299(5886): 802-803.
[49] Gottesman D, Chuang I L. Quantum teleportation is a universal computational primitive [OL]. 1999, arXiv:quant-ph/9908010, https://arxiv.org/abs/quant-ph/9908010.
[50] Zukowski M, Zeilinger A, Horne M, et al. " Event-ready-detectors" Bell experiment via entanglement swapping [J]. Physical Review Letters, 1993, 71(26).
[51] Cuomo D, Caleffi M, Krsulich K, et al. Optimized compiler for distributed quantum computing [J]. ACM Transactions on Quantum Computing, 2023, 4(2): 1-29.
[52] Eisert J, Jacobs K, Papadopoulos P, et al. Optimal local implementation of nonlocal quantum gates [J]. Physical Review A, 2000, 62(5): 052317.
[53] Yimsiriwattana A, Lomonaco Jr S J. Generalized GHZ states and distributed quantum computing [OL]. 2004, arXiv:quant-ph/0402148, https://arxiv.org/abs/quant-ph/0402148.
[54] Yimsiriwattana A, Lomonaco Jr S J. Distributed quantum computing: A distributed Shor algorithm [C]. Quantum Information and Computation II. SPIE, 2004, 5436: 360-372.
[55] Chou K S, Blumoff J Z, Wang C S, et al. Deterministic teleportation of a quantum gate between two logical qubits [J]. Nature, 2018, 561(7723): 368-373.
[56] Liu X, Hu X M, Zhu T X, et al. Distributed quantum computing over 7.0 km [OL]. 2023, arXiv:2307.15634, https://arxiv.org/abs/2307.15634.
[57] Boschi D, Branca S, De Martini F, et al. Experimental realization of teleporting an unknown pure quantum state via dual classical and Einstein-Podolsky-Rosen channels [J]. Physical Review Letters, 1998, 80(6): 1121.
[58] Popescu S. An optical method for teleportation [OL]. 1995, arXiv:quant-ph/9501020, https://arxiv.org/abs/quant-ph/9501020.
[59] Bouwmeester D, Pan J W, Mattle K, et al. Experimental quantum teleportation [J]. Nature, 1997, 390(6660): 575-579.
[60] Nielsen M A, Knill E, Laflamme R. Complete quantum teleportation using nuclear magnetic resonance [J]. Nature, 1998, 396(6706): 52-55.
[61] Duan L M, Lukin M D, Cirac J I, et al. Long-distance quantum communication with atomic ensembles and linear optics [J]. Nature, 2001, 414(6862): 413-418.
[62] Riebe M, H?ffner H, Roos C F, et al. Deterministic quantum teleportation with atoms [J]. Nature, 2004, 429(6993): 734-737.
[63] Kurpiers P, Magnard P, Walter T, et al. Deterministic quantum state transfer and remote entanglement using microwave photons [J]. Nature, 2018, 558(7709): 264-267.
[64] Brunner N, Cavalcanti D, Pironio S, et al. Bell nonlocality[J]. Reviews of Modern Physics, 2014, 86(2): 419.
[65] Wittmann B, Ramelow S, Steinlechner F, et al. Loophole-free Einstein–Podolsky–Rosen experiment via quantum steering [J]. New Journal of Physics, 2012, 14(5): 053030.
[66] Hensen B, Bernien H, Dréau A E, et al. Loophole-free Bell inequality violation using electron spins separated by 1.3 kilometres [J]. Nature, 2015, 526(7575): 682-686.
[67] Giustina M, Versteegh M A M, Wengerowsky S, et al. Significant-loophole-free test of Bell’s theorem with entangled photons [J]. Physical Review Letters, 2015, 115(25): 250401.
[68] Li M H, Wu C, Zhang Y, et al. Test of local realism into the past without detection and locality loopholes [J]. Physical Review Letters, 2018, 121(8): 080404.
[69] Rosenfeld W, Burchardt D, Garthoff R, et al. Event-ready Bell test using entangled atoms simultaneously closing detection and locality loopholes [J]. Physical Review Letters, 2017, 119(1): 010402.
[70] Storz S, Sch?r J, Kulikov A, et al. Loophole-free Bell inequality violation with superconducting circuits [J]. Nature, 2023, 617(7960): 265-270.
[71] Duan L M, Madsen M J, Moehring D L, et al. Probabilistic quantum gates between remote atoms through interference of optical frequency qubits [J]. Physical Review A, 2006, 73(6): 062324.
[72] Wan Y, Kienzler D, Erickson S D, et al. Quantum gate teleportation between separated qubits in a trapped-ion processor [J]. Science, 2019, 364(6443): 875-878.
[73] Qiu J, Liu Y, Niu J, et al. Deterministic quantum teleportation between distant superconducting chips [OL]. 2023, arXiv:2302.08756, https://arxiv.org/abs/2302.08756.
[74] Hucul D, Inlek I V, Vittorini G, et al. Modular entanglement of atomic qubits using photons and phonons [J]. Nature Physics, 2015, 11(1): 37-42.
[75] Zhong Y, Chang H S, Bienfait A, et al. Deterministic multi-qubit entanglement in a quantum network [J]. Nature, 2021, 590(7847): 571-575.
[76] Daiss S, Langenfeld S, Welte S, et al. A quantum-logic gate between distant quantum-network modules [J]. Science, 2021, 371(6529): 614-617.
[77] Krutyanskiy V, Galli M, Krcmarsky V, et al. Entanglement of trapped-ion qubits separated by 230 meters [J]. Physical Review Letters, 2023, 130(5): 050803.
[78] Sahu R, Qiu L, Hease W, et al. Entangling microwaves with light [J]. Science, 2023, 380(6646): 718-721.
[79] Gyongyosi L, Imre S. Scalable distributed gate-model quantum computers [J]. Scientific Reports, 2021, 11(1): 5172.
[80] H?ner T, Steiger D S, Hoefler T, et al. Distributed quantum computing with qmpi [C]. Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis. 2021: 1-13.
[81] Davarzani Z, Zomorodi M, Houshmand M. A hierarchical approach for building distributed quantum systems [J]. Scientific Reports, 2022, 12(1): 15421.
[82] Grover L K. Quantum telecomputation [OL]. 1997, arXiv:quant-ph/9704012, https://arxiv.org/abs/quant-ph?9704012.
[83] Meter III R D V. Architecture of a quantum multicomputer optimized for shor's factoring algorithm [OL]. 2006, arXiv:quant-ph/0607065, https://arxiv.org/abs/quant-ph/0607065.
[84] Van Meter R, Nemoto K, Munro W J, et al. Distributed arithmetic on a quantum multicomputer [J]. ACM SIGARCH Computer Architecture News, 2006, 34(2): 354-365.
[85] Sheng Y B, Zhou L. Distributed secure quantum machine learning [J]. Science Bulletin, 2017, 62(14): 1025-1029.
[86] DiAdamo S, Ghibaudi M, Cruise J. Distributed quantum computing and network control for accelerated vqe [J]. IEEE Transactions on Quantum Engineering, 2021, 2: 1-21.
[87] Xiao L, Qiu D, Luo L, et al. Distributed Shor's algorithm [J]. Quantum Information and Computation, 2023, 23(1&2): 0027-0044.
[88] Tani S, Kobayashi H, Matsumoto K. Exact Quantum Algorithms for the Leader Election Problem [OL]. 2007, arXiv: 0712.4213, https://arxiv.org/abs/0712.4213.
[89] Elkin M, Klauck H, Nanongkai D, et al. Can quantum communication speed up distributed computation? [C]. Proceedings of the 2014 ACM symposium on Principles of distributed computing. 2014: 166-175.
[90] Izumi T, Le Gall F. Quantum distributed algorithm for the All-Pairs Shortest Path problem in the CONGEST-CLIQUE model [C]. Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing. 2019: 84-93.
[91] van Apeldoorn J, de Vos T. A framework for distributed quantum queries in the CONGEST model [C]. Proceedings of the 2022 ACM Symposium on Principles of Distributed Computing. 2022: 109-119.
[92] Wu X, Yao P. Quantum Complexity of Weighted Diameter and Radius in CONGEST Networks [C]. Proceedings of the 2022 ACM Symposium on Principles of Distributed Computing. 2022: 120-130.
[93] Zomorodi-Moghadam M, Houshmand M, Houshmand M. Optimizing teleportation cost in distributed quantum circuits [J]. International Journal of Theoretical Physics, 2018, 57: 848-861.
[94] Andres-Martinez P, Heunen C. Automated distribution of quantum circuits via hypergraph partitioning [J]. Physical Review A, 2019, 100(3): 032308.
[95] Dadkhah D, Zomorodi M, Hosseini S E. A new approach for optimization of distributed quantum circuits [J]. International Journal of Theoretical Physics, 2021, 60: 3271-3285.
[96] Ferrari D, Cacciapuoti A S, Amoretti M, et al. Compiler design for distributed quantum computing [J]. IEEE Transactions on Quantum Engineering, 2021, 2: 1-20.
[97] G Sundaram R, Gupta H, Ramakrishnan C R. Efficient distribution of quantum circuits [C]. 35th International Symposium on Distributed Computing (DISC 2021). Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 2021.
[98] Dadkhah D, Zomorodi M, Hosseini S E, et al. Reordering and partitioning of distributed quantum circuits [J]. IEEE Access, 2022, 10: 70329-70341.
[99] Sundaram R G, Gupta H, Ramakrishnan C R. Distribution of quantum circuits over general quantum networks [C]. 2022 IEEE International Conference on Quantum Computing and Engineering (QCE). IEEE, 2022: 415-425.
[100] Ferrari D, Carretta S, Amoretti M. A Modular Quantum Compilation Framework for Distributed Quantum Computing [OL]. 2023, arXiv:2305.02969, https://arxiv.org/abs/2305.02969.
[101] Peng T, Harrow A W, Ozols M, et al. Simulating large quantum circuits on a small quantum computer [J]. Physical Review Letters, 2020, 125(15): 150504.
[102] Mitarai K, Fujii K. Constructing a virtual two-qubit gate by sampling single-qubit operations [J]. New Journal of Physics, 2021, 23(2): 023021.
[103] Perlin M, Tomesh T, Pearlman B, et al. Parallelizing Simulations of Large Quantum Circuits [J]. 2019, https://sc19.supercomputing.
[104] Ayral T, Le Régent F M, Saleem Z, et al. Quantum divide and compute: Hardware demonstrations and noisy simulations [C]. 2020 IEEE Computer Society Annual Symposium on VLSI (ISVLSI). IEEE, 2020: 138-140.
[105] Ayral T, Régent F M L, Saleem Z, et al. Quantum divide and compute: exploring the effect of different noise sources [J]. SN Computer Science, 2021, 2(3): 132.
[106] Eddins A, Motta M, Gujarati T P, et al. Doubling the size of quantum simulators by entanglement forging [J]. PRX Quantum, 2022, 3(1): 010309.
[107] Huembeli P, Carleo G, Mezzacapo A. Entanglement Forging with generative neural network models [OL]. 2022, arXiv:2205.00933, https://arxiv.org/abs/2205.00933.
[108] Piveteau C, Sutter D. Circuit knitting with classical communication [C]. Quantum Information Processing Conference. 2023.
[109] Lowe A, Medvidovi? M, Hayes A, et al. Fast quantum circuit cutting with randomized measurements [J]. Quantum, 2023, 7: 934.
[110] Van Den Berg E. A simple method for sampling random Clifford operators [C]. 2021 IEEE International Conference on Quantum Computing and Engineering (QCE). IEEE, 2021: 54-59.
[111] Brenner L, Piveteau C, Sutter D. Optimal wire cutting with classical communication [OL]. 2023, arXiv:2302.03366, https://arxiv.org/abs/2302.03366.
[112] Chen D T, Hansen E H, Li X, et al. Efficient Quantum Circuit Cutting by Neglecting Basis Elements [OL]. 2023, arXiv:2304.04093, https://arxiv.org/abs/2304.04093.
[113] Harada H, Wada K, Yamamoto N. Optimal parallel wire cutting without ancilla qubits [J]. 2023, arXiv:2303.07340, https://arxiv.org/abs/2303.07340.
[114] Pednault E. An alternative approach to optimal wire cutting without ancilla qubits [J]. 2023, arXiv:2303.08287, https://arxiv.org/abs/2303.08287.
[115] Perlin M A, Saleem Z H, Suchara M, et al. Quantum circuit cutting with maximum-likelihood tomography [J]. npj Quantum Information, 2021, 7(1): 64.
[116] Tang W, Tomesh T, Suchara M, et al. Cutqc: using small quantum computers for large quantum circuit evaluations [C]. Proceedings of the 26th ACM International conference on architectural support for programming languages and operating systems. 2021: 473-486.
[117] Tang W, Martonosi M. ScaleQC: A Scalable Framework for Hybrid Computation on Quantum and Classical Processors [OL]. 2022, arXiv:2207.00933, https://arxiv.org/abs/2207.00933.
[118] Chen D, Baheri B, Chaudhary V, et al. Approximate quantum circuit reconstruction [C]. 2022 IEEE International Conference on Quantum Computing and Engineering (QCE). IEEE, 2022: 509-515.
[119] Kandala A, Mezzacapo A, Temme K, et al. Hardware-efficient variational quantum eigensolver for small molecules and quantum magnets [J]. Nature, 2017, 549(7671): 242-246.
[120] Ying C, Cheng B, Zhao Y, et al. Experimental simulation of larger quantum circuits with fewer superconducting qubits [J]. Physical Review Letters, 2023, 130(11): 110601.
[121] Guala D, Zhang S, Cruz E, et al. Practical overview of image classification with tensor-network quantum circuits [J]. Scientific Reports, 2023, 13(1): 4427.
[122] Liu J, Gonzales A, Saleem Z H. Classical simulators as quantum error mitigators via circuit cutting [OL]. 2022, arXiv:2212.07335, https://arxiv.org/abs/2212.07335.
[123] Chen D T, Saleem Z H, Perlin M A. Quantum Divide and Conquer for Classical Shadows [OL]. 2022, arXiv:2212.00761, https://arxiv.org/abs/2212.00761.
[124] Smith K N, Perlin M A, Gokhale P, et al. Clifford-based Circuit Cutting for Quantum Simulation [C]. Proceedings of the 50th Annual International Symposium on Computer Architecture. 2023: 1-13.
[125] Chatterjee T, Das A, Mohtashim S I, et al. Qurzon: A Prototype for a Divide and Conquer-Based Quantum Compiler for Distributed Quantum Systems [J]. SN Computer Science, 2022, 3(4): 323.
[126] Basu S, Saha A, Chakrabarti A, et al. i-QER: An intelligent approach towards quantum error reduction [J]. ACM Transactions on Quantum Computing, 2022, 3(4): 1-18.