رقم المقالة : 1400092232656 زيارة : 4086 الصفحة: 207 - 216

نوع المخطوط: المحکّمة

سنتز منطقی چندهدفه مدارهای کوانتومی

الموضوعات :

آرزو رجايي ¹ (دانشگاه آزاد اسلامي واحد مشهد،گروه مهندسی کامپیوتر)
محبوبه هوشمند ² ( دانشگاه آزاد اسلامي واحد مشهد،گروه مهندسی کامپیوتر)
سيدعابد حسيني ³ (دانشگاه آزاد اسلامی واحد مشهد،گروه مهندسی برق)

تاريخ الإرسال : 09 الإثنين , جمادى الأولى, 1443 تاريخ التأكيد : 17 الإثنين , رمضان, 1443 تاريخ الإصدار : 08 الأربعاء , ربيع الثاني, 1444

الکلمات المفتاحية: محاسبات کوانتومی, مدل مداری کوانتومی, سنتز منطقی, بهینه‌سازی چندهدفه, برنامه‌ریزی پویا,

ملخص المقالة :

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

المصادر:

[1] G. E. Moore, "Cramming more components onto integrated circuits," Electronics, vol. 38, no. 8, pp. 114-117, 19 Apr. 1965.
[2] C. P. Williams, Explorations in Quantum Computing, Springer Verlog, Feb. 2011.
[3] M. Nielsen and I. L. Chuang, Quantum Computation and Quantum Information, 10th Anniversary Edition, Cambridge University Press, Jan 31, 2011.
[4] M. Lukac, et al., "Evolutionary approach to quantum and reversible circuit synthesis," Artificial Intelligence Review, vol. 20, pp. 361-417, Jan. 2003.
[5] R. P. Feynman, "Simulating physics with computers," International J. of Theoretical Physics, vol. 21, no. 6-7, pp. 467-488, Jun. 1982.
[6] D. Deutsch, "Quantum theory, the church-turing principle and the universal quantum computer," in Proc. of the Royal Society London A, vol. 400, no. 1818, pp. 97-117, Jun. 1985.
[7] P. W. Shor, "Algorithms for quantum computation: discrete logarithms and factoring," in Proc. of the 35th Annual Symp. on Foundations of Computer Science, pp. 124-134, Santa Fe, NM, USA, 20-22 Nov. 1994.
[8] P. W. Shor, "Polynomial-time algorithms for prime factorization and discrete alogarithms on a quantum computer," SIAM J. on Computing, vol. 26, no. 5, pp. 1484-1509, Oct. 1997.
[9] L. K. Grover, "A fast quantum mechanical algorithm for database search," in Proc. of the 28th Annual ACM Symp. on the Theory of Computing, STOC’96, pp. 212-219, Philadelphia, PA, USA, 22-24 May 1996.
[10] G. B. Charles and H. Bennett, "Quantum cryptography: public key distribution and coin tossing," in Proc. of IEEE Int. Conf. on Computer System and Signal Processing, pp. 175-179, Bangalore, India, 10-12 Dec.. 1984.
[11] C. H. Bennett, et al., "Teleporting an unknown quantum state via dual classical and Einstein-Podolsky-Rosen channels," Physical Review Letters, vol. 70, no. 13, pp. 1895-1899, 29 Mar. 1993.
[12] C. H. Bennett and S. J. Wiesner, "Communication via one-and two-particle operators on Einstein-Podolsky-Rosen states," Physical Review Letters, vol. 69, no. 20, pp. 2881-2884, Nov. 1992.
[13] A. Barenco, et al., "Elementary gates for quantum computation," Physical Review A, vol. 52, no. 5, pp. 3457-3467, Nov. 1995.
[14] G. Cybenko, "Reducing quantum computations to elementary unitary operations," Computing in Science and Engineering, vol. 3, no. 2, pp. 27-32, Mar./Apr. 2001.
[15] V. V. Shende, I. L. Markov, and S. S. Bullock, "Minimal universal two-qubit quantum circuits," Physical Review A, vol. 69, pp. 062321-062329, Jun. 2004.
[16] M. Mottonen, J. J. Vartiainen, V. Bergholm, and M. M. Salomaa, "Quantum circuits for general multiqubit gates," Physical Review Letters, vol. 93, Article ID: 130502, Sept. 2004.
[17] V. Bergholm, J. J. Vartiainen, M. Mottonen, and M. M. Salomaa, "Quantum circuits with uniformly controlled one-qubit gates," Physical Review A, vol. 71, no. 5, pp. 23-30, May 2005.
[18] V. V. Shende, S. S. Bullock, and I. L. Markov, "Synthesis of quantum-logic circuits," IEEE Trans. on CAD, vol. 25, no. 6, pp. 1000-1010, Jun. 2006.
[19] M. Saeedi, M. Arabzadeh, M. Saheb Zamani, and M. Sedighi, "Block-based quantum-logic synthesis," Quantum Information and Computation J., vol. 11, no. 3, pp. 262-277, Mar. 2011.
[20] ك. مرجوعي، م. هوشمند، م. صاحب‌الزماني و م. صديقي، "سنتز منطقی مدارهاي كوانتومي با استفاده از روش مبتني بر بلوك بهبوديافته،" نشريه مهندسي برق و مهندسي كامپيوتر ايران، ب- مهندسي كامپيوتر، سال 14، شماره 3، صص. 239-248، پاييز 1395.
[21] M. Steane, "Error correcting codes in quantum theory," Phys. Rev. Lett., vol. 77, no. 5, pp. 793-797, Jul. 1996.
[22] D. Bacon, "Operator quantum error-correcting subsystems for self-correcting quantum memories," Phys. Rev. A, vol. 73, no. 1, pp. 012 34001-012 4013, Jan. 2006.
[23] D. Forney, M. Grassl, and S. Guha, "Convolutional and tail-biting quantum error-correcting codes," IEEE Trans. on Information Theory, vol. 53, no. 3, pp. 865-880, Mar. 2007.
[24] M. Houshmand, S. Hosseini-Khayat, and M. M. Wilde, "Minimalmemory, non-catastrophic, polynomial-depth quantum convolutional encoders," IEEE Trans. on Information Theory, vol. 59, no. 2, pp. 1198-1210, Feb. 2013.
[25] V. Kliuchnikov, D. Maslov, and M. Mosca, "Fast and effcient exact synthesis of single qubit unitaries generated by clifford and T gates," Quantum Information and Computation, vol. 13, no. 7-8, pp. 607-630, Jul. 2013.
[26] C. Lin and A. Chakrabarti, "FTQLS: fault-tolerant quantum logic synthesis," IEEE Trans. on VLSI Systems, vol. 22, no. 6, pp. 1350-1363, Jun. 2013.
[27] B. Giles and P. Selinger, "Exact synthesis of multiqubit Clifford+T circuits," Physical Review A, vol. 87, no. 3, Article ID: 032332, Mar. 2013.
[28] P. Niemann, R. Wille, and R. Drechsler, "Advanced exact synthesis of Clifford+T circuits," Quantum Information Processing, vol. 19, Article ID: 317, 23 pp., 27 Aug. 2020.
[29] D. Ruffinelli and B. Barán, "Linear nearest neighbor optimization in quantum circuits: a multiobjective perspective," Springer Science+Business Media, LLC, pp. 1-26, Mar. 2017.
[30] ب. رستمیان ملکی و م. محمدی، "طراحی چندهدفه مدارهای کوانتومی با استفاده از برنامه‌نویسی ژنتیک،" مجموعه مقالات نوزدهمین كنفرانس ملي سالانه انجمن كامپیوتر ايران، دانشكده مهندسي كامپیوترصص. 1177-1182، ، دانشگاه شهید بهشتي، تهران، 15-13 اسفند 1392.
[31] V. V. Shende, S. S. Bullock, and I. L. Markov, "Synthesis of quantum-logic circuits," IEEE Trans. on CAD, vol. 25, no. 6, pp. 1000-1010, Jun. 2006.
[32] A. U. Khalid, FPGA Emulation of Quantum Circuits, MS Thesis: McGill University, Mar. 2005.
[33] V. V. Shende, I. L. Markov, and S. S. Bullock, "Smaller two-qubit circuits for quantum communication and computation," in Proc. Design Automation and Test in Europe Conf. and Exhibition, pp. 980-985, Paris, France, 16-20 Feb. 2004.
[34] D. Maslov, G. W. Dueck, D. M. Miller, and C. Negrevergne, "Quantum circuit simplification and level compaction," IEEE Trans. on CAD, vol. 27, no. 3, pp. 436-444, Mar. 2008.
[35] T. H Cormen, et al., Introduction to Algorithms, MIT Press, Jun. 2009.

