A Two-Level Method Based on Dynamic Programming for Partitioning and Optimization of the Communication Cost in Distributed Quantum Circuits
Subject Areas : electrical and computer engineeringzohreh davarzani 1 , maryam zomorodi-moghadam 2 * , M. Houshmand 3
1 - student
2 -
3 - دانشگاه آزاد اسلامی، واحد مشهد
Keywords: Quantum teleportation, dynamic programming, partitioning, load balancing, distributed quantum computing,
Abstract :
Nowadays, quantum computing has played a significant role in increasing the speed of algorithms. Due to the limitations in the manufacturing technologies of quantum computers, the design of a large-scale quantum computer faces many challenges. One solution to overcome these challenges is the design of distributed quantum systems. In these systems, quantum computers are connected to each other through the teleportation protocol to transfer quantum information. Since quantum teleportation requires quantum resources, it is necessary to reduce the number of that. The purpose of this paper is to present a distributed quantum system considering the two goals of balanced distribution of qubits and minimizing the number of teleportation protocols in two levels. In the first level, by presenting a dynamic programming algorithm, an attempt has been made to distribute qubits in a balanced manner and reduce the number of connections between subsystems. According to the output partitioning obtained from the first level, in the second level and in the stage of implementation of global gates, when one of the qubits of this gate is teleported from the home to the desired destination, this qubit may be able to be used by a number of global gates, observing the precedence restrictions and as a result it reduces the number of teleportations. The obtained results show the better performance of the proposed algorithm.
[1] A. S. Cacciapuoti, et al., "Quantum internet: networking challenges in distributed quantum computing," IEEE Network, vol. 34, no. 1, pp. 137-143, Jan./Feb. 2019.
[2] R. Van Meter, T. D. Ladd, A. G. Fowler, and Y. Yamamoto, "Distributed quantum computation architecture using semiconductor nanophotonics," International Journal of Quantum Information, vol. 8, no. 2, pp. 295-323, 2010.
[3] D. Cuomo, M. Caleffi, and A. S. Cacciapuoti, "Towards a distributed quantum computing ecosystem," IET Quantum Communication, vol. 1, no. 1, pp. 3-8, Jul. 2020.
[4] M. Loncar, et al., Development of Quantum Interconnects for Next-Generation Information Technologies, Nov. 2019.
[5] N. H. Nickerson, Y. Li, and S. C. Benjamin, "Topological quantum computing with a very noisy network and local error rates approaching one percent," Nature Communications, vol. 4, Article ID: 1756, 5 pp., 2013.
[6] M. Whitney, N. Isailovic, Y. Patel, and J. Kubiatowicz, "Automated generation of layout and control for quantum circuits," in Proc. of the 4th Int. Conf. on Computing Frontiers, pp. 83-94, Apr. 2007.
[7] D. Bouwmeester, et al., "Experimental quantum teleportation," Nature, vol. 390, pp. 575-579, Dec. 1997.
[8] M. A. Nielsen, E. Knill, and R. J. N. Laflamme, "Complete quantum teleportation using nuclear magnetic resonance," Nature, vol. 396, pp. 52-55, Nov. 1998.
[9] M. Riebe, et al., "Deterministic quantum teleportation with atoms," Nature, vol. 429, no. 6993, pp. 737-739, Jun. 2004.
[10] L. K. Grover, Quantum Telecomputation, Apr. 1997.
[11] R. Cleve and H. Buhrman, "Substituting quantum entanglement for communication," Physical Review A, vol. 56, no. 2, pp. 1201-1204, Apr. 1997.
[12] J. I. Cirac, A. Ekert, S. F. Huelga, and C. Macchiavello, "Distributed quantum computation over noisy," Physical Review A, vol. 59, no. 6, Article ID: 4249, Jun. 1999.
[13] J. Yepez, "Type-II quantum computers," Int. Journal of Modern Physics C, vol. 12, no. 09, pp. 1273-1284, 2001.
[14] S. S. Bharadwaj and K. R. Sreenivasan, "Quantum computation of fluid dynamics," Bulletin of the American Physical Society, Feb. 2020.
[15] J. Yepez, "Lattice-gas quantum computation," Int. Journal of Modern Physics C, vol. 9, no. 8, pp. 1596-1587, 1998.
[16] R. Beals, et al., "Efficient distributed quantum computing," Proceedings of the Royal Society A, vol. 469, no. 2153, 20 pp., 8 May 2013.
[17] 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, vol. 3, no. 4, Article ID: 2, 23 pp., Jan. 2008.
[18] D. Gottesman and I. L. Chuang, "Demonstrating the viability of universal quantum computation using teleportation and single-qubit operations," Nature, vol. 402, no. 6760, pp. 390-393, Aug. 1999.
[19] M. Caleffi, A. S. Cacciapuoti, and G. Bianchi, "Quantum internet: from communication to distributed computing!," in Proc. of the 5th ACM Int. Conf. on Nanoscale Computing and Communication, 4 pp., Reykjavik, Iceland, 5-7 Sept. 2018.
[20] C. Heunen and P. A. J. P. R. A. Martinez, "Automated distribution of quantum circuits," Physical Review A, vol.100, Article ID: 032308, Sept. 2019.
[21] Y. Akhremtsev, T. Heuer, P. Sanders, and S. Schlag, "Engineering a direct k-way hypergraph partitioning algorithm," in Proc. of the 19th Workshop on Algorithm Engineering and Experiments, ALENEX'17, pp. 28-42, Jan. 2017.
[22] M. Zomorodi-Moghadam, M. Houshmand, and M. Houshmand, "Optimizing teleportation cost in distributed quantum circuits," International Journal of Theorethical Physics, vol. 57, no. 3, pp. 848-861, May 2018.
[23] M. Houshmand, Z. Mohammadi, M. Zomorodi-Moghadam, and M. Houshmand, "An evolutionary approach to optimizing teleportation cost in distributed quantum computation," International Journal of Theorethical Physics, vol. 59, no. 4, pp. 1315-1329, Feb. 2020.
[24] Z. Davarzani, M. Zomorodi-Moghadam, M. Houshmand, and M. Nouri-Baygi, "A dynamic programming approach for distributing quantum circuits by bipartite graphs," Quantum Information Processing, vol. 19, no. 10, pp. 1-18, Sept. 2020.
[25] O. Daei, K. Navi, and M. Zomorodi-Moghadam, "Optimized quantum circuit partitioning," International Journal of Theorethical Physics, vol. 59, no. 12, pp. 3804-3820, Nov. 2020.
[26] E. Nikahd, N. Mohammadzadeh, M. Sedighi, and M. Saheb Zamani, "Automated window-based partitioning of quantum circuits," Physica Scripta, vol. 96, no. 3, Article ID: 035102, Mar. 2021.
[27] K. Andreev and H. Räcke, "Balanced graph partitioning," in Proc. of the 16th Annual ACM Symp. on Parallelism in Algorithms and Architectures, pp. 120-124, Barcelona, Spain, 27-30 Jun. 2004.
[28] A. U. Khalid, Z. Zilic, and K. Radecka, "FPGA emulation of quantum circuits," in Proc. IEEE In. Conf. on Computer Design: VLSI in Computers and Processors, pp. 310-315, San Jose, CA, USA, 11-13 Oct. 2004.
[29] J. Donald and N. K. Jha, "Reversible logic synthesis with Fredkin and Peres gates," ACM Journal on Emerging Technologies in Computing Systems, vol. 4, no. 1, Article ID:2, 19 pp., Apr. 2008.
[30] R. Wille, D. Große, L. Teuber, G. W. Dueck, and R. Drechsler, "RevLib: an online resource for reversible functions and reversible circuits," in Proc. 38th Int. Symp. on Multiple Valued Logic, pp. 220-225, Dallas, TX, USA, 22-24 May 2008.
[31] A. W. Cross, et al., Open Quantum Assembly Language, Mar. 2021, https://assets.amazon.science/2f/11/b60fba45406fb41d2b2af9aa43a8/open-quantum-assembly-language.pdf