کد مقاله : 1400112134075 بازدید : 1421 صفحه: 193 - 201

نوع مقاله: پژوهشی

یک روش دوسطحی مبتنی بر برنامه‌سازی پویا جهت افراز و بهینه‌سازی هزینه ارتباطات در مدارات کوانتومی توزیعی

محورهای موضوعی : مهندسی برق و کامپیوتر

زهره داورزنی ¹ , مریم زمردی مقدم ² , محبوبه هوشمند ³

1 - گروه مهندسی کامپیوتر، دانشگاه پیام نور
2 - گروه علوم کامپیوتر و ارتباطات، دانشگاه صنعتی کراکف لهستان
3 - گروه مهندسی کامپیوتر، دانشگاه آزاد اسلامی واحد مشهد

تاریخ دریافت : 1400/11/21 تاریخ پذیرش : 1401/08/23 تاریخ انتشار : 1402/12/01

کلید واژه: دورنوردی کوانتومی, برنامه‌سازی پویا, افراز, توازن بار, محاسبات کوانتومی توزیع‌شده,

چکیده مقاله :

امروزه محاسبات کوانتومی نقشی بسزا در افزایش سرعت الگوریتم‌ها دارند. به‌دلیل محدودیت در تکنولوژی‌های ساخت کامپیوترهای کوانتومی، طراحی یک کامپیوتر کوانتومی در مقیاس بزرگ با چالش‌های زیادی مواجه است. یک راه حل جهت غلبه بر این چالش‌ها، طراحی سیستم‌های کوانتومی توزیع‌شده است. در این سیستم‌ها، کامپیوترهای کوانتومی از طریق پروتکل دورنوردی جهت انتقال اطلاعات کوانتومی با یکدیگر در ارتباط هستند. از آنجایی‌که دورنوردی کوانتومی نیاز به منابع کوانتومی دارد، کاهش تعداد این پروتکل، ضروری می‌باشد. هدف از این مقاله، ارائه یک سیستم کوانتومی توزیع‌شده با درنظرگرفتن دو هدف توزیع متوازن کیوبیت‌ها و کمینه‌نمودن تعداد پروتکل دورنوردی در دو سطح است. در سطح اول با ارائه یک الگوریتم برنامه‌سازی پویا، سعی در افراز متعادل کیوبیت‌ها و کاهش تعداد ارتباطات بین زیرسیستم‌ها شده است. با توجه به افراز به‌دست‌آمده از سطح اول، در سطح دوم و در مرحله اجرای دروازه‌های سراسری، زمانی که یکی از کیوبیت‌های این دروازه از مبدأ به مقصد مورد نظر دورنورد می‌گردد، ممکن است این کیوبیت بتواند توسط تعدادی دروازه سراسری با رعایت محدودیت‌های تقدم مورد استفاده قرار گرفته و در نتیجه، موجب کاهش تعداد دورنوردی‌ها گردد. نتایج به‌دست‌آمده، نشان‌دهنده کارایی بهتر الگوریتم پیشنهادی بوده است.

چکیده انگلیسی:

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

متن کامل:

معرفي يک روش جديد خوشه‌يابي خودکار

مقاله پژوهشی

یک روش دوسطحی مبتنی بر برنامه‌سازی پویا جهت افراز و بهینه‌سازی هزینه ارتباطات در مدارات کوانتومی توزیعی

زهره داورزنی، مریم زمردی مقدم و محبوبه هوشمند

چکیده: امروزه محاسبات کوانتومی نقشی بسزا در افزایش سرعت الگوریتم‌ها دارند. به‌دلیل محدودیت در تکنولوژی‌های ساخت کامپیوترهای کوانتومی، طراحی یک کامپیوتر کوانتومی در مقیاس بزرگ با چالش‌های زیادی مواجه است. یک راه حل جهت غلبه بر این چالش‌ها، طراحی سیستم‌های کوانتومی توزیع‌شده است. در این سیستم‌ها، کامپیوترهای کوانتومی از طریق پروتکل دورنوردی جهت انتقال اطلاعات کوانتومی با یکدیگر در ارتباط هستند. از آنجایی‌که دورنوردی کوانتومی نیاز به منابع کوانتومی دارد، کاهش تعداد این پروتکل، ضروری می‌باشد. هدف از این مقاله، ارائه یک سیستم کوانتومی توزیع‌شده با درنظرگرفتن دو هدف توزیع متوازن کیوبیت‌ها و کمینه‌نمودن تعداد پروتکل دورنوردی در دو سطح است. در سطح اول با ارائه یک الگوریتم برنامه‌سازی پویا، سعی در افراز متعادل کیوبیت‌ها و کاهش تعداد ارتباطات بین زیرسیستم‌ها شده است. با توجه به افراز به‌دست‌آمده از سطح اول، در سطح دوم و در مرحله اجرای دروازه‌های سراسری، زمانی که یکی از کیوبیت‌های این دروازه از مبدأ به مقصد مورد نظر دورنورد می‌گردد، ممکن است این کیوبیت بتواند توسط تعدادی دروازه سراسری با رعایت محدودیت‌های تقدم مورد استفاده قرار گرفته و در نتیجه، موجب کاهش تعداد دورنوردی‌ها گردد. نتایج به‌دست‌آمده، نشان‌دهنده کارایی بهتر الگوریتم پیشنهادی بوده است.

کلیدواژه: دورنوردی کوانتومی، برنامه‌سازی پویا، افراز، توازن بار، محاسبات کوانتومی توزیع‌شده.

1- مقدمه

رایانه کوانتومی، ماشینی است که از پدیده‌ها و قوانین مکانیک کوانتوم مانند برهم‌نهی² و درهم‌تنیدگی³ برای انجام محاسبات استفاده می‌کند و با رایانه‌های فعلی که با ترانزیستورها کار می‌کنند، تفاوت اساسی دارد. ایده اصلی نهفته در پس رایانه‌های کوانتومی، این است که می‌توان از خواص و قوانین فیزیک کوانتوم برای ذخیره‌سازی و انجام عملیات روی داده‌ها استفاده کرد؛ در حالی که یک کامپیوتر کلاسیک می‌تواند یک کامپیوتر کوانتومی را شبیه‌سازی کند، اما به روشی کارا آن را انجام نمی‌دهد. کامپیوترهای کوانتومی، افزایش سرعت اساسی نسبت به کامپیوترهای کلاسیک دارند و این مزیت سرعت، چنان چشمگیر است که محققان اعتقاد دارند هیچ پیشرفت قابل توجهی در کامپیوترهای کلاسیک، فضای خالی بین توان یک کامپیوتر کلاسیک و یک کامپیوتر کوانتومی را پر نخواهد کرد. همچنین با پیشرفت روزافزون تکنولوژی، این محاسبات با محدودیت‌هایی مانند اتلاف گرما و کاهش سرعت مواجه هستند. از طرفی قدرت محاسبات کوانتومی با افزایش تعداد کیوبیت‌های آن به‌صورت نمایی رشد می‌کند [1]. از چالش‌های اساسی در محاسبات کوانتومی این است که کیوبیت‌ها با کوچک‌ترین اغتشاشی در محیط خراب شده و از بین می‌روند؛ مگر اینکه در دمای بسیار پایینی نگهداری شوند. یکی از اغتشاشاتی که منجر به ازبین‌رفتن اطلاعات کوانتومی و ایجاد ناهمدوسی⁴ کیوبیت‌ها می‌شود، تعاملشان در محیط است که با افزایش تعداد آنها، این اطلاعات شکننده شده و در معرض خطا قرار می‌گیرند. بنابراین ساخت کامپیوترهای کوانتومی در مقیاس بزرگ و با تعداد کیوبیت‌های زیاد، بسیار چالش‌برانگیز و در عین حال دستیابی به آن، هدفی بسیار ارزشمند است. برای غلبه بر مشکل ذکرشده می‌توان برای داشتن سیستم کوانتومی در مقیاس بزرگ، آن را در تعدادی زیرسیستم کوانتومی با تعداد کیوبیت کمتر تجزیه کرد و یک سیستم کوانتومی توزیع‌شده به‌وجود آورد. بنابراین ساخت کامپیوتر‌های کوانتومی توزیع‌شده ضروری است [2].