نص كامل:

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

مقاله پژوهشی

سنتز منطقی چندهدفه مدارهای کوانتومی

آرزو رجایی، محبوبه هوشمند و سید عابد حسینی

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

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

1- مقدمه

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

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

از جمله زمینه‌های مرتبط با محاسبات كوانتومی می‌توان به بحث سنتز منطقی مدارهای كوانتومی اشاره كرد. سنتز منطقی مدارهای کوانتومی به فرایند تبدیل یک گیت کوانتومی به یک سری گیت‌های پایه (با توجه
به كتابخانه گیت‌های جامع) اطلاق می‌شود. مسئله سنتز منطقی و بهینه‌سازی مدارهای کوانتومی یک مسئله سخت² است [4]. یكی از متداول‌ترین كتابخانه‌های گیت‌های جامع، كتابخانه گیت‌های پایه³ است كه از گیت CNOT و كلیه گیت‌های تك‌كیوبیتی تشكیل شده است. به منظور ارزیابی یك مدار كوانتومی، معیارهای هزینه مختلفی مانند تعداد گیت‌های CNOT و تك‌كیوبیتی، هزینه كوانتومی و عمق مدار وجود دارد.

ساختار ادامه این مطالعه از این ‌قرار است: در بخش 2، پیش‎زمینه‌های مورد نیاز در رابطه با محاسبات کوانتومی بیان شده‌اند. در بخش 3 به تعریف روش سنتز منطقی چندهدفه مدارهای کوانتومی و در بخش 4 به بررسی نتایج این روش پرداخته شده است. بخش 5 به جمع‌بندی می‌پردازد و پیشنهادهایی برای کارهای آتی دارد.

2- پیش‌زمینه

محاسبات کوانتومی حاصل ترکیب مکانیک کوانتومی و نظریه اطلاعات کلاسیک است و منجر به رخدادهای عجیب و قدرتمندی در حوزه کوانتوم می‌شود. در زیربخش 2-1، تاریخچه محاسبات کوانتومی، در زیربخش
2-2، کارهای قبلی مربوط به سنتز منطقی مدارهای کوانتومی و در زیربخش 2-3، اصول محاسبات کوانتومی مطرح می‌شود.

2-1 تاریخچه محاسبات کوانتومی

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

ایده دستگاه محاسباتی بر مبنای مکانیک کوانتومی برای اولین
بار در دهه 1970 و اوایل دهه 1980 توسط فیزیکدانان
و متخصصین کامپیوتر از قبیل چارلز بنت⁴، پل بنیوف⁵،
دیوید دویچ⁶ و ریچارد فاینمن⁷ مطرح شد. این ایده زمانی ظاهر شد که دانشمندان با محدودیت‌های اساسی محاسبات روبه‌رو گردیدند و متوجه شدند که اگر فناوری طبق قانون مور⁸ جلو رود، اندازه عناصر مداری که روی تراشه‌های سیلیکونی تعبیه می‎شوند عاقبت، بیشتر از چند اتم نخواهد بود. مشکلی که در اینجا پیش می‌آید این است که در اندازه اتمی، قوانین فیزیکی که بر رفتار اتم‌ها حاکم هستند، قوانین مکانیک کوانتومی هستند و نه قوانین مکانیک کلاسیک.

فاینمن [5]، جزو اولین افرادی بود که در سال 1982، مدلی انتزاعی پیشنهاد کرد که نشان می‌داد چگونه یک سیستم کوانتومی می‌تواند محاسبات را انجام دهد. سپس در سال 1985، دوستچ [6] دریافت که ایده فیمن می‌تواند عاقبت به یک کامپیوتر همه‌کاره منجر شود و یک مقاله منتشر کرد که به صورت نظری نشان می‌داد هر فرایند فیزیکی را می‌توان کاملاً با یک کامپیوتر کوانتومی مدل کرد. موفقیت اصلی توسط شور در سال 1994، وقتی او به کمک کامپیوترهای کوانتومی، روشی برای شکستن یک مسئله مهم در نظریه اعداد- تجزیه اعداد به عوامل اول [7] و [8] پیدا کرد، حاصل شد. او نشان داد که مجموعه‌ای از اعمال ریاضی که برای کامپیوتر کوانتومی طراحی شده‌اند، قابلیت تجزیه اعداد بزرگ را بر روی کامپیوترهای کوانتومی، بسیار سریع‌تر از کامپیوترهای کلاسیک دارند. با این موفقیت و همین طور کشف الگوریتم جستجوی گراور [9]، محاسبات کوانتومی از یک کنجکاوی دانشگاهی صرف، به یک علاقه جهانی تبدیل شد.

حوزه محاسبات کوانتومی مدرن، با کشف توزیع کلید کوانتومی⁹ [10]، توانایی ارسال یک بیت کوانتومی به کمک دو بیت کلاسیک و یک بیت درهم‌تنیدگی (مخابره از راه دور کوانتومی¹⁰ [11]) و توانایی ارسال دو بیت کلاسیک با ارسال یک بیت کوانتومی و یک بیت درهم‌تنیدگی (کدگذاری چگال¹¹ کوانتومی [12]) آغاز شد. سپس محققین، تلاش‌های عمیق‌تری برای ترکیب منابع مخابرات کلاسیک، مخابرات کوانتومی و درهم‌تنیدگی برای فرمول‌بندی پروتکل‌های جدید کوانتومی انجام دادند.

2-2 کارهای قبلی در مورد سنتز منطقی کوانتومی

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

