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