یکی از کاربرد‌های جدید امروز و آینده در محاسبات کوانتومی که مورد توجه طرفداران تکنولوژی بوده و در آن با بهره‌‌برداری از خصوصیات کوانتومی عجیب فوتون‌ها و الکترون‌ها، پیام‌ها و اطلاعات به‌طور امن ارسال می‌شوند، اینترنت کوانتومی است. این خصوصیات سبب می‌گردند تا دولت‌ها، ارتش‌ها، بانک‌ها و مؤسسات مالی برای امنیت تمام امور خود از جمله قراردادها و تراکنش‌های مالی به اینترنت کوانتومی تمایل نشان دهند. اینترنت کوانتومی، از چارچوب‌های اصلی و اساسی در سیستم‌های کوانتومی توزیع‌شده است که در آن از خاصیت درهم‌تنیدگی کوانتومی استفاده می‌شود [3]. در این پدیده، دو ذره کوانتومی (حتی در فواصل بسیار دور) اطلاعات خود را با یکدیگر به اشتراک می‌گذارند. در واقع با استفاده از جفت فوتون‌های ایجادشده می‌توان اطلاعات کوانتومی را با استفاده از این خاصیت بین دو نقطه جابه‌جا کرد. از این خاصیت در شبکه‌های کوانتومی نظیر اینترنت کوانتومی و در حالت کلی‌تر در سیستم‌های کوانتومی توزیع‌شده، فراوان استفاده می‌شود.

شبکه‌های کوانتومی توزیع‌شده، شامل تعدادی سیستم‌های کوانتومی هستند که در فواصل دور از هم قرار دارند و از قوانین و پدیده‌های اساسی مکانیک کوانتومی مثل ابربرهم‌نهی⁵، درهم‌تنیدگی و اندازه‌گیری کوانتومی جهت انتقال اطلاعات خود استفاده می‌کنند که در کابردهای جدید بسیاری قابل استفاده هستند [4]. برای داشتن یک کامپیوتر کوانتومی در مقیاس بزرگ می‌توان شبکه‌ای از کامپیوترهای کوانتومی با ظرفیت محدود (تعداد کیوبیت‌های محدود و مشخص) داشت؛ به‌طوری که ارتباط بین آنها از طریق یک کانال کوانتومی یا کلاسیک و یا هر دو باشد و بتواند رفتار کل سیستم را پیاده‌سازی کند. این ساختار به‌عنوان کامپیوتر کوانتومی توزیع‌شده⁶ شناخته می‌شود [5].

یک سیستم کوانتومی توزیع‌شده، نیازمند مکانیزم و پروتکلی برای ایجاد ارتباط بین زیر‌سیستم‌هاست که پروتکل دورنوردی⁷ نام دارد و از خاصیت در‌هم‌تنیدگی کیوبیت‌ها برای توزیع اطلاعات کوانتومی استفاده می‌کند [6] و در تکنولوژی‌های بسیاری مانند علم فوتون⁸ [7]، NMR [8] و یون‌های به‌دام‌افتاده [9] کاربرد دارد. این پروتکل دارای هزینه زیادی برای سیستم کوانتومی است. طبق قضیه تکثیرناپذیری⁹ کوانتومی، زمانی که یک کیوبیت به مقصد خود دورنوردی می‌شود، نمی‌تواند در زیرسیستم خود استفاده گردد و تا زمان برگشت کیوبیت دورنوردی‌شده، امکان استفاده از کیوبیت در زیرسیستم خود وجود ندارد. به‌همین دلیل تعداد دورنوردی‌ها در یک سیستم کوانتومی توزیع‌شده، چالشی اساسی است و در نتیجه ارائه یک الگوریتم جهت کاهش این تعداد، کمک قابل توجهی به طراحی و توسعه دیگر مدارهای کوانتومی خواهد کرد.

در سیستم‌های کوانتومی توزیعی، هر زیرسیستم دارای تعداد مشخص کیوبیت است و کل سیستم توزیع‌شده از تعدادی دروازه‌های محلی¹⁰ و سراسری¹¹ تشکیل می‌شود. دروازه‌های محلی بر روی کیوبیت‌های هر زیرسیستم اعمال می‌گردند؛ اما دروازه‌های سراسری بین دو زیرسیستم قرار گرفته‌اند و نیازمند استفاده از دو کیوبیت در دو زیرسیستم مختلف هستند و برای اجرای این دروازه‌ها نیاز به دو بار ارسال کیوبیت برای رفت و برگشت آن با استفاده از پروتکل دورنوردی می‌باشد. به دلیل پیچیدگی بالای سیستم‌های كوانتومی، طراحی سیستم‌های كوانتومی توزیع‌شده و بهینه‌سازی آنها در یك سطح، امری دشوار است. راهکار پیشنهادی مقاله این است تا بتوان سیستم مورد نظر را در دو سطح به‌طور سلسله‌مراتبی بهینه نمود که در ادامه آمده‌اند.

سطح اول: در این سطح با استفاده از یک الگوریتم برنامه‌سازی پویا، سعی در افراز¹² کیوبیت‌های مدار کوانتومی با درنظرگرفتن دو هدف توزیع متوازن¹³ و کمینه‌نمودن تعداد ارتباطات بین زیرسیستم‌ها شده است. در این سطح، تعداد ارتباطات بین زیرسیستم‌ها برابر تعداد دروازه‌های سراسری بین سیستم‌ها خواهد بود. خروجی الگوریتم سطح اول، برچسب‌گذاری کیوبیت‌ها به است؛ به‌طوری که دو هدف زیر برآورده گردند:

- توزیع متوازن کیوبیت‌ها

(1)

که ، و به‌ترتیب برابر مجموعه کیوبیت‌های سیستم، تعداد افرازها یا زیرسیستم‌ها و فاکتور توازن بار هستند.

- کمینه‌کردن تعداد ارتباطات بین زیرسیستم‌ها: الگوریتم ارائه‌شده باید بتواند کیوبیت‌ها را طوری بین زیرسیستم‌ها توزیع کند که تعداد ارتباطات کمینه شود.