- در دسته اول، با استفاده از ویژگی‌های ماتریسی مدار و گیت‌های کوانتومی و نیز تعریف گیت‌های خاص و روش‌های تجزیه آنها
با توجه به روش‌های تجزیه ریاضی، ماتریس مدار مورد نظر به دسته ماتریس‌های خاص که همان گیت‌های کوانتومی هستند، تجزیه می‌شود.

- در دسته دوم با استفاده از روش‌های جستجوی اکتشافی (الگوریتم‌های تکاملی)، اقدام به یافتن مداری متشکل از کتابخانه گیت‌های مورد نظر می‌شود.

در مقالات قبلی مربوط به سنتز منطقی، هدف اصلی عمدتاً کاهش تعداد گیت‌های CNOT است. در [13]، مرتبه تعداد گیت‌های CNOT مورد نیاز برای ساخت هر ماتریس بر روی کیوبیت برابر با گزارش شده است. با استفاده از تجزیه QR در [14] که بر مبنای استفاده از ماتریس‌های دوسطحی یکانی است، همین مرتبه به دست می‌آید. ماتریس‌های دوسطحی یکانی¹²، زیرمجموعه‌ای از ماتریس‌های یکانی هستند که به صورت غیر بدیهی فقط بر روی دو بردار عمل می‌کنند. سپس در [15]، بیشترین مقدار حد پایین مرزی¹³ برای تعداد گیت CNOT در سنتز منطقی مدارهای كوانتومی برابر می‌باشد. پس از آن با استفاده از روش سنتز منطقی مبتنی بر روش تجزیه شناخته‌شده CS¹⁴ [16] در جبر خطی با نام CSD مرتبه تعداد CNOT به رسید. در [17] با بهبود روش CSD، تعداد CNOTها به رسید و تعداد کمتری از گیت‌های تک‌کیوبیتی را تولید می‌کند. سپس [18] با تعریف سنتز منطقی مبتنی بر تجزیه CS با

عنوان ¹⁵QSD به تولید تعداد گیت CNOT رسید.

مقاله [19] روشی به نام ¹⁶BQD را طراحی کرده که تركیبی از دو روش CSD و QSD می‌باشد كه در نهایت منجر به ارائه روش جدیدی با خصوصیات جدید و تركیبی از خواص دو روش نام برده شده است. در نهایت، روش BQD در [20] بهبود یافته و منجر به ارائه روش جدیدی با نام¹⁷IBQD با خصوصیات جدید و نتایج بهتر شده است.

از آنجا که سیستم‌های كوانتومی بیشتر از محاسبات كلاسیك در معرض خطا هستند، مدارهای كوانتومی تحمل‌پذیر اشکال برای پیاده‌سازی عملی مورد نیازند. بسیاری از كدهای تصحیح اشکال كوانتومی [21] تا [24]، برای ممكن‌ساختن محاسبات تحمل‌پذیر اشکال ارائه شده‌اند كه
از گیت‌های كتابخانه حاوی گیت‌های كلیفورد و استفاده می‌کنند. برخی از پژوهش‌های اخیر در حوزه سنتز كوانتومی نیز به سنتز كوانتومی با هدف تحمل‌پذیری اشکال می‌پردازند. در [24] تا [26]، سنتز منطقی مدارهای كوانتومی عمدتاً با استفاده از كتابخانه گیت‌های كلیفورد و صورت می‌گیرد.

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

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

در [29] برای بهینه‌سازی هزینه معیار NNC از بهینه‌سازی چندهدفه استفاده شده که از الگوریتم تکاملی مبتنی بر NSGA-II بهره می‌گیرد. برای این منظور، دو هدف پیشنهاد گردیده است: به حداقل رساندن تعداد گیت‌های SWAP اضافی و تعداد فرعی‌های شبکه (اندازه شبکه). چون این دو هدف با هم تناقض دارند در نتیجه، یک الگوریتم تکاملی چندهدفه مبتنی بر NSGA-II برای حل این مشکل با در نظر گرفتن این دو هدف ایجاد شده است. در [30]، یک روش طراحی چندهدفه مدارهای کوانتومی مبتنی بر برنامه‌نویسی ژنتیک مطرح گردید. برای این منظور، سه هدف پیشنهاد شده است: هزینه مدار کوانتومی، هزینه نزدیک‌ترین همسایه و عمق مدار. از دیگر نوآوری‌های آن مقاله در نظر گرفتن هم‌ارزی فاز سراسری و همچنین استفاده از یک تابع برازش دومرحله‌ای را می‌توان ذکر کرد که در مرحله اول، صحت عملکرد مدار ارزیابی می‌شود. سپس معیارهای هزینه مدارهای کوانتومی، عمق و نزدیک‌ترین همسایه مجاور را مورد نظر قرار می‌دهد. نتایج اجرا بر روی مدارهای دو تا پنج کیوبیتی نشان دادند که روش مورد نظر قادر است در زمان کوتاه به یک جواب بهینه برای طراحی این مدارها بینجامد.

2-3 اصول محاسبات کوانتومی

2-3-1 کیوبیت‌ها

حالات کوانتومی را می‌توان بر حسب بردارها و یا با نماد معروف‌تر برا/کت²⁰ نمایش داد. کت‌ها همانند نمایشگر بردارهای ستونی هستند و عموماً برای توصیف حالات کوانتومی به کار می‌روند. حالت برا ، نمایشگر ترانهاده مزدوج²¹ است. حالات پایه و را می‌توان
به صورت و بیان کرد. هر ترکیبی از و را می‌توان به فرم نشان داد. نمایشگر ضرب داخلی²² دو بردار است. برای نمونه چون و عمود هستند، داریم . نماد نشان‌دهنده ضرب خارجی²³ دو بردار است.

یک کیوبیت²⁴، برداری یکه در فضای دوبعدی مختلط است که برای این فضا، بردارهای پایه مشخص که با نماد و نمایش داده می‌شوند، انتخاب شده‌اند. بردارهای پایه و به ترتیب همتای کوانتومی بیت‌های کلاسیک 0 و 1 می‌باشند. برخلاف بیت‌های کلاسیک، کیوبیت‌ها می‌توانند در هر برهم‎نهی²⁵ از و همانند قرار بگیرند که و اعداد مختلطی هستند که .

2-3-2 گیت‌های کوانتومی

اعمال کوانتومی را می‌توان با شبکه‌ای از گیت‌ها محقق کرد. هر گیت کوانتومی، یک تبدیل خطی است که با یک ماتریس یکانی²⁶ مؤثر بر
روی فضای کیوبیتی تعریف می‌گردد. ماتریس یکانی است اگر که ، ترانهاده مزدوج ماتریس می‌باشد. ماتریس یكانی عمومی كه بر روی كیوبیت عمل می‌كند، با نماد نمایش داده می‌شود.

از معروف‌ترین گیت‌های تک‌کیوبیتی، اعضای مجموعه پائولی هستند که از چهار عملگر زیر تشکیل شده‌اند

(1)

که تبدیل همانی²⁷، گیت چرخش بیت²⁸، گیت چرخش فاز²⁹ و ترکیبی از هر دو است.

از دیگر گیت‌های پرکاربرد تک‌کیوبیتی دیگر، گیت‌های دوران به دور محورهای ، و با زاویه هستند که به ترتیب با ماتریس‌های (2) نمایش داده می‌شوند

