یک روش دوسطحی مبتنی بر برنامه‌سازی پویا جهت افراز و بهینه‌سازی هزینه ارتباطات در مدارات کوانتومی توزیعی
محورهای موضوعی : مهندسی برق و کامپیوترزهره داورزنی 1 , مریم زمردی مقدم 2 * , محبوبه هوشمند 3
1 - گروه مهندسی کامپیوتر، دانشگاه پیام نور
2 - گروه علوم کامپیوتر و ارتباطات، دانشگاه صنعتی کراکف لهستان
3 - گروه مهندسی کامپیوتر، دانشگاه آزاد اسلامی واحد مشهد
کلید واژه: دورنوردی کوانتومی, برنامه‌سازی پویا, افراز, توازن بار, محاسبات کوانتومی توزیع‌شده,
چکیده مقاله :
امروزه محاسبات کوانتومی نقشی بسزا در افزایش سرعت الگوریتم‌ها دارند. به‌دلیل محدودیت در تکنولوژی‌های ساخت کامپیوترهای کوانتومی، طراحی یک کامپیوتر کوانتومی در مقیاس بزرگ با چالش‌های زیادی مواجه است. یک راه حل جهت غلبه بر این چالش‌ها، طراحی سیستم‌های کوانتومی توزیع‌شده است. در این سیستم‌ها، کامپیوترهای کوانتومی از طریق پروتکل دورنوردی جهت انتقال اطلاعات کوانتومی با یکدیگر در ارتباط هستند. از آنجایی‌که دورنوردی کوانتومی نیاز به منابع کوانتومی دارد، کاهش تعداد این پروتکل، ضروری می‌باشد. هدف از این مقاله، ارائه یک سیستم کوانتومی توزیع‌شده با درنظرگرفتن دو هدف توزیع متوازن کیوبیت‌ها و کمینه‌نمودن تعداد پروتکل دورنوردی در دو سطح است. در سطح اول با ارائه یک الگوریتم برنامه‌سازی پویا، سعی در افراز متعادل کیوبیت‌ها و کاهش تعداد ارتباطات بین زیرسیستم‌ها شده است. با توجه به افراز به‌دست‌آمده از سطح اول، در سطح دوم و در مرحله اجرای دروازه‌های سراسری، زمانی که یکی از کیوبیت‌های این دروازه از مبدأ به مقصد مورد نظر دورنورد می‌گردد، ممکن است این کیوبیت بتواند توسط تعدادی دروازه سراسری با رعایت محدودیت‌های تقدم مورد استفاده قرار گرفته و در نتیجه، موجب کاهش تعداد دورنوردی‌ها گردد. نتایج به‌دست‌آمده، نشان‌دهنده کارایی بهتر الگوریتم پیشنهادی بوده است.
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