سطح دوم: با توجه به افراز به‌دست‌آمده از سطح اول در مرحله اجرای دروازه‌های سراسری کوانتومی، زمانی که یکی از کیوبیت‌های این دروازه از مبدأ خود به مقصد مورد نظر دورنورد می‌گردد، ممکن است کیوبیت دورنوردشده بتواند توسط تعدادی دروازه سراسری دیگر با رعایت محدودیت‌های پیش‌نیازی، مورد استفاده قرار گرفته و در نتیجه موجب کاهش تعداد دورنوردی‌ها گردد.

بخش 2 به بیان مطالعات صورت‌گرفته تا کنون در محاسبات کوانتومی توزیع‌شده پرداخته است. در بخش 3 الگوریتم پیشنهادی در دو سطح ارائه گردیده و نهایتاً بررسی نتایج الگوریتم ارائه‌شده در بخش 4 آمده است.

2- کارهای مرتبط

محاسبات کوانتومی توزیع‌شده بیش از 15 سال مورد مطالعه قرار گرفته‌اند [10]. به‌طور کلی مطالعاتی که در زمینه سیستم‌های کوانتومی توزیع‌شده انجام گردیده است، به دو دسته کلی تقسیم می‌شوند که در ادامه به توضیح هر یک از آنها می‌پردازیم.

دسته اول مطالعاتی هستند که بر روی نحوه پیاده‌سازی فیزیکی این سیستم‌ها تمرکز داشته‌اند و فاقد دید الگوریتمیک و بهینه‌سازی در زمینه کاهش تعداد دورنوردی‌های کوانتومی و سنتز مدارها هستند. اولین مطالعات و پیشنهادها در مورد آنها توسط گرور [10]، کلو و بهرمن [11] و بعد از آن توسط کیرک در [12] بوده است. گرور [10] سیستم کوانتومی توزیع‌شده‌ای ارائه داد که در آن ذرات در مکان‌هایی با فواصل دور از هم قرار گرفته‌اند و هر کدام محاسبات خود را انجام داده و در صورت نیاز، اطلاعات مورد نیاز را به یک ایستگاه پایه ارسال می‌نمایند. وی نشان داد که با استفاده از محاسبات کوانتومی توزیع‌شده، با توجه به تعداد ذرات توزیع‌شده، زمان محاسبات کلی نسبتاً سریع‌تر است. او در مقاله‌ای دیگر، الگوریتمی ارائه داد و آن را بر روی یک سیستم توزیعی که دارای هزینه محاسباتی زیادی بود، اعمال نمود.

یپز و همکاران [13] یک معماری برای محاسبات کوانتومی توزیع‌شده که دارای دو نوع ارتباط I و II بود، ارائه کردند. آنها سیستم‌های کوانتومی توزیع‌شده را در دو نوع به این صورت تعریف نمودند: کامپیوترهای کوانتومی نوع I از ارتباطات کوانتومی بین زیرسیستم‌ها استفاده می‌کنند. در این نوع کامپیوترها هر کیوبیت می‌تواند با هر یک از کیوبیت‌های
دیگر درهم‌تنیده شود؛ اما در نوع II، کامپیوترهای کوانتومی از ارتباطات کلاسیک بین زیرسیستم‌ها استفاده می‌نمایند. در این دسته از کامپیوترها، کامپیوترهای کوانتومی آرایه‌ یا شبکه‌ای از کامپیوترهای کوانتومی کوچک را در نظر گرفتند که با استفاده از کانال ارتباطی کلاسیک به هم متصل شده‌اند. برخلاف نوع I که هر کیوبیت می‌توانست با هر کیوبیت دلخواه ارتباط برقرار نماید، در این نوع هر کیوبیت تنها با کیوبیت‌های نزدیک خود و در زمان کوتاه درهم‌تنیده می‌شود.

از آنجایی که تعدادی از الگوریتم‌های کوانتومی به تعداد زیادی کیوبیت (حداقل میلیون‌ها) نیاز دارند که این کیوبیت‌ها در فاصله کوتاهی از یکدیگر (حداقل در فاصله یک مولکول) و یا فقط در زمان کوتاهی (کمتر از زمان ناهمدوسی اسپین- اسپین ) با یکدیگر در هم تنیده شوند [14] و [15]. اینچنین الگوریتم‌های کوانتومی باید روی آرایه و شبکه‌ای از کامپیوترهای کوانتومی با تعداد کیوبیت اندک پیاده شوند؛ به‌طوری که گره‌ها با استفاده از یک شبکه ارتباط کلاسیک با یکدیگر در ارتباط باشند. بنابراین نیاز به کامپیوترهای کوانتومی از نوع II احساس می‌گردد.

بیل و همکارانش [16] یک سیستم کوانتومی توزیع‌شده ارائه دادند که در آن گره‌ها طبق یک گراف ابرمکعب¹⁴ چیده شده و از کیوبیت‌هایی که با فاصله زیادی از هم قرار گرفته‌اند، استفاده می‌کند. آنها نشان دادند
که هر مدار کوانتومی دلخواه می‌تواند با استفاده از یک مدار کوانتومی توزیع‌شده با گره‌های متصل‌شده بر اساس یک ابرمکعب طراحی شود.

زمانی که دو کیوبیت از دو سیستم کوانتومی جدا از هم باید با یکدیگر تعامل کنند، دو راه انتخاب مختلف وجود دارد: اول اینکه کیوبیت می‌تواند از یک کامپیوتر به کامپیوتر دیگر انتقال یابد و سپس دروازه بین آنها اعمال شود. دوم اینکه می‌توان از یک دروازه دورنوردشده به‌طور مستقیم روی کیوبیت‌ها استفاده نمود؛ بدون اینکه کیوبیت‌ها انتقال داده شوند. نویسندگان در [17] دو نوع مختلف دورنوردی را مطرح نمودند: در نوع اول دروازه‌ها دورنوردی می‌شوند؛ بدون اینکه کیوبیتی انتقال داده شود (telegate) و در نوع دوم کیوبیت‌ها انتقال داده شده و الگوریتم روی دروازه‌های محلی که از طریق دورنوردی‌نمودن کیوبیت‌ها ایجاد شده‌اند، انجام می‌شوند (teledata). نویسندگان در [18] نشان دادند که مدار دورنوردی می‌تواند برای دورنوردی‌کردن یک دروازه CNOT مورد استفاده قرار گیرد. برای این کار آنها به دو زوج درهم‌تنیده احتیاج داشتند؛ اما در مطالعه‌ای که در [17] انجام شده است، آنها با استفاده از دروازه‌های pariaty توانستند از یک زوج درهم‌تنیده برای دورنوردی‌کردن یک دروازه استفاده نمایند.