(2)

از جمله گیت‌های تک‌کیوبیتی پرکاربرد دیگر، گیت‌های هادامارد³⁰ (H)، گیت فاز³¹ (Phase) و گیت است. ماتریس‌های مربوط به این گیت‌ها در (3) آورده شده است.

(3)

شکل 1: نمايش مداري گيت CNOT.

گیت معکوس‌کننده- کنترلی ³²(CNOT)، یک گیت دوکیوبیتی است. کیوبیت اول در نقش کنترل و کیوبیت دوم در نقش هدف است. اگر کیوبیت کنترل، باشد، CNOT کیوبیت هدف را معکوس می‌کند و اگر کیوبیت کنترل، باشد، کیوبیت هدف بدون تغییر خارج می‌شود. به عبارت دیگر، خروجی دوم، XOR کیوبیت کنترل و هدف می‌باشد. نمایش مداری گیت CNOT به صورت (4) است

(4)

شکل 1، نمایش مداری گیت CNOT را نشان می‌دهد.

یک مالتی‌پلکسر کوانتومی [31]، کیوبیت هدف و کیوبیت انتخاب دارد و ترکیب مختلف خطوط انتخاب، مشخص می‌کنند که چه گیت کوانتومی متفاوتی به خطوط هدف اعمال شود. در حالتی كه تنها یك كیوبیت هدف (با نام ) داریم و گیت‌های كوانتومی اعمال‌شده در خط هدف ، باشند، مالتی‌پلكسر كوانتومی، مالتی‌پلكس‌شده نامیده می‌شود.

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

2-3-3 مدارهای کوانتومی

یک مدار کوانتومی، از مجموعه‌ای از سیم‌ها (کیوبیت‌ها) و یک توالی از گیت‌های کوانتومی تشکیل می‌گردد. محاسبات کوانتومی که با مدارهای کوانتومی مدل گردیده‌اند، در شکل 2 نشان داده شده‌اند. یک مدار کوانتومی همواره از چپ به راست ارزیابی می‌شود و بنابراین حرکت
از چپ به راست در یک مدار کوانتومی به معنای حرکت به جلو در زمان است.

2-3-4 مسئله بهینه‌سازی چندهدفه

یک مسأله بهینه‌سازی چندهدفه³³ را می‌توان به صورت رابطه زیر فرمول‌بندی کرد

(5)

که در آن برداری از متغیر و فضای تصمیم‌گیری می‌باشد. هر مؤلفه از ، یک تابع هدف³⁴ است و برداری از محدودیت³⁵

شکل 2: محاسبات کوانتومي که با مدارهاي کوانتومي مدل شده است [32].

می‌باشد که یک ناحیه ممکن³⁶ را تعریف می‌کند. هر نقطه از ، یک جواب ممکن³⁷ است.

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

2-3-5 سنتزهای منطقی CSD و QSD

روش‌های سنتز منطقی QSD و CSD مبتنی بر تجزیه CS هستند. روش سنتز منطقی CSD یك روش بازگشتی است كه به صورت بازگشتی بر روی گیت‌های به طور یكنواخت كنترلی چندكیوبیتی اعمال می‌شود. در نهایت، حاصل تجزیه گیت كوانتومی دلخواه كیوبیتی به صورت مداری با به طور یكنواخت كنترلی تك‌كیوبیتی و یك گیت قطری است. سپس این نوع گیت‌ها به گیت‌های CNOT و تك‌كیوبیتی تجزیه می‌شوند.

از دیگر روش‌های سنتز منطقی بازگشتی، روش سنتز منطقی QSD است. این روش بر خلاف روش CSD در اولین گام بازگشتی، یك گیت كوانتومی دلخواه كیوبیتی را به چهار گیت كوانتومی کیوبیتی و سه گیت مالتی‌پلكس‌شده، تجزیه می‌كند. سپس تجزیه QSD به طور بازگشتی بر روی چهار گیت كوانتومی کیوبیتی ادامه می‌یابد تا نهایتاً گیت‌های دو كیوبیتی حاصل شوند. سپس هر گیت دو كیوبیتی توسط مدار بهینه به دست آمده در [33] جایگزین می‌گردد.

[1] این مقاله در تاریخ 22 آذر ماه 1400 دریافت و در تاریخ 8 اسفند ماه 1400 بازنگری شد.

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

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

سید عابد حسینی، گروه مهندسی برق، واحد مشهد، دانشگاه آزاد اسلامی، مشهد، ایران، (email: hosseyni@mshdiau.ac.ir).

[2] . NP-Hard Problem

[3] . Basic Gate Library

[4] . Charles H. Benet

[5] . Paul A. Benioff

[6] . David Deustch

[7] . Richard P. Feynman

[8] . Moore's Law

[9] . Quantum Key Distribution

[10] . Quantum Teleportation

[11] . Dense Coding

[12] . Two-Level Unitary Matrices

[13] . Highest Lower Bound

[14] . Cosine-Sine Decomposition

[15] . Quantum Shannon Decomposition

[16] . Block-Based Quantum Decomposition

[17] . Improved-BQD

[18] . Denominator Exponent

[19] . Quantum Multiple-Valued Decision Diagram

[20] . Bra/Ket

[21] . Transpose Conjugate

[22] . Inner Product

[23] . Outer Product

[24] . Qubit

[25] . Superposition

[26] . Unitary

[27] . Identity

[28] . Bit Flip

[29] . Phase Flip

[30] . Hadamard Gate

[31] . Phase Rotation

[32] . Controlled-NOT

[33] . Multi-Objective Optimization Problem

[34] . Object Function

[35] . Restriction

[36] . Feasible Region

[37] . Feasible Solution

[38] . Optimization Variables

شکل 3: سنتز منطقی ماتریس یکانی نمونه .

2-3-6 معیارهای ارزیابی مدار کوانتومی

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

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

- عمق مدار: گیت‌های پایه‌ای که در یک مدار کوانتومی می‌توانند با هم اجرا شوند به عنوان یک سطح منطقی¹ در نظر گرفته می‌شوند [34]. تعداد سطوح منطقی یک مدار، عمق منطقی² مدار نامیده می‌شود. عمق یک مدار کوانتومی (نشان داده شده با )، می‌تواند از (6) به دست آید که در آن تعداد کل گیت‌ها و تعداد گیت‌هایی را که در مدار موازی هستند نشان می‌دهد

(6)

3- روش پیشنهادی

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

3-1 سنتز منطقی چندهدفه مدارهای کوانتومی

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

می‌توان مسئله سنتز منطقی این ماتریس یکانی به کتابخانه پایه را به صورت یک مسئله بهینه‌سازی مقید چندهدفه مدل‌سازی کرد

(7)

که در آن مجموعه‌ای از توابع هدف است که به شرح (8) است

(8)

هدف این مسئله، بهینه‌سازی 3 معیار ارزیابی عمق مدار⁴، تعداد کل گیت‌ها و تعداد گیت‌های CNOT است.

