• Home
  • A Two-Level Method Based on Dynamic Programming for Partitioning and Optimization of the Communication Cost in Distributed Quantum Circuits

Share To

Article Url


Manuscript ID : 1400112134075 Visit : 1468 Page: 193 - 201

Article Type: Original Research

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 engineering

zohreh davarzani 1 , maryam zomorodi-moghadam 2 * , M. Houshmand 3

1 - student
2 -
3 - دانشگاه آزاد اسلامی، واحد مشهد

Received: 2022-02-10 Accepted : 2022-11-14 Published : 2024-02-20

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.

References:

[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
Full-Text:
معرفي يک روش جديد خوشه‌يابي خودکار

نشریه مهندسی برق و مهندسی کامپیوتر ایران، ب- مهندسی کامپیوتر، سال 21، شماره 3، پاییز 1402  193

مقاله پژوهشی

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

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

 

 

1 

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

 

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

1-       مقدمه

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

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

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

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

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

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

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

img0        (1)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

img0        (2)

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

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

        داشته باشد.

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

img0        (3)

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

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

img0        (4)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

img0 

(الف)

img0 

(ب)

img0 

(ج)

img0 

(د)

img0 

(ﻫ)

img0 

(و)

img0 

(ز)

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-       نتایج

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

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

img0 

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

 

img0        (5)

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

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

img0        (6)

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

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

img0        (7)

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

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

img0        (8)

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

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

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

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

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

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

 

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

 

شماره

نام مدار

img0 

img0 

K

img0 پیشنهادی

img0 [26]

1

img0 

6

104

2

40

40

2

img0 

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

img0 

20

5861

3

2262

2028

7

img0 

15

220

4

144

101

8

50Hwb

56

6430

4

1272

1301

9

100Hwb

107

6430

4

2014

2513

10

img0 

5

5

2

4

6

11

img0 

7

49

4

34

30

12

img0 

8

49

2

8

12

13

img0 

13

104

3

16

22

14

247 Parity

17

16

3

6

4

15

img0 

49

200

3

6

9

 

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

 

 

روش پیشنهادی

روش [26]

شماره

img0 

img0 

img0 

img0 

img0 

img0 

img0 

img0 

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 محقق پسا دکترا در زمینه رمزنگاری کوانتومی به طور مشترک در دانشگاه ملی سنگاپور و دانشگاه تکتنولوژی و طراحی سنگاپور بوده است. دکتر هوشمند در حال حاضر استادیار گروه مهندسی کامپیوتر دانشگاه آزاد اسلامی مشهد است. علایق پژوهشی فعلی نام­برده شامل نظریه اطلاعات و محاسبات کوانتومی، سیستم‌های چندعاملی، محاسبات تکاملی و داده‌کاوی است.

 

 

 

 


Related articles

The rights to this website are owned by the Raimag Press Management System.
Copyright © 2017-2024

Home| Login| About Rimag| Contact Us|
[فارسی] [العربية] [fa] [ar]