یكی از كاربردهای اصلی و اساسی محاسبات كوانتومی توزیع‌شده، استفاده آنها در اینترنت كوانتومی است. نویسندگان در [19] به افزایش نمایی سرعت محاسبات کوانتومی اشاره کردند که از طریق ارتباطات کامپیوترهای کوانتومی با استفاده از اینترنت کوانتومی به دست آمده است. آنها در مطالعه خود بیان نمودند که استفاده از اینترنت کوانتومی با محدودیت‌هایی مانند عدم کپی‌برداری، درهم‌تنیدگی و دورنوردی کوانتومی مواجه است؛ در حالی که در شبکه‌های کلاسیک این چالش‌ها موجود نیستند و بنابراین در مطالعه خود به بررسی این چالش‌ها پرداختند. آنها بیان نمودند که چگونه می‌‌توان کیوبیت‌های یک سیستم را افزایش داد تا بتوان به برتری کوانتومی دست یافت. پاسخ این بود تا کامپیوترهای کوانتومی از طریق اینترنت کوانتومی با یکدیگر در تعامل باشند. برای مثال دو سیستم کوانتومی مجزای ده‌کیوبیتی می‌توانند 210 حالت کوانتومی را ارائه دهند و بنابراین این دو سیستم حالت را نشان دهند؛ اما اگر از طریق اینترنت کوانتومی با یکدیگر تعامل داشته باشند، می‌توانند 218 حالت را نشان دهند.

نویسندگان در [19] به مطالعه و بررسی چالش‌های موجود در اینترنت کوانتومی پرداختند. همان طور که از طریق اینترنت کنونی می‌توان اطلاعات را منتقل نمود، از طریق اینترنت کوانتومی نیز می‌توان ارتباطات مورد نیاز را انجام داد. برای مثال نمونه‌ای از ارتباطات کوانتومی در توزیع کلید کوانتومی ¹⁵(QKD) می‌باشد. QKD یک پروتکل نهان‌نگاری¹⁶ است که می‌تواند بین دو ذره، یک کلید تصادفی مشترک با استفاده از قوانین مکانیک کوانتوم ایجاد کند. همچنین آنها بیان نمودند که با استفاده از اینترنت کوانتومی می‌توان حالت‌های کوانتومی را بین گره‌های از راه دور به اشتراک گذاشت؛ اما همان طور که قبلاً بیان شد، یک کیوبیت با محدودیت‌هایی مانند کپی‌برداری و اندازه‌گیری مواجه است. اگرچه یک فوتون می‌تواند یک کیوبیت را رمز نماید¹⁷ و به گره‌های راه دور (از طریق فیبر نوری) ارسال کند، اما چنانچه فوتون ارسال‌شده در معرض نویز قرار گیرد، اطلاعات کوانتومی از بین می‌روند و از آنجا که اطلاعات کوانتومی بر طبق قضیه عدم کپی قابلیت کپی‌برداری ندارد، بنابراین انتقال مستقیم اطلاعات کوانتومی از طریق فوتون امکان‌پذیر نیست و باید از پروتکل دورنوردی استفاده شود.

دسته دوم برخلاف دسته اول، شامل مطالعاتی است که به پیاده‌سازی و معماری این سیستم‌ها توجه نداشته و گامی در جهت بهینه‌سازی مدار توزیع‌شده با رویکرد کاهش تعداد دورنوردی‌های کوانتومی داشته‌اند.

پابلو و همکاران [20] الگوریتمی خودکار جهت توزیع مدار کوانتومی به چندین زیرسیستم ارائه نمودند. آنها مسئله توزیع مدارهای کوانتومی را به مسئله افراز ابرگراف¹⁸ کاهش دادند و با استفاده از الگوریتم افراز ابرگراف که در [21] ارائه شده است، مدار را به چند زیرسیستم توزیع نمودند. ایده اصلی الگوریتم پیشنهادی آنها در این بود زمانی که دو دروازه سراسری پشت سر هم وجود دارند که دارای کیوبیت کنترلی مشترک هستند، با دورنوردی کیوبیت کنترلی اولین دروازه، دروازه دوم نیز اجرا شود.

زمردی و همکاران [22] الگوریتمی جهت کاهش تعداد دورنوردی‌های مورد نیاز در یک مدار کوانتومی ارائه دادند. در این الگوریتم از دو سیستم کوانتومی مجزا که در فواصل طولانی از همدیگر قرار گرفته‌اند، استفاده شده است. آنها دو سیستم کوانتومی را در نظر گرفته و کیوبیت‌ها را به‌طور مساوی در آن توزیع نمودند. همچنین در کار خود نشان دادند که چنانچه یکی از کیوبیت‌های یک دروازه سراسری از زیرسیستم مبدأ به زیرسیستم مقصد دورنوردی شود، می‌تواند توسط دیگر دروازه‌های سراسری مورد استفاده قرار گیرد و سپس به زیرسیستم مبدأ خود بازگردد. آنها همچنین بیان نمودند که اگر سیستم توزیع‌شده دارای $n$ دروازه سراسری باشد، تعداد پیکربندی ممکن برای انجام دورنوردی‌های لازم بر روی دو زیرسیستم کوانتومی در نظر گرفته شده است. الگوریتم آنها برای دو بخش ثابت بوده و برای چند بخش بررسی نشده است. در کار دیگری از زمردی و همکاران [23]، آنها الگوریتمی تکاملی ارائه دادند تا مسئله کاهش تعداد دورنوردی‌ها در دو زیرسیستم را به‌صورت کاراتر در زمان چندجمله‌ای حل کند.

نویسندگان در [24]، یک الگوریتم مبتنی بر برنامه‌سازی پویا را جهت افراز مدار کوانتومی ارائه دادند؛ اما در کار خود مسئله توزیع متوازن کیوبیت‌ها را در نظر نگرفتند. همچنین هیچ بهینه‌سازی را پس از افراز مدار کوانتومی در جهت کاهش تعداد دورنوردی‌های کوانتومی ارائه ندادند. این نویسندگان در مطالعه‌ای دیگر با استفاده از الگوریتم NSGA-II و درنظرگرفتن سه هدف، مسئله افراز مدار کوانتومی به دو بخش را حل نمودند و سپس به ارائه دو هیوریستیک جهت کاهش تعداد دورنوردی‌های کوانتومی در سطح دوم پرداختند.

دایی و همکاران در [25] با استفاده از الگوریتم بهبودیافته افراز K-L، الگوریتمی را ارائه دادند تا بتواند یک مدار کوانتومی یکنواخت را در چند بخش توزیع کند. الگوریتم آنها مدار کوانتومی را به‌صورت یک گراف بدون جهت وزن‌دار در نظر می‌گرفت و سپس با اعمال الگوریتم افراز
K-L این گراف را به چند زیرگراف تجزیه می‌نمود. محدودیت کارشان در این بود که آنها تعداد دورنوردی‌های کوانتومی را در سطح اول کاهش دادند و به بررسی سطوح پایین‌تر نپرداختند.

در مطالعه‌ای دیگر [26] به افرازبندی مدار کوانتومی و توزیع آن در تعدادی زیرسیستم کوانتومی پرداخته شد. نویسندگان در این مطالعه، دو مفهوم دورنوردی کیوبیت و دروازه‌ها را با یکدیگر ترکیب نمودند تا بتوانند تعداد ارتباطات بین زیرسیستم‌ها را کاهش دهند و برای این کار الگوریتمی مبتنی بر برنامه‌ریزی خطی ارائه دادند.

3- الگوریتم پیشنهادی

همان طور که در بخش قبل بیان گردید، طراحی سیستم‌های كوانتومی توزیع‌شده و بهینه‌سازی آنها در یك سطح به دلیل پیچیدگی بالای سیستم‌های كوانتومی، امری دشوار است. راهکار پیشنهادی مقاله این است تا بتوان سیستم مورد نظر را در دو سطح به‌طور سلسله‌مراتبی بهینه نمود که در ادامه به ارائه هر یک از آنها پرداخته شده است.