در روش پیشنهادی، فضای جوابی از ترکیب‌های مختلف روش‌های تجزیه QSD و CSD ایجاد می‌شود. فضای جواب ایجادشده، یک فضا با اندازه نمایی بسیار بزرگ است. سپس با استفاده از یک رهیافت پایین به بالا از روش حل برنامه‌ریزی پویای چندهدفه (MODP)، روشی ارائه می‌شود تا تنها بخشی از کل فضای جواب، برای یافتن مدارها با هزینه‌های بهینه پرتو جستجو شوند. این روش، ⁵MOQLS خوانده می‌شود.

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

روش پیشنهادی که برای ساختن فضای جواب، در آن از ترکیب دو روش QSD و CSD استفاده می‌گردد، ⁷SSG خوانده می‌شود. در این روش، ماتریس می‌تواند با روش‌های QSD و CSD تجزیه شود. اگر باشد، این ماتریس می‌تواند با روش CSD سنتز منطقی گردد. همچنین می‌تواند یک گام با روش سنتز منطقی بازگشتی QSD تجزیه شود که در این صورت، سه گیت مالتی‌پلکس‌شده روی کیوبیت و چهار ماتریس تولید می‌شود. روش SSG به طور بازگشتی بر روی هر یک از ماتریس‌های اجرا می‌گردد.

1. if

2. if

3. return

4. elseif

5. return

6. if

7. if

8. return

9. elseif

10. return

11.

12.

13.

14.

15. if

16. return

$img0$

17: return

شکل 4: الگوریتم بازگشتی پیشنهادی سنتز منطقی.

ماتریس‌های یکانی تولیدگردیده به دو کلاس ابتدایی و غیر ابتدایی به روشی که در ادامه توضیح داده شده است، افراز می‌شوند. اگر خود ماتریس

یک ماتریس ابتدایی باشد (در اولین بار فراخوانی این روش، ماتریس ابتدایی است)، به سمت راست‌ترین ماتریس ، ماتریس ابتدایی و به بقیه ماتریس‌ها، ماتریس‌های غیر ابتدایی گفته می‌شود. سه گیت مالتی‌پلکس‌شده روی کیوبیت نیز به کتابخانه ابتدایی تجزیه می‌شوند.

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

تعداد حالت‌های کلی فضای جواب تولیدشده توسط روش SSG از رابطه بازگشتی (9) به دست می‌آید

(9)

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

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

اندیس که تابعی از است و از صفر تا تغییر می‌کند، به صورت (10) محاسبه می‌شود. علی‌رغم آن که این اندیس تابعی از است، به علت ساده‌نوشتن، معیار به صراحت در آن ذکر نمی‌شود

(10)

که به ترتیب حاوی اندیس چهار ماتریس از سمت چپ به سمت راست مدار هستند و خود از رابطه بازگشتی (10) به دست می‌آیند. در واقع ، عددی است که از تبدیل عدد به مبنای 10 حاصل می‌شود. اگر داده‌شده با روش QSD سنتز منطقی شود، اندیس صفر می‌گیرد. اگر این ماتریس یکانی با روش CSD سنتز منطقی شود، اندیس آن به صورت در نظر گرفته می‌شود. در غیر این صورت، یک مرحله تجزیه بازگشتی QSD اعمال شده و 3 گیت مالتی‌پلکس‌شده روی کیوبیت و چهار ماتریس تولید می‌شود و اندیس این مدار با استفاده از رابطه بازگشتی (3) به دست می‌آید.

مداری که در روش SSG برای سنتز منطقی ماتریس‌های غیر ابتدایی بر روی کیوبیت تولید می‌شود و اندیسی برابر با دارد، خوانده می‌شود.

به منظور مشخص‌کردن نحوه تجزیه یک مدار مشخص در فضای جواب این روش، اندیس آن و تعداد کیوبیت‌هایی که آن مدار بر آن اثر می‌کند ، باید داده شوند و الگوریتم بازگشتی شکل 4 مورد استفاده قرار می‌گیرد. این تابع، یک ورودی به نام نیز دارد که ابتدایی یا غیر ابتدایی بودن ماتریس فراخواننده این الگوریتم را که قرار است تجزیه شود، نشان می‌دهد. قابل ذکر است که فرض می‌شود مقادیر به ازای های مختلف از قبل در حافظه ذخیره شده‌اند. همچنین دو تابع و به ترتیب خارج قسمت و باقیمانده تقسیم صحیح عدد بر را برمی‌گردانند.

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

در اولین بار فراخوانی تابع به منظور تجزیه یک ماتریس کیوبیتی، است. اگر ماتریس متناظر در فراخوانی این الگوریتم، خود ابتدایی باشد و یک گام با روش سنتز منطقی بازگشتی QSD تجزیه شود، آن گاه سمت راست‌ترین ماتریس تولیدشده توسط آن ابتدایی است، یعنی آن برابر با یک خواهد بود. برای مثال فرض کنید که و باشد. با استفاده از رابطه بازگشتی (9)، مقادیر ، و محاسبه گردیده و مورد استفاده قرار خواهند گرفت. تابع ارائه‌شده در شکل 4، شرط‌های داخل خطوط 1 تا 10 را چک کرده و هیچ کدام ارضا نمی‌شوند. سپس در خطوط 11 تا 14، ، ، و به ترتیب به صورت 16، 9، 16 و 0 محاسبه می‌شوند. روند بازگشتی فوق با ورودی‌های (3,0,0)، (3,16,0)، (3,9,0) و (3,16,1) دوباره فراخوانی می‌شود. نهایتاً با به انتها رسیدن روند بازگشتی فوق، تجزیه این مدار به شکل محاسبه خواهد شد. همچنین برای محاسبات هزینه که در ادامه آمده است، احتیاج به مشخص‌کردن نوع ماتریس‌های غیر ابتدایی در مجموعه جواب نیز است. این نوع با استفاده از رابطه بازگشتی (11) به دست می‌آید

(11)

اگر باشد (یعنی در سنتز منطقی یک مرحله QSD اعمال شده باشد)، سپس نوع ماتریس از روی ، ، یعنی اندیس سمت راست‌ترین ماتریس یکانی تولیدشده پس از اعمال یک مرحله تجزیه QSD به دست می‌آید و سپس (11) به طور بازگشتی با و ادامه می‌یابد تا به و به 0 یا برسد که در این حالت نوع این مدار به صورت 1 یا که به ترتیب به منزله تجزیه ماتریس ابتدایی با یا است، محاسبه می‌شود.

3-2 ارزیابی هزینه

به منظور بررسی ارزیابی هزینه، حد بالای سه معیار تعداد CNOT، عمق مدار کوانتومی و تعداد کل گیت‌ها در میان جواب‌های تولیدشده در فضای جواب SSG مورد بررسی قرار می‌گیرند.

3-2-1 تعداد CNOT

رابطه بازگشتی (12) تعداد گیت‌های CNOT را که روش پیشنهادی برای یک مدار تولید می‌کند، نشان می‌دهد

(12)

که در آن ، ، و مشابه با حالت قبل هستند. لازم به ذکر است که عبارت در (12)، تعداد گیت‌های CNOT مربوط به کوانتوم مالتی‌پلکسرهای میانی را نشان می‌دهد. رابطه بازگشتی (13)، تعداد گیت‌های CNOT تولیدشده در یک مدار را حساب می‌کند

(13)

