1Department of Physics and Center for Advanced Quantum Computing, Tamkang University, 151 Yingzhuan Rd., New Taipei City 25137, Taiwan, ROC
2Physics Division, National Center for Theoretical Sciences, Taipei 10617, Taiwan, ROC
3The University of Tokyo, Hongo 7-3-1, Bunkyo-ku, Tokyo 113-0033, Japan
4Principles of Informatics Research Division, National Institute of Informatics, 2-1-2 Hitotsubashi, Chiyoda-ku, Tokyo 101-8430, Japan
5Department of Informatics, School of Multidisciplinary Sciences, SOKENDAI (The Graduate University for Advanced Studies), 2-1-2 Hitotsubashi, Chiyoda-ku, Tokyo 101-8430, Japan
6Quantinuum, Terrington House, 13-15 Hills Road, Cambridge CB2 1NL, UK
Find this paper interesting or want to discuss? Scite or leave a comment on SciRate.
Abstract
In noisy intermediate-scale quantum computing, the limited scalability of a single quantum processing unit (QPU) can be extended through distributed quantum computing (DQC), in which one can implement global operations over two QPUs by entanglement-assisted local operations and classical communication. To facilitate this type of DQC in experiments, we need an entanglement-efficient protocol. To this end, we extend the protocol in [Eisert et. al., PRA, 62:052317(2000)] implementing each nonlocal controlled-unitary gate locally with one maximally entangled pair to a packing protocol, which can pack multiple nonlocal controlled-unitary gates locally using one maximally entangled pair. In particular, two types of packing processes are introduced as the building blocks, namely the distributing processes and embedding processes. Each distributing process distributes corresponding gates locally with one entangled pair. The efficiency of entanglement is then enhanced by embedding processes, which merge two non-sequential distributing processes and hence save the entanglement cost. We show that the structure of distributability and embeddability of a quantum circuit can be fully represented by the corresponding packing graphs and conflict graphs. Based on these graphs, we derive heuristic algorithms for finding an entanglement-efficient packing of distributing processes for a given quantum circuit to be implemented by two parties. These algorithms can determine the required number of local auxiliary qubits in the DQC. We apply these algorithms for bipartite DQC of unitary coupled-cluster circuits and find a significant reduction of entanglement cost through embeddings. This method can determine a constructive upper bound on the entanglement cost for the DQC of quantum circuits.
Featured image: Packing and conflict edges of a circuit. The red lines induce the packing edges, while the blue and green lines induce intrinsic and extrinsic conflict edges, respectively. The packing graph and conflict graph induced by these edges fully describe the distributability, embeddability, and incompatibility of a quantum circuit, upon which our embedding-enhanced-distributing protocol is built.
Popular summary
In our paper, an entanglement-efficient architecture for bipartite distributed quantum computing is established based on a decomposition of a quantum circuit into a set of distributable blocks. In each block, one maximally-entangled state is consumed to distribute nonlocal gates with local operations and classical communication. In previous protocols, a distributing process ends with single qubit gates. To improve entanglement efficiency, we introduce embedding processes to merge two non-sequential distributing processes into one, saving on the amount of entanglement needed. Such an embedding-enhanced-distributing structure of a quantum circuit can be fully described by a packing graph made up of vertices representing gate nodes that could be merged together.
The vertices of a packing graph are the candidates for distributing processes. However, there may be conflicts between two embeddings that prevent us from implementing them simultaneously. We have to remove some embeddings to solve the conflicts, which leads to a split of vertices in a packing graph. Such a conflict can be fully described by a conflict graph.
The packing graph and conflict graph of a circuit fully describe its distributability, embeddability, and incompatibility. To determine the best way to distribute a circuit, we develop a packing algorithm that takes into account both the minimum vertex covering of the packing graph and its corresponding conflict graph to find a distributing strategy that is both entanglement-efficient and conflict-free.
Overall, our protocol can be summarized as an “embedding-enhanced-distributing” protocol, which is based on two types of entanglement-assisted quantum operation, namely distributing processes and embedding processes. Compared to previous protocols, it significantly reduces the amount of entanglement required for distributed quantum computing, making it more practical for real-world applications. It can be employed to determine a tighter constructive upper bound on the entanglement cost for a unitary being decomposed into local operations and classical communication. The protocol can be extended to multipartite systems and adapted to network topology for distributed quantum computing over the quantum internet. The “embedding-enhanced-distributing” protocol can therefore facilitate large-scale quantum computing in a quantum network of QPUs.
► BibTeX data
► References
[1] J. Preskill. Quantum computing in the NISQ era and beyond. Quantum, 2018 2: 79. 10.22331/q-2018-08-06-79.
https://doi.org/10.22331/q-2018-08-06-79
[2] N. Moll, P. Barkoutsos, L. S. Bishop, J. M. Chow, A. Cross, D. J. Egger, S. Filipp, A. Fuhrer, J. M. Gambetta, M. Ganzhorn, A. Kandala, A. Mezzacapo, P. Müller, W. Riess, G. Salis, J. Smolin, I. Tavernelli, and K. Temme. Quantum optimization using variational algorithms on near-term quantum devices. Quantum Science and Technology, 2018 3 (3): 030503. 10.1088/2058-9565/aab822.
https://doi.org/10.1088/2058-9565/aab822
[3] A. W. Cross, L. S. Bishop, S. Sheldon, P. D. Nation, and J. M. Gambetta. Validating quantum computers using randomized model circuits. Physical Review A, 2019 100: 032328. 10.1103/PhysRevA.100.032328.
https://doi.org/10.1103/PhysRevA.100.032328
[4] S. Bose, P. L. Knight, M. B. Plenio, and V. Vedral. Proposal for teleportation of an atomic state via cavity decay. Physical Review Letters, 1999 83: 5158–5161. 10.1103/PhysRevLett.83.5158.
https://doi.org/10.1103/PhysRevLett.83.5158
[5] C. Cabrillo, J. I. Cirac, P. García-Fernández, and P. Zoller. Creation of entangled states of distant atoms by interference. Physical Review A, 1999 59: 1025–1033. 10.1103/PhysRevA.59.1025.
https://doi.org/10.1103/PhysRevA.59.1025
[6] D. E. Browne, M. B. Plenio, and S. F. Huelga. Robust creation of entanglement between ions in spatially separate cavities. Physical Review Letters, 2003 91: 067901. 10.1103/PhysRevLett.91.067901.
https://doi.org/10.1103/PhysRevLett.91.067901
[7] L.-M. Duan, B. Blinov, D. Moehring, and C. Monroe. Scalable trapped ion quantum computation with a probabilistic ion-photon mapping. Quantum Information and Computation, 2004 4: 165–173. 10.48550/arXiv.quant-ph/0401020.
https://doi.org/10.48550/arXiv.quant-ph/0401020
arXiv:quant-ph/0401020
[8] Y. L. Lim, A. Beige, and L. C. Kwek. Repeat-until-success linear optics distributed quantum computing. Physical Review Letters, 2005 95: 030505. 10.1103/PhysRevLett.95.030505.
https://doi.org/10.1103/PhysRevLett.95.030505
[9] L.-M. Duan, M. J. Madsen, D. L. Moehring, P. Maunz, R. N. Kohn, and C. Monroe. Probabilistic quantum gates between remote atoms through interference of optical frequency qubits. Physical Review A, 2006 73: 062324. 10.1103/PhysRevA.73.062324.
https://doi.org/10.1103/PhysRevA.73.062324
[10] Z.-q. Yin, W. L. Yang, L. Sun, and L. M. Duan. Quantum network of superconducting qubits through an optomechanical interface. Physical Review A, 2015 91: 012333. 10.1103/PhysRevA.91.012333.
https://doi.org/10.1103/PhysRevA.91.012333
[11] K. Koshino, K. Inomata, Z. R. Lin, Y. Tokunaga, T. Yamamoto, and Y. Nakamura. Theory of deterministic entanglement generation between remote superconducting atoms. Physical Review Applied, 2017 7: 064006. 10.1103/PhysRevApplied.7.064006.
https://doi.org/10.1103/PhysRevApplied.7.064006
[12] D. L. Moehring, P. Maunz, S. Olmschenk, K. C. Younge, D. N. Matsukevich, L.-M. Duan, and C. Monroe. Entanglement of single-atom quantum bits at a distance. Nature, 2007 449 (7158): 68–71. 10.1038/nature06118.
https://doi.org/10.1038/nature06118
[13] L. Slodička, G. Hétet, N. Röck, P. Schindler, M. Hennrich, and R. Blatt. Atom-atom entanglement by single-photon detection. Physical Review Letters, 2013 110 (8): 083603. 10.1103/physrevlett.110.083603.
https://doi.org/10.1103/physrevlett.110.083603
[14] S. Ritter, C. Nolleke, C. Hahn, A. Reiserer, M. Neuzner, Andreas andUphoff, M. Mucke, E. Figueroa, J. Bochmann, , and G. Rempe. An elementary quantum network of single atoms in optical cavities. Nature, 2012 484: 195–200. 10.1038/nature11023.
https://doi.org/10.1038/nature11023
[15] J. Hofmann, M. Krug, N. Ortegel, L. Gérard, M. Weber, W. Rosenfeld, and H. Weinfurter. Heralded entanglement between widely separated atoms. Science, 2012 337 (6090): 72–75. 10.1126/science.1221856.
https://doi.org/10.1126/science.1221856
[16] H. Bernien, B. Hensen, W. Pfaff, G. Koolstra, M. S. Blok, L. Robledo, T. H. Taminiau, M. Markham, D. J. Twitchen, L. Childress, and R. Hanson. Heralded entanglement between solid-state qubits separated by three metres. Nature, 2013 497 (7447): 86–90. 10.1038/nature12016.
https://doi.org/10.1038/nature12016
[17] A. Delteil, Z. Sun, W. bo Gao, E. Togan, S. Faelt, and A. Imamoğlu. Generation of heralded entanglement between distant hole spins. Nature Physics, 2015 12 (3): 218–223. 10.1038/nphys3605.
https://doi.org/10.1038/nphys3605
[18] R. Stockill, M. J. Stanley, L. Huthmacher, E. Clarke, M. Hugues, A. J. Miller, C. Matthiesen, C. Le Gall, and M. Atatüre. Phase-tuned entangled state generation between distant spin qubits. Physical Review Letters, 2017 119: 010503. 10.1103/PhysRevLett.119.010503.
https://doi.org/10.1103/PhysRevLett.119.010503
[19] A. Narla, S. Shankar, M. Hatridge, Z. Leghtas, K. M. Sliwa, E. Zalys-Geller, S. O. Mundhada, W. Pfaff, L. Frunzio, R. J. Schoelkopf, and M. H. Devoret. Robust concurrent remote entanglement between two superconducting qubits. Physical Review X, 2016 6: 031036. 10.1103/PhysRevX.6.031036.
https://doi.org/10.1103/PhysRevX.6.031036
[20] L. J. Stephenson, D. P. Nadlinger, B. C. Nichol, S. An, P. Drmota, T. G. Ballance, K. Thirumalai, J. F. Goodwin, D. M. Lucas, and C. J. Ballance. High-rate, high-fidelity entanglement of qubits across an elementary quantum network. Physical Review Letters, 2020 124: 110501. 10.1103/PhysRevLett.124.110501.
https://doi.org/10.1103/PhysRevLett.124.110501
[21] D. Hucul, I. V. Inlek, G. Vittorini, C. Crocker, S. Debnath, S. M. Clark, and C. Monroe. Modular entanglement of atomic qubits using photons and phonons. Nature Physics, 2014 11 (1): 37–42. 10.1038/nphys3150.
https://doi.org/10.1038/nphys3150
[22] H. J. Kimble. The quantum internet. Nature, 453: 1023–1030, 2008. 10.1038/nature07127.
https://doi.org/10.1038/nature07127
[23] A. Soeda, Y. Kinjo, P. S. Turner, and M. Murao. Quantum computation over the butterfly network. Physical Review A, 2011 84: 012333. 10.1103/PhysRevA.84.012333.
https://doi.org/10.1103/PhysRevA.84.012333
[24] D. Gottesman and I. L. Chuang. Demonstrating the viability of universal quantum computation using teleportation and single-qubit operations. Nature, 402: 390–393, 1999. 10.1038/46503.
https://doi.org/10.1038/46503
[25] X. Zhou, D. W. Leung, and I. L. Chuang. Methodology for quantum logic gate construction. Physical Review A, 2000 62: 052316. 10.1103/PhysRevA.62.052316.
https://doi.org/10.1103/PhysRevA.62.052316
[26] J. Eisert, K. Jacobs, P. Papadopoulos, and M. B. Plenio. Optimal local implementation of nonlocal quantum gates. Physical Review A, 2000 62: 052317. 10.1103/PhysRevA.62.052317.
https://doi.org/10.1103/PhysRevA.62.052317
[27] S. F. Huelga, J. A. Vaccaro, A. Chefles, and M. B. Plenio. Quantum remote control: Teleportation of unitary operations. Physical Review A, 2001 63: 042303. 10.1103/PhysRevA.63.042303.
https://doi.org/10.1103/PhysRevA.63.042303
[28] S. F. Huelga, M. B. Plenio, and J. A. Vaccaro. Remote control of restricted sets of operations: Teleportation of angles. Physical Review A, 2002 65: 042316. 10.1103/PhysRevA.65.042316.
https://doi.org/10.1103/PhysRevA.65.042316
[29] L. Jiang, J. M. Taylor, A. S. Sørensen, and M. D. Lukin. Distributed quantum computation based on small quantum registers. Physical Review A, 2007 76: 062323. 10.1103/PhysRevA.76.062323.
https://doi.org/10.1103/PhysRevA.76.062323
[30] R. V. Meter, W. Munro, K. Nemoto, and K. M. Itoh. Arithmetic on a distributed-memory quantum multicomputer. ACM Journal on Emerging Technologies in Computing Systems (JETC), 3 (4): 1–23, 2008. 10.1145/1324177.1324179.
https://doi.org/10.1145/1324177.1324179
[31] M. Caleffi, M. Amoretti, D. Ferrari, D. Cuomo, J. Illiano, A. Manzalini, and A. S. Cacciapuoti. Distributed quantum computing: a survey, 2022. 10.48550/arXiv.2212.10609.
https://doi.org/10.48550/arXiv.2212.10609
[32] K. S. Chou, J. Z. Blumoff, C. S. Wang, P. C. Reinhold, C. J. Axline, Y. Y. Gao, L. Frunzio, M. H. Devoret, L. Jiang, and R. J. Schoelkopf. Deterministic teleportation of a quantum gate between two logical qubits. Nature, 2018 561 (7723): 368–373. 10.1038/s41586-018-0470-y.
https://doi.org/10.1038/s41586-018-0470-y
[33] Y. Wan, D. Kienzler, S. D. Erickson, K. H. Mayer, T. R. Tan, J. J. Wu, H. M. Vasconcelos, S. Glancy, E. Knill, D. J. Wineland, A. C. Wilson, and D. Leibfried. Quantum gate teleportation between separated qubits in a trapped-ion processor. Science, 364 (6443): 875–878, 2019. 10.1126/science.aaw9415.
https://doi.org/10.1126/science.aaw9415
[34] P. Andrés-Martínez and C. Heunen. Automated distribution of quantum circuits via hypergraph partitioning. Physical Review A, 2019 100: 032308. 10.1103/PhysRevA.100.032308.
https://doi.org/10.1103/PhysRevA.100.032308
[35] R. G. Sundaram, H. Gupta, and C. R. Ramakrishnan. Efficient Distribution of Quantum Circuits. In S. Gilbert, editor, 35th International Symposium on Distributed Computing (DISC 2021), volume 209 of Leibniz International Proceedings in Informatics (LIPIcs), pages 41:1–41:20, Dagstuhl, Germany, 2021. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. ISBN 978-3-95977-210-5. 10.4230/LIPIcs.DISC.2021.41.
https://doi.org/10.4230/LIPIcs.DISC.2021.41
[36] D. Cuomo, M. Caleffi, K. Krsulich, F. Tramonto, G. Agliardi, E. Prati, and A. S. Cacciapuoti. Optimized compiler for distributed quantum computing. ACM Transactions on Quantum Computing, 2023 4 (2). ISSN 2643-6809. 10.1145/3579367.
https://doi.org/10.1145/3579367
[37] R. G. Sundaram, H. Gupta, and C. R. Ramakrishnan. Distribution of quantum circuits over general quantum networks. In 2022 IEEE International Conference on Quantum Computing and Engineering (QCE), pages 415–425, 2022 Los Alamitos, CA, USA. IEEE Computer Society. 10.1109/QCE53715.2022.00063.
https://doi.org/10.1109/QCE53715.2022.00063
[38] D. Stahlke and R. B. Griffiths. Entanglement requirements for implementing bipartite unitary operations. Physical Review A, 2011 84: 032316. 10.1103/PhysRevA.84.032316.
https://doi.org/10.1103/PhysRevA.84.032316
[39] P. Andres-Martinez, T. Forrer, D. Mills, J.-Y. Wu, L. Henaut, K. Yamamoto, M. Murao, and R. Duncan. Distributing circuits over heterogeneous, modular quantum computing network architectures. 10.48550/arXiv.2305.14148.
https://doi.org/10.48550/arXiv.2305.14148
[40] J. M. Baker, C. Duckering, A. Hoover, and F. T. Chong. Time-sliced quantum circuit partitioning for modular architectures. In Proceedings of the 17th ACM International Conference on Computing Frontiers, CF ’20, page 98–107, New York, NY, USA, 2020. Association for Computing Machinery. ISBN 9781450379564. 10.1145/3387902.3392617.
https://doi.org/10.1145/3387902.3392617
[41] S. DiAdamo, M. Ghibaudi, and J. Cruise. Distributed quantum computing and network control for accelerated vqe. IEEE Transactions on Quantum Engineering, 2: 1–21, 2021. 10.1109/TQE.2021.3057908.
https://doi.org/10.1109/TQE.2021.3057908
[42] D. Ferrari, A. S. Cacciapuoti, M. Amoretti, and M. Caleffi. Compiler design for distributed quantum computing. IEEE Transactions on Quantum Engineering, 2: 1–20, 2021. 10.1109/TQE.2021.3053921.
https://doi.org/10.1109/TQE.2021.3053921
[43] A. Ovide, S. Rodrigo, M. Bandic, H. Van Someren, S. Feld, S. Abadal, E. Alarcon, and C. G. Almudever. Mapping quantum algorithms to multi-core quantum computing architectures. In 2023 IEEE International Symposium on Circuits and Systems (ISCAS), pages 1–5, 2023. 10.1109/ISCAS46773.2023.10181589.
https://doi.org/10.1109/ISCAS46773.2023.10181589
[44] D. Ferrari, S. Carretta, and M. Amoretti. A modular quantum compilation framework for distributed quantum computing. IEEE Transactions on Quantum Engineering, 2023 4 (01): 1–13. ISSN 2689-1808. 10.1109/TQE.2023.3303935.
https://doi.org/10.1109/TQE.2023.3303935
[45] A. G. Taube and R. J. Bartlett. New perspectives on unitary coupled-cluster theory. International Journal of Quantum Chemistry, 106 (15): 3393–3401, 2006. 10.1002/qua.21198.
https://doi.org/10.1002/qua.21198
[46] A. Peruzzo, J. McClean, P. Shadbolt, M.-H. Yung, X.-Q. Zhou, P. J. Love, A. Aspuru-Guzik, and J. L. O’Brien. A variational eigenvalue solver on a photonic quantum processor. Nature Communications, 2014 5 (1). 10.1038/ncomms5213.
https://doi.org/10.1038/ncomms5213
[47] D. Jonathan and M. B. Plenio. Entanglement-assisted local manipulation of pure quantum states. Physical Review Letters, 1999 83: 3566–3569. 10.1103/PhysRevLett.83.3566.
https://doi.org/10.1103/PhysRevLett.83.3566
[48] A. Yimsiriwattana and S. J. Lomonaco. Generalized GHZ states and distributed quantum computing, 2004. 10.48550/ARXIV.QUANT-PH/0402148.
https://doi.org/10.48550/ARXIV.QUANT-PH/0402148
[49] T. Uno. Algorithms for enumerating all perfect, maximum and maximal matchings in bipartite graphs. In Algorithms and Computation, pages 92–101. Springer Berlin Heidelberg. 10.1007/3-540-63890-3_11.
https://doi.org/10.1007/3-540-63890-3_11
[50] M. Garey and D. Johnson. Computers and Intractability: A Guide to the Theory of NP-completeness. Mathematical Sciences Series. Freeman, 1979. ISBN 9780716710448.
[51] A. Björklund, T. Husfeldt, and M. Koivisto. Set partitioning via inclusion-exclusion. SIAM Journal on Computing, 39 (2): 546–563, 2009. 10.1137/070683933.
https://doi.org/10.1137/070683933
[52] R. Diestel. Graph theory, volume 173 of Graduate Texts in Mathematics. Springer-Verlag, Heidelberg, 2005 2005 edition. 10.1007/978-3-662-53622-3.
https://doi.org/10.1007/978-3-662-53622-3
[53] J. W. Moon and L. Moser. On cliques in graphs. Israel journal of Mathematics, 3: 23–28, 1965. 10.1007/BF02760024.
https://doi.org/10.1007/BF02760024
[54] J. E. Hopcroft and R. M. Karp. An $n^{5/2}$ algorithm for maximum matchings in bipartite graphs. 2 (4): 225–231. 10.1137/0202019.
https://doi.org/10.1137/0202019
Cited by
[1] Pablo Andres-Martinez, Tim Forrer, Daniel Mills, Jun-Yi Wu, Luciana Henaut, Kentaro Yamamoto, Mio Murao, and Ross Duncan, “Distributing circuits over heterogeneous, modular quantum computing network architectures”, arXiv:2305.14148, (2023).
The above citations are from SAO/NASA ADS (last updated successfully 2023-12-06 02:16:54). 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 2023-12-06 02:16:52).
This Paper is published in Quantum under the Creative Commons Attribution 4.0 International (CC BY 4.0) license. Copyright remains with the original copyright holders such as the authors or their institutions.
- SEO Powered Content & PR Distribution. Get Amplified Today.
- PlatoData.Network Vertical Generative Ai. Empower Yourself. Access Here.
- PlatoAiStream. Web3 Intelligence. Knowledge Amplified. Access Here.
- PlatoESG. Carbon, CleanTech, Energy, Environment, Solar, Waste Management. Access Here.
- PlatoHealth. Biotech and Clinical Trials Intelligence. Access Here.
- Source: https://quantum-journal.org/papers/q-2023-12-05-1196/