3-1 افرازبندی سطح اول

هدف از این سطح آن است تا کیوبیت‌های مدار در تعدادی زیرسیستم کوانتومی به‌طور متوازن توزیع شوند؛ به‌طوری‌ که تعداد ارتباطات بین این سیستم‌ها کمینه گردد. از آنجایی که این مسئله NP-Hard است [27]، الگوریتمی دقیق با زمان چندجمله‌ای برای آن وجود ندارد. در این سطح در ابتدا با استفاده از روش ارائه‌شده در [24] مدار کوانتومی به یک گراف دوبخشی تبدیل می‌گردد و سپس با استفاده از یک الگوریتم برنامه‌سازی پویا به افرازبندی متعادل کیوبیت‌ها در K زیرسیستم پرداخته شده است.

وجود دروازه‌های با بیشتر از دو ورودی در مدار، نیاز به دسترسی هم‌زمان به کیوبیت‌ها دارد و ساخت و پیاده‌سازی آنها کاری دشوار است. در روش پیشنهادی، بدون ازدست‌دادن کلیت مسئله، دروازه‌های با بیشتر از دو ورودی حذف می‌شوند و با دروازه‌های تک‌کیوبیتی و دوکیوبیتی جایگزین می‌گردند.

فرض شود که مدار کوانتومی QC شامل مجموعه‌ای از کیوبیت‌ها  و مجموعه‌ای از دروازه‌های کوانتومی  است و  و  به‌ترتیب تعداد کیوبیت‌ها و مجموعه‌ دروازه‌های دوکیوبیتی مدار باشند. در یک گراف دوبخشی، مجموعه رأس‌های گراف به دو مجموعه مجزای
و  تقسیم می‌گردد؛ به‌طوری که هر یک از یال‌های گراف دارای
یک رأس در مجموعه  و یک رأس در  هستند. در گراف دوبخشی که در [24] آمده است، مجموعه کیوبیت‌های مدار در سمت  و مجموعه دروازه‌های دوکیوبیتی مدار در سمت  از گراف دوبخشی قرار گرفته‌اند و دروازه‌های دوکیوبیتی مدار، رئوس این دو مجموعه را به هم متصل می‌کند.

می‌توان مسئله افرازبندی متوازن کیوبیت‌های مدار کوانتومی را که در یک سمت از گراف دوبخشی قرار گرفته است، با رویکرد کاهش تعداد ارتباطات بین زیرسیستم‌ها به یک مسئله بهینه‌سازی با استفاده از الگوریتم برنامه‌سازی پویا نگاشت نمود. در این نگاشت، تعداد افراز‌ها یا تعداد زیرسیستم‌ها برابر تعداد مراحلی است که الگوریتم برنامه‌سازی پویا، مسئله افرازبندی مدار کوانتومی را حل می‌کند. در هر مرحله از الگوریتم، مجموعه کیوبیت‌هایی که باید در یک زیرسیستم قرار بگیرند، به‌دست خواهد آمد.

رابطه بازگشتی ارائه‌شده برای حل مسئله در (2) آمده است

(2)

فرض شود که کیوبیت‌های مدار در مجموعه قرار گرفته‌اند و این کیوبیت‌ها می‌خواهند در زیرسیستم توزیع شوند. رابطه اصلی به‌صورت فراخوانی می‌گردد و بیانگر کمینه تعداد ارتباطات مورد نیاز جهت افرازبندی مجموعه در بخش می‌باشد. واضح است که در شروع الگوریتم، این مقدار به‌صورت فراخوانی می‌گردد. این رابطه از سه قسمت تشکیل شده است: قسمت اول آن انتخاب زیرمجموعه‌ای مناسب به نام بوده که این مجموعه برابر کیوبیت‌هایی است که باید در زیرسیستم یا بخش ام قرار گیرند و از آنجایی که مسئله توازن بار در افرازبندی کیوبیت‌ها امری ضروری و حیاتی است، اندازه این زیرمجموعه باید دارای دو ویژگی زیر باشد:

- اندازه زیرمجموعه باید حداکثر حد بالای را

داشته باشد.

- با توجه به تعیین حد بالا برای اندازه مجموعه ، باید حد پایینی برای آن نیز در نظر گرفت؛ زیرا از آنجا که باید تعداد کیوبیت‌های سایر زیرسیستم‌ها از حد بالای بیان‌شده در مورد اول بیشتر نشود، در هر مرحله اندازه زیرمجموعه باید دارای حد پایین بیان‌شده در (3) باشد

(3)

همان طور که پیشتر بیان گردید، انتخاب اندازه مناسب برای مجموعه‌ به معنای تعداد کیوبیت‌هایی است که در یک زیرسیستم قرار می‌گیرند. از آنجایی که هر زیرسیستم دارای ظرفیت محدودی از لحاظ تعداد کیوبیت‌ها است، انتخاب مناسب اندازه آن در توزیع متوازن کیوبیت‌ها و تعداد دورنوردی‌های کوانتومی تأثیر می‌گذارد.

قسمت دوم این تابع بازگشتی، شمارش تعداد دروازه‌های سراسری بین دو زیرمجموعه‌ و است. به عبارتی هر دروازه‌ای که بین مجموعه‌ کیوبیت‌های مجموعه و در گراف دوبخشی وجود دارد، یک دروازه سراسری است و دروازه سراسری نیاز به ایجاد ارتباط بین زیرسیستم و مجموعه می‌باشد. محاسبه تعداد دروازه‌های سراسری بیان‌شده با استفاده از تابعی با نام Connect انجام می‌شود که در (4) آمده است

(4)

بخش سوم تابع، شامل فراخوانی بازگشتی تابع می‌باشد که به‌صورت فراخوانی می‌گردد. به عبارتی باقیمانده کیوبیت‌های مدار باید در زیرسیستم توزیع شوند.

در این رابطه بازگشتی دو شرط توقف زیر وجود دارد:

- چنانچه و اندازه مجموعه حداکثر

باشد، مقدار برابر صفر قرار می‌گیرد.

- چنانچه در هر سطح از درخت در محاسبه محدودیت

نقض گردید، درخت هرس‌شده و مقدار آن

برابر بی‌نهایت قرار می‌گیرد؛ زیرا حداقل تعداد کیوبیت‌های یکی از افرازها از مقدار حد بالای ممکن و ظرفیت خود تجاوز نموده و شرط توازن بار رعایت نمی‌گردد.

3-2 بهینه‌سازی سطح دوم

یک مدار کوانتومی از مجموعه‌ای از سیم‌های افقی (کیوبیت‌ها) و یک توالی از دروازه‌ها تشکیل می‌گردد و همواره از چپ به راست ارزیابی می‌شود. بنابراین حرکت از چپ به راست در یک مدار کوانتومی به معنای حرکت به جلو در زمان است [28] و زمان‌بندی دروازه‌های کوانتومی و رعایت تقدم¹⁹ اجرای آنها امری بسیار ضروری است.