3-2-2 هزینه کل گیت‌ها

برای محاسبه تعداد کل گیت‌های یک مدار کوانتومی، ابتدا تعداد گیت‌های تک‌کیوبیتی محاسبه ‌می‌شود. رابطه بازگشتی (14) به منظور ارزیابی حداکثر تعداد گیت‌های تک‌کیوبیتی که این روش برای هر مدار تولید می‌کند، استفاده می‌شود

(14)

اگر ماتریس داده‌شده با روش تجزیه شود، آن گاه تعداد گیت‌های تک‌کیوبیتی تولیدشده در آن، است. در غیر این صورت، اگر در (10) باشد (یعنی یک مرحله روش سنتز QSD اعمال شده باشد)، آن گاه چهار ماتریس و سه گیت مالتی‌پلکس‌شده تولید می‌شوند. تعداد گیت‌های تک‌کیوبیتی در ماتریس‌های غیر ابتدایی و ابتدایی به ترتیب با ، و نشان داده می‌شوند. ، ، و به ترتیب اندیس چهار ماتریس از سمت چپ به سمت راست مدار هستند و با استفاده از دستورهای 11 تا 14 از الگوریتم شکل 4 به دست می‌آیند. در نتیجه، تعداد کلی گیت‌های تک‌کیوبیتی با جمع‌کردن گیت‌های تک‌کیوبیتی در این چهار ماتریس تولیدشده به علاوه تعداد گیت‌های تک‌کیوبیتی در گیت‌های مالتی‌پلکس‌شده به دست می‌آید. تعداد گیت‌های تک‌کیوبیتی در گیت‌های مالتی‌پلکس‌شده برابر است.

رابطه بازگشتی (15)، تعداد گیت‌های تولیدشده در یک مدار را حساب می‌کند

(15)

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

رابطه (16) مجموع کلی گیت‌های تولیدشده به این روش را که از جمع (12) با (14) به دست آمده است، نشان می‌دهد

(16)

رابطه بازگشتی (17)، را حساب می‌کند

(17)

3-2-3 عمق مدار

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

(18)

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

رابطه بازگشتی (19) عمق مربوط به یک مدار را حساب می‌کند

جدول 1: مقایسه بین و به ازای .

5	4	3	2
	83522	17	2
	5266	9	2

(19)

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

3-2-4 تحلیل اندازه فضای جواب

همان طور که گفته شد، روش SSG به تعداد نمایی بسیار بزرگی از حالات مختلف برای تجزیه می‌انجامد. قابل توجه است که در فرمول‌های بازگشتی ارائه‌شده (روابط (12)، (16) و (18))، هزینه از جمع چهار هزینه محاسبه می‌شود. با استفاده از جابه‌جاپذیری جمع، مشخص است که تعداد زیادی از این حالت‌ها به یک هزینه یکسان کوانتومی می‌انجامند و تنها یکی از آن ترکیب‌ها می‌تواند مورد بررسی قرار گیرد. به طور خاص‌تر، حداکثر تعداد حالت‌های با هزینه مختلف کوانتومی با رابطه بازگشتی (20) محاسبه می‌شود

(20)

برای محاسبه این امر به بیان دیگر، مسأله را به فرم در نظر بگیرید و فرض کنید که ، و هر کدام مقدار متمایز
و نیز مقدار متمایز دیگر می‌تواند داشته باشد. در ادامه محاسبه می‌کنیم که حداکثر چند مقدار متمایز می‌تواند داشته باشد. تعریف می‌کنیم و مشخص است که . تعداد حالات مختلف را در نظر می‌گیریم. به سادگی می‌توان بررسی کرد که تعداد حالات مختلف (یعنی ) برابر خواهد بود با . تعداد حالات مختلف نیز می‌تواند به 3 حالت زیر افراز شود:

1) ، و هر سه برابر هستند. در این صورت تعداد حالت‌ها برابر با خواهد بود.

2) ، و هر سه متمایز هستند. در این صورت تعداد حالت‌ها برابر با جایگشت 3 از یعنی خواهد بود.

3) دقیقاً دو تا از مقادیر ، و برابر و یکی متمایز است. در این صورت تعداد حالت‌ها برابر با جایگشت 2 از یعنی خواهد بود.

با این توضیحات، به صورت (21) محاسبه می‌شود

(21)

قابل ذکر است که در محاسبه تعداد حالات مختلف فضای جواب (یعنی )، و برابر با است. با اضافه‌کردن یک حالت بیشتر به علت روش سنتز CSD، این تعداد به صورت (20) محاسبه
می‌شود. جدول 1، مقایسه بین تعداد حالات کل و را به ازای

2: if

3: then return

6: for to

8: for all

9: if has Pareto-optimal costs //if is not dominated

by all

10: then

11:

12: if has Pareto-optimal costs //if is not dominated

by all

13: then

14:

15:

16:

17: return

شکل 5: الگوریتم پیشنهادی MOQLS.

نشان می‌دهد. قابل ذکر است که در مورد مدارهای تولیدشده توسط روش SSG که هزینه یکسان دارند، مدارهایی با کوچک‌ترین اندیس ممکن در نظر گرفته می‌شوند.

3-3 الگوریتم MOQLS

الگوریتم MOQLS به منظور تولید مدارات با بهترین جواب‌ها
در فضای جواب ایجادشده با روش تولید فضای جواب SSG (جواب‌های

با هزینه‌های بهینه پرتو) روی کیوبیت، با استفاده از یک رهیافت مبتنی بر برنامه‌ریزی پویا، به صورت پایین به بالا با شروع از دو کیوبیت، جواب‌های بهینه پرتو را تولید می‌کند تا به مورد نظر برسد (شکل 5).

قضیه 1: الگوریتم MOQLS تمام مدارهای کوانتومی با هزینه‌های بهینه پرتوی سنتز منطقی چندهدفه را در فضای جواب تشکیل‌شده با روش SSG تولید می‌کند.

اثبات: به سادگی می‌توان دید که به ازای ، مدار (که روش تجزیه آن QSD است) هزینه بهینه پرتو دارد و لذا در مجموعه جواب تولیدشده توسط روش MOQLS قرار می‌گیرد. حال مدارهای با هزینه‌های بهینه پرتو روی کیوبیت ، یعنی و یک عضو دلخواه از این مجموعه را با نام در نظر بگیرید. اگر باشد، یعنی این مدار با روش CSD تجزیه شده است، آن گاه این مدار هزینه‌های بهینه پرتو دارد، لذا در این مجموعه قرار داده شده است. اگر باشد، اثبات با برهان خلف انجام می‌گیرد. فرض کنید در پایه به صورت نوشته شود و حداقل یک رقم مانند در این عدد وجود داشته باشد که هزینه‌های غیر بهینه پرتو دارد. در نتیجه حداقل یک مدار وجود دارد که حداقل یکی از هزینه‌های آن مانند ، کوچک‌تر از هزینه متناظر در است و هزینه‌های دیگر آن نیز از هزینه متناظر در کوچک‌تر یا مساوی است. اگر این مدار به جای در نظر گرفته شود، به مدار دیگر کیوبیتی مانند می‌انجامد که هزینه آن از هزینه مربوط به کوچک‌تر و هزینه‌های دیگر آن نیز از هزینه‌های کوچک‌تر

جدول 2: مدارهای کوانتومی با هزینه‌های بهینه پرتو تولیدشده با روش سنتز MOQLS
در فضای جواب ایجادشده توسط روش SSG برای .

تجزیه	تعداد CNOT	تعداد کل گیت‌ها	عمق
	3	10	7

جدول 3: مدارهای کوانتومی با هزینه‌های بهینه پرتو تولیدشده با روش سنتز MOQLS
در فضای جواب ایجادشده توسط روش SSG برای .

تجزیه	تعداد CNOT	تعداد کل گیت‌ها	عمق
	20	55	41
	26	58	51

جدول 4: مدارهای کوانتومی با هزینه‌های بهینه پرتو تولیدشده با روش سنتز MOQLS
در فضای جواب ایجادشده توسط روش SSG برای .

تجزیه	تعداد CNOT	تعداد کل گیت‌ها	عمق
	100	259	201
	106	262	211
	112	265	221
	118	268	231
	124	271	241
	118	249	234

[1] . Logical Level

[2] . Logical Depth

[3] . Multi-Objective Logic Synthesis

[4] . Depth of Circuit

[5] . Multi-Objective Quantum Logic Synthesis

[6] . Muli-Objective Dynamic Programming

[7] . Solution Space Generator

جدول 5: مدارهای کوانتومی با هزینه‌های بهینه پرتو تولیدشده با روش سنتز MOQLS در فضای جواب ایجادشده توسط روش SSG برای .

تجزیه	تعداد CNOT	تعداد کل گیت‌ها	عمق
	444	1123	889
	450	1126	899
	456	1129	909
	462	1113	922
	468	1116	932
	474	1119	942
	480	1103	955
	486	1109	965
	492	1109	975
	498	1093	988
	504	1096	998
	510	1099	1008
	516	1102	1018
	522	1105	1028
	516	1083	1021
	494	1016	985

یا مساوی است. لذا مدار بر مدار غالب است که با بهینه پرتو بودن در تناقض می‌باشد.

4- نتایج

جداول 2 تا 5 مدارهای کوانتومی با هزینه‌های بهینه پرتو تولیدگردیده را توسط روش سنتز MOQLS در فضای جواب ایجادشده توسط روش

SSG برای به همراه تجزیه‌های مربوط نشان می‌دهند. این جداول بیان می‌کنند که با استفاده از یک رهیافت پایین به بالای روش برنامه‌ریزی پویای چندهدفه، چگونه این مسأله می‌تواند حل شود. روش ارائه‌شده فضای جواب بزرگ‌تری را نسبت به تمام روش‌های CSD [17]، QSD [18]، BQD [19] و IBQD [20] جستجو می‌کند. در واقع این روش، تمام حالات مختلف ترکیب این روش‌ها را بررسی می‌کند و تمام روش‌های ذکرشده، حالت‌های خاصی از MOQLS هستند. همچنین این روش، حالاتی را تولید می‌کند که در هیچ یک از روش‌های ذکرشده قادر به تولید نیست. روش MOQLS برای سنتز منطقی ماتریس‌های یکانی عمومی، بهترین جواب‌ها در فضای جواب تولیدشده (نقاط بهینه پرتو) را ارائه کرده است. هر یک از این جواب‌ها می‌توانند در تکنولوژی‌های مختلف کوانتومی از اهمیت‌های مختلفی برخوردار باشند. برای مثال اگر در یک تکنولوژی، عمق از اهمیت بیشتری برخوردار باشد (مثلاً تکنولوژی تله‌یونی)، روش QSD به بهترین عمق کوانتومی می‌انجامد.

5- جمع‌بندی و پیشنهادهایی برای کارهای آتی

در این مقاله، یك روش سنتز منطقی چندهدفه مدارهای كوانتومی با هدف بهبود معیارهای ارزیابی مدار (تعداد CNOT، تعداد کل گیت‌ها و عمق مدار) معرفی شد که مبتنی بر ترکیبی از دو روش سنتز منطقی CSD و QSD در مدل محاسباتی مداری در جهت بهبود معیارهای ارزیابی مدار برای تولید مدار بهینه است. در روش پیشنهادی، فضای جوابی از ترکیب‌های مختلف این دو روش سنتز ایجاد می‌شود. فضای جواب ایجادشده، یک فضا با اندازه نمایی بسیار بزرگ است. سپس با استفاده از یک رهیافت پایین به بالا از روش حل برنامه‌ریزی پویای چندهدفه، روشی ارائه شد تا تنها بخشی از کل فضای جواب، برای یافتن مدارهای کوانتومی با هزینه‌های بهینه پرتو جستجو شوند و نشان داده شد که این روش می‌تواند نتایج موازنه‌ای از لحاظ این سه معیار ارزیابی
مدار نسبت به روش‌‌های قبلی ارائه‌شده تولید كند. هر یک از پاسخ‌های تولیدشده، با توجه به قیدهایی که تکنولوژی‌های ساخت کوانتومی دارند می‌توانند حائز اهمیت باشند. به عنوان یك كار آتی در این زمینه، یك روش سنتز چندهدفه آگاه از تحمل‌پذیری اشکال كه مبتنی بر روش سنتز پیشنهادی برای کتابخانه کلیفورد است، در حال بررسی می‌باشد.

مراجع

[1] G. E. Moore, "Cramming more components onto integrated circuits," Electronics, vol. 38, no. 8, pp. 114-117, 19 Apr. 1965.

[2] C. P. Williams, Explorations in Quantum Computing, Springer Verlog, Feb. 2011.

[3] M. Nielsen and I. L. Chuang, Quantum Computation and Quantum Information, 10th Anniversary Edition, Cambridge University Press, Jan 31, 2011.

[4] M. Lukac, et al., "Evolutionary approach to quantum and reversible circuit synthesis," Artificial Intelligence Review, vol. 20, pp. 361-417, Jan. 2003.

[5] R. P. Feynman, "Simulating physics with computers," International J. of Theoretical Physics, vol. 21, no. 6-7, pp. 467-488, Jun. 1982.

[6] D. Deutsch, "Quantum theory, the church-turing principle and the universal quantum computer," in Proc. of the Royal Society London A, vol. 400, no. 1818, pp. 97-117, Jun. 1985.

[7] P. W. Shor, "Algorithms for quantum computation: discrete logarithms and factoring," in Proc. of the 35th Annual Symp. on Foundations of Computer Science, pp. 124-134, Santa Fe, NM, USA, 20-22 Nov. 1994.

[8] P. W. Shor, "Polynomial-time algorithms for prime factorization
and discrete alogarithms on a quantum computer," SIAM J. on Computing, vol. 26, no. 5, pp. 1484-1509, Oct. 1997.

[9] L. K. Grover, "A fast quantum mechanical algorithm for database search," in Proc. of the 28th Annual ACM Symp. on the Theory of Computing, STOC’96, pp. 212-219, Philadelphia, PA, USA, 22-24 May 1996.

[10] G. B. Charles and H. Bennett, "Quantum cryptography: public key distribution and coin tossing," in Proc. of IEEE Int. Conf. on Computer System and Signal Processing, pp. 175-179, Bangalore, India, 10-12 Dec.. 1984.