گاهی اوقات می‌توان در یک مدار کوانتومی با دورنوردنمودن یک کیوبیت از مبدأ به مقصد خود، این کیوبیت در مقصد خود و قبل بازگشت به مبدأ مورد استفاده تعدادی دروازه سراسری قرار گیرد؛ به شرط آنکه تقدم اجرای آنها در نظر گرفته شود. در نتیجه می‌توان در بخش مقصد به‌صورت بهینه مورد استفاده قرار گیرد که این به نوبه خود باعث کاهش تعداد دورنوردی‌های کوانتومی می‌گردد. در سطح دوم به بررسی و پیاده‌سازی ایده پیشنهادی پرداخته شده است. شکل 1 تعدادی حالت‌ را نشان می‌دهد که در روش پیشنهادی با آنها مواجه شده و در برخی موارد می‌توان بدون درنظرگرفتن تقدم اجرای دروازه‌ها، آنها را اجرا نمود. در این شکل سه دروازه ، و در نظر گرفته شده است. در ابتدا برای اجرای دروازه ، کیوبیت از این دروازه به بخش دورنورد می‌گردد. با دورنوردشدن این کیوبیت، دروازه به این کیوبیت در بخش نیاز دارد. حالات بیان‌شده در این شکل را می‌توان به سه دسته تقسیم نمود:

- در حالات الف تا د، اجرای دروازه‌ بر اجرای دروازه تقدم دارد و در نتیجه نمی‌توان با یک بار دورنوردنمودن کیوبیت ، هر دو دروازه و را اجرا نمود. در روش پیشنهادی، چنانچه یک کیوبیت دورنورد شده باشد، تا زمانی که به مقصد خورد بازنگردد از دورنوردنمودن کیوبیت‌های دیگر اجتناب می‌شود؛ زیرا ممکن است که با این کار، هر بخش یا زیرسیستم از ظرفیت کیوبیت‌هایی که می‌تواند در خود نگه دارد، تجاوز نماید. از این رو در این موارد، از آنجایی که دروازه دروازه‌ای سراسری بوده و برای اجرا نیاز به دورنوردی دارد، اجرای آن تا زمان برگشت به تعویق می‌افتد.

- در حالات ﻫ و و می‌توان ادعا نمود که دو دروازه و دارای هیچ تقدمی نسبت به یکدیگر نبوده و می‌توان ترتیب اجرای آنها را رعایت نکرد.

- در حالت‌های ز و ح، دروازه به‌ترتیب یک دروازه تک‌کیوبیتی و دوکیوبیتی محلی بوده و دارای تقدم اجرا نسبت به دروازه است. با توجه به اینکه اجرای دروازه در این حالت‌ها نیاز به دورنوردی کوانتومی ندارد می‌توان با رعایت تقدم‌های این دروازه، این دروازه و دروازه را هم‌زمان اجرا نمود.

در ادامه، ایده پیشنهادی در سطح دوم ارائه خواهد شد. همان طور که بیان گردید خروجی سطح اول، شماره افرازهایی است که کیوبیت‌ها به آنها تعلق دارند و در آرایه‌ای با نام قرار گرفته‌اند. این آرایه به‌عنوان ورودی سطح دوم در نظر گرفته می‌شود.

در این الگوریتم آرایه‌ای به نام به اندازه تعداد دروازه‌های مدار در نظر گرفته شده که مقدار بیانگر حالت دروازه است که دارای مقدار 0 (در صورت عدم اجرای دروازه ) و مقدار 1 (در صورت اجرای دروازه ) می‌باشد. دروازه‌های مدار به‌ترتیب از سمت چپ به راست با اندیس بررسی شده‌اند و می‌توانند در یکی از حالات زیر باشند:

- دروازه یک دروازه تک‌کیوبیتی است؛ در این صورت این دروازه اجرا شده و مقداردهی می‌گردد.

- دروازه یک دروازه محلی است؛ در این صورت این دروازه اجرا شده و مقداردهی می‌گردد.

- دروازه یک دروازه سراسری است و برای اجرا نیاز به دو دورنوردی کوانتومی دارد.

در دو مورد اول دروازه بدون بررسی اجرا می‌گردد؛ اما در مورد سوم دروازه جهت اجرا نیاز به دو دورنوردی کوانتومی دارد (یکی برای رفتن کیوبیت از مبدأ به مقصد و دیگری جهت بازگشت آن). فرض شود دروازه دارای دو کیوبیت و بوده و یکی از کیوبیت‌های آن به نام جهت اجرا به بخش مقصد دورنورد شود. در نتیجه به شماره افرازی که دورنوردی می‌شود، تغییر می‌یابد. سپس الگوریتم کل مدار را جستجو نموده تا دروازه اجرانشده‌ای مانند بیابد که برای اجرا نیاز به داشته باشد. فرض گردد دروازه اولین دروازه سراسری باشد که دارای یکی از شرایط زیر است:

- یکی از کیوبیت‌های یا برابر با باشد.

- کیوبیت دیگر آن در قرار گرفته باشد.

سپس به بررسی اجرای دروازه پرداخته می‌شود که در کدام حالات الف تا ح در شکل 1 قرار دارد. یکی از سه حالت زیر می‌تواند اتفاق بیفتد:

- تعدادی دروازه اجرا نشده بین دروازه‌های و وجود دارد؛ به‌طوری‌که این دروازه‌ها نتوانند قبل از اجرای اجرا شوند و اجرای دروازه به آنها وابسته باشد. در این صورت دروازه نمی‌تواند اجرا گردد (حالت‌های الف تا د از شکل 1). فرض شود که اولین دروازه اجرانشده و سراسری بین دروازه‌های و باشد؛ به‌طوری که دروازه‌های و در یک کیوبیت با برچسب‌های متفاوت مشترک بوده و یا اینکه در کیوبیت مشترک دارای برچسب هستند و همچنین کیوبیت دیگر آنها در دو بخش متفاوت قرار داشته باشد. در این صورت دروازه نسبت به دروازه دارای تقدم است. از آنجا که دروازه جهت اجرا نیاز به یک دورنوردی دارد، در نتیجه دروازه‌ نمی‌تواند اجرا شود. چنانچه دروازه‌ دروازه‌‌ای سراسری بوده که با دروازه دارای کیوبیت مشترک با برچسب باشد، آنگاه دروازه و از لحاظ اجرایی به یکدیگر وابستگی نداشته و بنابراین می‌توان از روی دروازه عبور کرد و اجرای آن را بررسی نکرد (حالت‌های ﻫ و و از شکل 1).

- چنانچه یک دروازه اجرانشده تک‌کیوبیتی و یا دروازه‌ای محلی باشد که در یک کیوبیت با دروازه اشتراک داشته باشد، آنگاه اجرای دروازه منوط به اجرای دروازه است (حالت‌های ز و ح از شکل 1).

- اگر هیچ درواز‌ه‌ای مانند با شرایط بیان‌شده در دو حالت قبل بین دروازه‌های و نباشد، می‌توان با دورنوردی‌نمودن کیوبیت ، علاوه بر اجرای دروازه ، دروازه را نیز اجرا نمود؛ در نتیجه مقداردهی می‌گردد.

(الف)

(ب)

(ج)

(د)

(ﻫ)

(و)

$img0$

(ز)

(ح)

[1] این مقاله در تاریخ 21 بهمن ماه 1400 دریافت و در تاریخ 24 مهر ماه 1401 بازنگری شد.

زهره داورزنی، گروه مهندسی کامپیوتر، دانشگاه پیام نور، تهران، ایران،
(email: zohreh.davarzani@pnu.ac.ir).

مریم زمردی مقدم (نویسنده مسئول)، گروه علوم کامپیوتر و ارتباطات، دانشگاه صنعتی کراکف، کراکف، لهستان، (email: zomorodi@pk.edu.pl).

محبوبه هوشمند، گروه مهندسی کامپیوتر، واحد مشهد، دانشگاه آزاد اسلامی، مشهد، ایران، (email: houshmand@mshdiau.ac.ir).

[2] . Superposition

[3] . Entanglement

[4] . Decoherence

[5] . Superposition

[6] . Distributed Quantum Circuit

[7] . Teleportation

[8] . Photonics

[9] . No-Cloning

[10] . Local

[11] . Global

[12] . Partitioning

[13] . Load Balancing

[14] . Hypercube

[15] . Quantum Key Distribution

[16] . Cryptographic

[17] . Encode

[18] . Hypergraph

[19] . Precedence

شکل 1: مواردی که الگوریتم پیشنهادی در سطح دوم نیاز به رعایت تقدم (الف تا د)، عدم رعایت تقدم (ﻫ و و) و بررسی تقدم (ز و ح) دارد.

4- نتایج

در این بخش به ارزیابی روش پیشنهادی بر روی مجموعه مدارهای کوانتومی مختلف پرداخته شده است. جهت ارزیابی روش پیشنهادی با سایر روش‌ها، معیارهای تا به‌صورت زیر معرفی شده‌اند:

- معیار : در این معیار، نسبت تعداد دورنوردی‌های کوانتومی به تعداد دروازه‌های دوکیوبیتی مدار مورد ارزیابی قرار می‌گیرد. این معیار در بازه [0,1] بوده و به‌صورت (5) تعریف می‌شود

شکل 2: درصد دورنوردي‌هاي مورد نياز به دورنوردي‌هاي غيرلازم براي مجموعه مدارهاي 16 تا 25.

(5)

در بدترین افرازبندی مدار کوانتومی، هر دروازه دوکیوبیتی در مدار ممکن است به‌صورت یک دروازه سراسری در نظر گرفته شود و دو برابر تعداد دروازه‌های دوکیوبیتی در مدار به ارتباطات نیاز باشد. در نتیجه نسبت
تعداد دورنوردی‌های به‌دست‌آمده از روش پیشنهادی نسبت به دو برابر دروازه‌های دوکیوبیتی می‌تواند نشان‌دهنده عملکرد روش پیشنهادی باشد. هرچه این معیار به صفر نزدیک‌تر باشد، بیانگر این است که کاهش تعداد دورنوردی‌ها بهتر بوده و الگوریتم بهتر عمل کرده است.

- معیار : برای نشان‌دادن تأثیر بهینه‌سازی سطح دوم بر افرازبندی سطح اول، معیار به صورت (6) تعریف شده است

(6)

که در آن بیانگر تعداد دروازه‌های سراسری است. این معیار بیان می‌کند که بهینه‌سازی سطح دوم چه اندازه تأثیر بر افرازبندی سطح اول دارد و بنابراین درصد نسبت تعداد دورنوردی‌های به‌دست‌آمده از سطح دوم به دو برابر تعداد دروازه‌های سراسری به‌دست‌آمده از سطح اول می‌تواند جهت نشان‌دادن میزان بهبودی که بهینه‌سازی سطح دوم بر سطح اول داشته است، استفاده شود. هرچه این میزان به صفر نزدیک‌تر باشد، نشان‌دهنده بهبود بیشتر است.

- معیار : با توجه به معیار ، پر واضح است که تفاضل دو برابر تعداد دروازه‌های سراسری در سطح اول و تعداد دورنوردی‌های به‌دست‌آمده از سطح دوم، بیانگر تعداد دروازه‌های سراسری است که می‌تواند به صورت محلی در سطح دوم اجرا گردد. بنابراین این تفاضل، بیانگر تعداد دورنوردی‌های غیرلازم از سطح اول بوده و درصد آن می‌تواند با استفاده از (7) محاسبه شود

(7)

هرچه میزان به یك نزدیك‌تر باشد، نشان‌دهنده عملکرد بهتر روش پیشنهادی بوده است؛ زیرا تعداد دروازه‌های بیشتری پس از اعمال سطح دوم توانسته‌اند به‌صورت محلی اجرا شوند.

- معیار : جهت نشان‌دادن متوسط تعداد دورنوردی‌های مورد نیاز به‌ازای هر کیوبیت، معیار به‌صورت (8) تعریف شده است

(8)

در این رابطه، نسبت فضای مورد نیاز برای دورنوردی‌های کوانتومی به تعداد کیوبیت‌های موجود در سیستم آمده است. این معیار بیان می‌کند که به‌طور متوسط به‌ازای هر کیوبیت، چه تعداد دورنوردی کوانتومی مورد نیاز است. هرچه میزان از یک بیشتر باشد، بیانگر این است که به‌طور متوسط به ازای هر کیوبیت نیاز به یک دورنوردی کوانتومی است. هرچه این میزان از یک کمتر باشد، به این معناست که کیوبیت‌های بیشتری با یکدیگر به‌طور محلی در تعامل بوده و توزیع کیوبیت‌ها به‌طور متوسط خوب عمل کرده است. هرچه این میزان از یک بیشتر باشد، به معنای توزیع نامناسب کیوبیت‌ها در افرازها و به این معناست که به‌طور متوسط برخی کیوبیت‌ها بیشتر از یک بار دورنوردی می‌شوند.

الگوریتم پیشنهادی روی مجموعه مدارهای با شماره 1 تا 15 برگرفته از [29] و [30] اعمال شد و با روش مبتنی بر پنجره ارائه‌شده در [26] مقایسه گردید. جدول 1 تعداد دورنوردی‌های کوانتومی به‌دست‌آمده از روش پیشنهادی را در مقایسه با روش [26] روی این مجموعه نشان می‌دهد. همان طور که دیده می‌شود به‌جز در پنج مدار از مجموع 15 مدار، تعداد دورنوردی‌های به‌دست‌آمده از روش پیشنهادی نسبت به روش بیان‌شده در [26] بهتر بوده است.

همچنین معیارهای تا برای مدارات 1 تا 15 در جدول 2 برای الگوریتم پیشنهادی و الگوریتم ارائه‌شده در [26] گزارش گردید. در مقایسه مقادیر و برای روش پیشنهادی و روش ارائه‌شده در [26]، در 9 مورد الگوریتم پیشنهادی دارای مقدار کمتری ، در یک مورد مقدار برابر و 4 مورد بیشتر نسبت به روش دیگر بوده است.