[11] C. H. Bennett, et al., "Teleporting an unknown quantum state via dual classical and Einstein-Podolsky-Rosen channels," Physical Review Letters, vol. 70, no. 13, pp. 1895-1899, 29 Mar. 1993.

[12] C. H. Bennett and S. J. Wiesner, "Communication via one-and
two-particle operators on Einstein-Podolsky-Rosen states," Physical Review Letters, vol. 69, no. 20, pp. 2881-2884, Nov. 1992.

[13] A. Barenco, et al., "Elementary gates for quantum computation," Physical Review A, vol. 52, no. 5, pp. 3457-3467, Nov. 1995.

[14] G. Cybenko, "Reducing quantum computations to elementary unitary operations," Computing in Science and Engineering, vol. 3, no. 2, pp. 27-32, Mar./Apr. 2001.

[15] V. V. Shende, I. L. Markov, and S. S. Bullock, "Minimal universal two-qubit quantum circuits," Physical Review A, vol. 69, pp. 062321-062329, Jun. 2004.

[16] M. Mottonen, J. J. Vartiainen, V. Bergholm, and M. M. Salomaa, "Quantum circuits for general multiqubit gates," Physical Review Letters, vol. 93, Article ID: 130502, Sept. 2004.

[17] V. Bergholm, J. J. Vartiainen, M. Mottonen, and M. M. Salomaa, "Quantum circuits with uniformly controlled one-qubit gates," Physical Review A, vol. 71, no. 5, pp. 23-30, May 2005.

[18] V. V. Shende, S. S. Bullock, and I. L. Markov, "Synthesis of quantum-logic circuits," IEEE Trans. on CAD, vol. 25, no. 6, pp. 1000-1010, Jun. 2006.

[19] M. Saeedi, M. Arabzadeh, M. Saheb Zamani, and M. Sedighi, "Block-based quantum-logic synthesis," Quantum Information and Computation J., vol. 11, no. 3, pp. 262-277, Mar. 2011.

[20] ك. مرجوعي، م. هوشمند، م. صاحب‌الزماني و م. صديقي، "سنتز منطقی مدارهاي كوانتومي با استفاده از روش مبتني بر بلوك بهبوديافته،" نشريه مهندسي برق و مهندسي كامپيوتر ايران، ب- مهندسي كامپيوتر، سال 14، شماره 3، صص. 239-248، پاييز 1395.

[21] M. Steane, "Error correcting codes in quantum theory," Phys. Rev. Lett., vol. 77, no. 5, pp. 793-797, Jul. 1996.

[22] D. Bacon, "Operator quantum error-correcting subsystems for self-correcting quantum memories," Phys. Rev. A, vol. 73, no. 1, pp. 012 34001-012 4013, Jan. 2006.

[23] D. Forney, M. Grassl, and S. Guha, "Convolutional and tail-biting quantum error-correcting codes," IEEE Trans. on Information Theory, vol. 53, no. 3, pp. 865-880, Mar. 2007.

[24] M. Houshmand, S. Hosseini-Khayat, and M. M. Wilde, "Minimalmemory, non-catastrophic, polynomial-depth quantum convolutional encoders," IEEE Trans. on Information Theory,
vol. 59, no. 2, pp. 1198-1210, Feb. 2013.

[25] V. Kliuchnikov, D. Maslov, and M. Mosca, "Fast and effcient exact synthesis of single qubit unitaries generated by clifford and T gates," Quantum Information and Computation, vol. 13, no. 7-8, pp. 607-630, Jul. 2013.

[26] C. Lin and A. Chakrabarti, "FTQLS: fault-tolerant quantum logic synthesis," IEEE Trans. on VLSI Systems, vol. 22, no. 6, pp. 1350-1363, Jun. 2013.

[27] B. Giles and P. Selinger, "Exact synthesis of multiqubit Clifford+T circuits," Physical Review A, vol. 87, no. 3, Article ID: 032332, Mar. 2013.

[28] P. Niemann, R. Wille, and R. Drechsler, "Advanced exact synthesis of Clifford+T circuits," Quantum Information Processing, vol. 19, Article ID: 317, 23 pp., 27 Aug. 2020.

[29] D. Ruffinelli and B. Barán, "Linear nearest neighbor optimization in quantum circuits: a multiobjective perspective," Springer Science+Business Media, LLC, pp. 1-26, Mar. 2017.

[30] ب. رستمیان ملکی و م. محمدی، "طراحی چندهدفه مدارهای کوانتومی با استفاده از برنامه‌نویسی ژنتیک،" مجموعه مقالات نوزدهمین كنفرانس ملي سالانه انجمن كامپیوتر ايران، دانشكده مهندسي كامپیوترصص. 1177-1182، ، دانشگاه شهید بهشتي، تهران، 15-13 اسفند 1392.

[31] V. V. Shende, S. S. Bullock, and I. L. Markov, "Synthesis of quantum-logic circuits," IEEE Trans. on CAD, vol. 25, no. 6, pp. 1000-1010, Jun. 2006.

[32] A. U. Khalid, FPGA Emulation of Quantum Circuits, MS Thesis: McGill University, Mar. 2005.

[33] V. V. Shende, I. L. Markov, and S. S. Bullock, "Smaller two-qubit circuits for quantum communication and computation," in Proc. Design Automation and Test in Europe Conf. and Exhibition, pp. 980-985, Paris, France, 16-20 Feb. 2004.

[34] D. Maslov, G. W. Dueck, D. M. Miller, and C. Negrevergne, "Quantum circuit simplification and level compaction," IEEE Trans. on CAD, vol. 27, no. 3, pp. 436-444, Mar. 2008.

[35] T. H Cormen, et al., Introduction to Algorithms, MIT Press, Jun. 2009.

آرزو رجایی در سال 1386 مدرك كارشناسي مهندسي کامپیوتر گرایش نرمافزار خود را از دانشگاه فردوسی مشهد و در سال 1390 مدرك كارشناسي ارشد مهندسي کامپیوتر گرایش نرمافزار را از دانشگاه شیخ بهایی اصفهان دريافت نمود. از سال 1391 الي 1396 نامبرده به عنوان مدرس حق التدریس در دانشگاه علمی و کاربردی بهزیستی مشهد به كار مشغول بوده و پس از آن به دوره دكتراي مهندسي کامپیوتر گرایش نرمافزار در دانشگاه آزاد اسلامی مشهد وارد گرديد و تاکنون در همان دانشگاه مشغول به تحصیل میباشد. مهندس رجایی از سال 1395 تاکنون به عنوان مدرس فرهنگی در
هنرستانهای دولتی مشهد مشغول به فعالیت میباشد. زمينه‎هاي علمي مورد علاقه ایشان متنوع بوده و شامل موضوعاتي مانند ايده‎هاي نوین در محاسبات کوانتومی، طراحی وب و پایگاه دادهها مي‎باشد.

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

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

شارک

عنوان URL للمقالة

سنتز منطقی چندهدفه مدارهای کوانتومی

رایمگ

الروابط

المراكز ذات الصلة

دعامة

الصفحات الرسمية