جهت نشان‌دادن تأثیر بهینه‌سازی سطح دوم بر افرازبندی سطح اول، الگوریتم پیشنهادی روی مجموعه مدارهای دیگری با شماره 16 تا 25 برگرفته از [31] اعمال شد. شکل 2 این میزان را نشان می‌دهد. قسمت پایین این نمودار (رنگ آبی) تعداد دورنوردی‌های مورد نیاز پس از اعمال بهینه‌سازی سطح دوم بر افرازبندی سطح اول الگوریتم پیشنهادی را نشان می‌دهد. قسمت بالای نمودار (رنگ نارنجی) تعداد دورنوردی‌های غیرلازم را که از سطح اول به دست آمده است، نشان می‌دهد. به میزان نمودار نارنجی‌رنگ، این تعداد دروازه‌های سراسری با اعمال بهینه‌سازی سطح دوم می‌تواند به‌صورت محلی و بدون نیاز به دورنوردی کوانتومی اجرا گردد. همان طور که نمودار نشان می‌دهد، بیش از 70 درصد دروازه‌های سراسری حاصل از سطح اول به‌صورت محلی اجرا می‌گردد.

5- نتیجه‌گیری

از آنجا که کامپیوترهای کوانتومی دارای محدودیت در تعداد کیوبیت‌ها هستند، داشتن یک سیستم کوانتومی در مقیاس بزرگ امری چالش‌برانگیز و بدین روی، طراحی سیستم‌های کوانتومی توزیع‌شده ضروری است. اتباطات در سیستم‌های کوانتومی توزیع‌شده مبتنی بر پروتکل دورنوردی می‌باشد. این پروتکل مبتنی بر منابع کوانتومی و کلاسیک بوده و کاهش تعداد آن از ضروریات است. به‌دلیل پیچیدگی بالای طراحی سیستم‌های کوانتومی، کمینه‌سازی تعداد دورنوردی‌ها در یک فاز، امری دشوار است. در این مقاله، طراحی و بهینه‌سازی آن در دو سطح انجام شد. در سطح اول به دنبال افرازبندی کیوبیت‌ها در تعدادی زیرسیستم کوانتومی با هدف توزیع متوزان آنها صورت پذیرفت. در این سطح جهت افرازبندی متوازن کیوبیت‌ها، روشی مبتنی بر برنامه‌سازی پویا ارائه گردید. سپس در سطح

جدول 1: تعداد دورنوردی‌های کوانتومی حاصل از الگوریتم پیشنهادی در مقایسه با روش [26].

شماره	نام مدار			K	پیشنهادی	[26]
1		6	104	2	40	40
2		6	21	3	14	11
3	sym6	10	72	2	14	16
4	sym9	12	108	3	22	36
5	bitadder8	24	338	6	46	84
6		20	5861	3	2262	2028
7		15	220	4	144	101
8	50Hwb	56	6430	4	1272	1301
9	100Hwb	107	6430	4	2014	2513
10		5	5	2	4	6
11		7	49	4	34	30
12		8	49	2	8	12
13		13	104	3	16	22
14	247 Parity	17	16	3	6	4
15		49	200	3	6	9

جدول 2: مقادیر تا برای مجموعه مدارهای 1 تا 15.

	روش پیشنهادی				روش [26]
شماره
1	2/0	40	6/0	6/6	2/0	-	-	6/6
2	33/0	53	47/0	3/2	26/0	-	-	83/1
3	09/0	22	78/0	4/1	11/0	-	-	6/1
4	1/0	19	81/0	8/1	16/0	-	-	3
5	06/0	21	79/0	91/1	13/0	-	-	5/3
6	19/0	30	7/0	1/113	18/0	-	-	4/101
7	35/0	62	38/0	6/9	2/0	-	-	73/6
8	06/0	23	77/0	71/22	1/0	-	-	23/23
9	15/0	32	68/0	82/18	2/0	-	-	48/23
10	4/0	20	8/0	8/0	6/0	-	-	2/1
11	34/0	53	47/0	28/5	3/0	-	-	2/4
12	08/0	10	9/0	5/0	1	-	-	5/1
13	08/0	20	8/0	23/1	1/0	-	-	6/1
14	18/0	30	7/0	35/0	125/0	-	-	23/0
15	015/0	43	57/0	12/0	02/0	-	-	18/0

دوم با استفاده از افرازبندی و برچسب‌گذاری‌ به‌دست‌آمده جهت توزیع كیوبیت‌ها از سطح اول، سعی در کاهش تعداد دورنوردی‌های کوانتومی گردید. در این سطح از این ایده الهام گرفته شد: زمانی که یکی از کیوبیت‌های یک دروازه سراسری از مبدأ خود به مقصد مورد نظر دورنورد می‌گردد، می‌تواند قبل از برگشت آن به مبدأ خود توسط تعداد بیشتری دروازه‌های دیگر مورد استفاده قرار گیرد که این مسئله در سطح اول بررسی نمی‌شد. همین امر به کاهش بیش از نیمی از تعداد دورنوردی‌های کوانتومی منجر گردید.

مراجع

[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

زهره داورزني کارشناسي، کارشناسي ارشد و دکتري خود را در رشته مهندسي کامپيوتر، گرايش نرم افزار بهترتيب در سالهاي 1387، 1390 و 1401از دانشگاه فردوسي مشهد دريافت کرده است. دکتر داورزني در حال حاضر استاديار گروه مهندسي کامپيوتر دانشگاه پيام نور است. علايق پژوهشي ايشان شامل الگوريتم و محاسبات کوانتومي، محاسبات نرم و هوش مصنوعي ميباشد.

مریم زمردی مقدم مدارک تحصیلی کارشناسی، کارشناسی‌ارشد و دکترای خود را در رشته مهندسی کامپیوتر به ترتیب از دانشگاه علم و صنعت ایران، دانشگاه صنعتی امیرکبیر و دانشگاه شهید بهشتی، در سال‌های 1381، 1386 و 1393 دریافت کرده است. ایشان در حال حاضر در گروه علوم کامپیوتر و ارتباطات در دانشگاه صنعتی کراکف در لهستان کار می‌کند. علایق تحقیقاتی فعلی ایشان شامل محاسبات کوانتومی، محاسبات تکاملی و یادگیری ماشین است.

محبوبه هوشمند کارشناسی و کارشناسی‌ارشد خود را در رشته مهندسی کامپیوتر، گرایش نر‌م‌افزار بهترتیب در سال‌های 1386 و 1389 از دانشگاه فردوسی مشهد و دکترای خود را در رشته مهندسی کامپیوتر، گرایش معماری‌کامپیوتر از دانشگاه صنعتی امیرکبیر در سال 1393 دریافت کرده است. ایشان از آخر تابستان 1395 تا آخر تابستان 1396 محقق پسا دکترا در زمینه رمزنگاری کوانتومی به طور مشترک در دانشگاه ملی سنگاپور و دانشگاه تکتنولوژی و طراحی سنگاپور بوده است. دکتر هوشمند در حال حاضر استادیار گروه مهندسی کامپیوتر دانشگاه آزاد اسلامی مشهد است. علایق پژوهشی فعلی نامبرده شامل نظریه اطلاعات و محاسبات کوانتومی، سیستم‌های چندعاملی، محاسبات تکاملی و داده‌کاوی است.

اشتراک گذاری

آدرس مقاله

یک روش دوسطحی مبتنی بر برنامه‌سازی پویا جهت افراز و بهینه‌سازی هزینه ارتباطات در مدارات کوانتومی توزیعی

رایمگ

پیوندهای سایت

مراکز مرتبط

پشتیبانی

صفحات رسمی