Multi-Objective Logic Synthesis of Quantum Circuits
Subject Areas : electrical and computer engineering
Arezoo
Rajaei
1
(Mashhad Branch, Islamic Azad University)
Mahboobeh
Houshmand
2
(Mashhad Branch, Islamic Azad University, Mashhad, Iran)
Seyyed Abed
Hosseini
3
(Mashhad Branch, Islamic Azad University)
Keywords: Quantum computing, quantum circuit model, logic synthesis, multi-objective optimization, dynamic programming,
Abstract :
Quantum computing is a new method of information processing that is based on the concepts of quantum mechanics and leads to strange and powerful events in the quantum field. The logic synthesis of quantum circuits refers to the process of converting a given quantum gate into a set of gates that can be implemented in quantum technologies. The most famous logic synthesis methods are CSD and QSD. The main goal of this study is to present a multi-objective logical synthesis method combining the above two methods in the quantum circuit model with the aim of optimizing the evaluation criteria. In this proposed method, the solution space is created from different combinations of CSD and QSD decomposition methods. The created solution space is a space with a very large exponential size. Then, using a bottom-up approach of multi-objective dynamic programming, a method is presented to search only a part of the entire solution space to find circuits with the optimal Pareto costs. The obtained results show that this method creates a balance between the evaluation criteria and produces many optimal Pareto solutions that can be selected according to different quantum technologies.
[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.
نشریه مهندسی برق و مهندسی كامپیوتر ایران، ب- مهندسی کامپیوتر، سال 20، شماره 3، پاییز 1401 207
مقاله پژوهشی
سنتز منطقی چندهدفه مدارهای کوانتومی
آرزو رجایی، محبوبه هوشمند و سید عابد حسینی
چكیده: محاسبات کوانتومی، روش جدیدی از پردازش اطلاعات است که بر مبنای مفاهیم مکانیک کوانتومی بنا شده و منجر به رخدادهای عجیب و قدرتمندی در حوزه کوانتوم میشود. سنتز منطقی مدارهای كوانتومی به فرایند تبدیل یك گیت دادهشده كوانتومی به مجموعهای از گیتها با قابلیت پیادهسازی در تكنولوژیهای كوانتومی اطلاق میشود. از معروفترین روشهای سنتز منطقی CSD و QSD هستند. هدف اصلی این مقاله، ارائه یک روش سنتز منطقی چندهدفه ترکیبی از دو روش فوق در مدل مداری محاسباتی با هدف بهینهسازی معیارهای ارزیابی است. در این روش پیشنهادی، فضای جوابی از ترکیبهای مختلف روشهای تجزیه CSD و QSD ایجاد میشود. فضای جواب ایجادشده، یک فضا با اندازه نمایی بسیار بزرگ است. سپس با استفاده از یک رهیافت پایین به بالا از روش حل برنامهریزی پویای چندهدفه، روشی ارائه میشود تا تنها بخشی از کل فضای جواب، برای یافتن مدارهایی با هزینههای بهینه پرتو جستجو شوند. نتایج به دست آمده نشان میدهند که این روش، موازنهای بین معیارهای ارزیابی ایجاد میکند و پاسخهای بهینه پرتو متعددی تولید کرده که با توجه به تکنولوژیهای مختلف کوانتومی میتوانند انتخاب شوند.
کلیدواژه: محاسبات کوانتومی، مدل مداری کوانتومی، سنتز منطقی، بهینهسازی چندهدفه، برنامهریزی پویا.
1- مقدمه
در طول چند دهه گذشته با پیشرفت شگفتانگیز فناوری، روند کوچکسازی ترانزیستورها در ساخت تراشههای کامپیوتری پدیدار شده است، به گونهای که امروزه ریزپردازندهها دربرگیرنده بیش از صدها میلیون ترانزیستور هستند. قانون مور بیان میکند که در هر 18 ماه، تعداد ترانزیستورهای یک تراشه الکترونیکی دو برابر میشود [1]. پیروی از قانون مور سبب میشود که اندازه ترانزیستورها در نهایت به اندازه اتم باشد. با رسیدن به اندازه اتمی در تراشهها، نظریه ریاضیات حاکم بر علم کامپیوتر نوین نقض میشود. در چنین ابعادی قوانین کوانتومی بر ساخت تراشهها حاکم خواهد شد، نه قوانین موجود در طراحی و ساخت تراشههای امروزی. بدین منظور دانشمندان، نظریه جدیدی تحت عنوان محاسبات کوانتومی بیان نمودند که در مقیاس بسیار کوچک، قوانین مورد نظر، قوانین مربوط به مکانیک کوانتومی هستند [2].
محاسبات و فناوری اطلاعات کوانتومی، علم پردازش اطلاعات توسط سیستمهای مکانیک کوانتوم است. این عرصه از علم در حقیقت شامل سه علم نظریه اطلاعات، علوم کامپیوتر و فیزیک کوانتوم است [3]. دانشمندان انتظار دارند که کامپیوترهای کوانتومی بتوانند باعث تحولات چشمگیری در زمینههای مختلف مانند افزایش چشمگیر سرعت پردازش اطلاعات، انتقال امن دادهها، رفع محدودیتهای مدارهای مجتمع و کاهش مصرف انرژی شوند.
از جمله زمینههای مرتبط با محاسبات كوانتومی میتوان به بحث سنتز منطقی مدارهای كوانتومی اشاره كرد. سنتز منطقی مدارهای کوانتومی به فرایند تبدیل یک گیت کوانتومی به یک سری گیتهای پایه (با توجه
به كتابخانه گیتهای جامع) اطلاق میشود. مسئله سنتز منطقی و بهینهسازی مدارهای کوانتومی یک مسئله سخت2 است [4]. یكی از متداولترین كتابخانههای گیتهای جامع، كتابخانه گیتهای پایه3 است كه از گیت CNOT و كلیه گیتهای تككیوبیتی تشكیل شده است. به منظور ارزیابی یك مدار كوانتومی، معیارهای هزینه مختلفی مانند تعداد گیتهای CNOT و تككیوبیتی، هزینه كوانتومی و عمق مدار وجود دارد.
ساختار ادامه این مطالعه از این قرار است: در بخش 2، پیشزمینههای مورد نیاز در رابطه با محاسبات کوانتومی بیان شدهاند. در بخش 3 به تعریف روش سنتز منطقی چندهدفه مدارهای کوانتومی و در بخش 4 به بررسی نتایج این روش پرداخته شده است. بخش 5 به جمعبندی میپردازد و پیشنهادهایی برای کارهای آتی دارد.
2- پیشزمینه
محاسبات کوانتومی حاصل ترکیب مکانیک کوانتومی و نظریه اطلاعات کلاسیک است و منجر به رخدادهای عجیب و قدرتمندی در حوزه کوانتوم میشود. در زیربخش 2-1، تاریخچه محاسبات کوانتومی، در زیربخش
2-2، کارهای قبلی مربوط به سنتز منطقی مدارهای کوانتومی و در زیربخش 2-3، اصول محاسبات کوانتومی مطرح میشود.
2-1 تاریخچه محاسبات کوانتومی
محاسبات کوانتومی، شاخه جدیدی از پردازش اطلاعات بر مبنای اصول مکانیک کوانتومی است. هرچند هنوز کامپیوترهای کوانتومی کاملاً عملی ساخته نشدهاند، اما آینده کامپیوترهای کوانتومی بسیار روشن به نظر میرسد.
ایده دستگاه محاسباتی بر مبنای مکانیک کوانتومی برای اولین
بار در دهه 1970 و اوایل دهه 1980 توسط فیزیکدانان
و متخصصین کامپیوتر از قبیل چارلز بنت4، پل بنیوف5،
دیوید دویچ6 و ریچارد فاینمن7 مطرح شد. این ایده زمانی ظاهر شد که دانشمندان با محدودیتهای اساسی محاسبات روبهرو گردیدند و متوجه شدند که اگر فناوری طبق قانون مور8 جلو رود، اندازه عناصر مداری که روی تراشههای سیلیکونی تعبیه میشوند عاقبت، بیشتر از چند اتم نخواهد بود. مشکلی که در اینجا پیش میآید این است که در اندازه اتمی، قوانین فیزیکی که بر رفتار اتمها حاکم هستند، قوانین مکانیک کوانتومی هستند و نه قوانین مکانیک کلاسیک.
فاینمن [5]، جزو اولین افرادی بود که در سال 1982، مدلی انتزاعی پیشنهاد کرد که نشان میداد چگونه یک سیستم کوانتومی میتواند محاسبات را انجام دهد. سپس در سال 1985، دوستچ [6] دریافت که ایده فیمن میتواند عاقبت به یک کامپیوتر همهکاره منجر شود و یک مقاله منتشر کرد که به صورت نظری نشان میداد هر فرایند فیزیکی را میتوان کاملاً با یک کامپیوتر کوانتومی مدل کرد. موفقیت اصلی توسط شور در سال 1994، وقتی او به کمک کامپیوترهای کوانتومی، روشی برای شکستن یک مسئله مهم در نظریه اعداد- تجزیه اعداد به عوامل اول [7] و [8] پیدا کرد، حاصل شد. او نشان داد که مجموعهای از اعمال ریاضی که برای کامپیوتر کوانتومی طراحی شدهاند، قابلیت تجزیه اعداد بزرگ را بر روی کامپیوترهای کوانتومی، بسیار سریعتر از کامپیوترهای کلاسیک دارند. با این موفقیت و همین طور کشف الگوریتم جستجوی گراور [9]، محاسبات کوانتومی از یک کنجکاوی دانشگاهی صرف، به یک علاقه جهانی تبدیل شد.
حوزه محاسبات کوانتومی مدرن، با کشف توزیع کلید کوانتومی9 [10]، توانایی ارسال یک بیت کوانتومی به کمک دو بیت کلاسیک و یک بیت درهمتنیدگی (مخابره از راه دور کوانتومی10 [11]) و توانایی ارسال دو بیت کلاسیک با ارسال یک بیت کوانتومی و یک بیت درهمتنیدگی (کدگذاری چگال11 کوانتومی [12]) آغاز شد. سپس محققین، تلاشهای عمیقتری برای ترکیب منابع مخابرات کلاسیک، مخابرات کوانتومی و درهمتنیدگی برای فرمولبندی پروتکلهای جدید کوانتومی انجام دادند.
2-2 کارهای قبلی در مورد سنتز منطقی کوانتومی
فعالیتهای انجامشده در زمینه سنتز منطقی مدارهای کوانتومی را میتوان به دو دسته مبتنی بر تجزیه و مبتنی بر ترکیب تقسیم کرد که فعالیتهای مختلفی در هر بخش صورت گرفته است.
- در دسته اول، با استفاده از ویژگیهای ماتریسی مدار و گیتهای کوانتومی و نیز تعریف گیتهای خاص و روشهای تجزیه آنها
با توجه به روشهای تجزیه ریاضی، ماتریس مدار مورد نظر به دسته ماتریسهای خاص که همان گیتهای کوانتومی هستند، تجزیه میشود.
- در دسته دوم با استفاده از روشهای جستجوی اکتشافی (الگوریتمهای تکاملی)، اقدام به یافتن مداری متشکل از کتابخانه گیتهای مورد نظر میشود.
در مقالات قبلی مربوط به سنتز منطقی، هدف اصلی عمدتاً کاهش تعداد گیتهای CNOT است. در [13]، مرتبه تعداد گیتهای CNOT مورد نیاز برای ساخت هر ماتریس بر روی کیوبیت برابر با
گزارش شده است. با استفاده از تجزیه QR در [14] که بر مبنای استفاده از ماتریسهای دوسطحی یکانی است، همین مرتبه به دست میآید. ماتریسهای دوسطحی یکانی12، زیرمجموعهای از ماتریسهای یکانی هستند که به صورت غیر بدیهی فقط بر روی دو بردار عمل میکنند. سپس در [15]، بیشترین مقدار حد پایین مرزی13 برای تعداد گیت CNOT در سنتز منطقی مدارهای كوانتومی برابر
میباشد. پس از آن با استفاده از روش سنتز منطقی مبتنی بر روش تجزیه شناختهشده CS14 [16] در جبر خطی با نام CSD مرتبه تعداد CNOT به
رسید. در [17] با بهبود روش CSD، تعداد CNOTها به
رسید و تعداد کمتری از گیتهای تککیوبیتی را تولید میکند. سپس [18] با تعریف سنتز منطقی مبتنی بر تجزیه CS با
عنوان 15QSD به تولید تعداد گیت CNOT رسید.
مقاله [19] روشی به نام 16BQD را طراحی کرده که تركیبی از دو روش CSD و QSD میباشد كه در نهایت منجر به ارائه روش جدیدی با خصوصیات جدید و تركیبی از خواص دو روش نام برده شده است. در نهایت، روش BQD در [20] بهبود یافته و منجر به ارائه روش جدیدی با نام17IBQD با خصوصیات جدید و نتایج بهتر شده است.
از آنجا که سیستمهای كوانتومی بیشتر از محاسبات كلاسیك در معرض خطا هستند، مدارهای كوانتومی تحملپذیر اشکال برای پیادهسازی عملی مورد نیازند. بسیاری از كدهای تصحیح اشکال كوانتومی [21] تا [24]، برای ممكنساختن محاسبات تحملپذیر اشکال ارائه شدهاند كه
از گیتهای كتابخانه حاوی گیتهای كلیفورد و استفاده میکنند. برخی از پژوهشهای اخیر در حوزه سنتز كوانتومی نیز به سنتز كوانتومی با هدف تحملپذیری اشکال میپردازند. در [24] تا [26]، سنتز منطقی مدارهای كوانتومی عمدتاً با استفاده از كتابخانه گیتهای كلیفورد و
صورت میگیرد.
کتابخانه کلیفورد و که شامل گیتهای CNOT، هادامارد، فاز و
میباشد، یک کتابخانه تقریباً جهانی است. یکی از راهکارهایی که برای کاهش محدودیت این کتابخانه ارائه شده است، گسترش آن میباشد [26]، یعنی افزودن گیتهای جدید به کتابخانه. این عمل سبب میشود در صورت وجود این گیتها در مدار کوانتومی بدون خاصیت تحملپذیر اشکال، نیازی به سنتز آن نباشد. همین امر سبب بهبود هزینههای این سنتز خواهد شد. حتی با وجود گسترش کتابخانه، باز هم امکان تجزیه دقیق یک گیت دلخواه به گیتهای کلیفورد و
وجود ندارد.
در [27] از الگوریتمهای مبتنی بر ریاضی برای طراحی یک روش سنتز منطقی دقیق با توجه به کتابخانه کلیفورد و استفاده شده و همچنین با استفاده از کیوبیتهای کمکی برای عملگرهای کلیفورد و
، تعداد کل گیتهای ابتدایی این کتابخانه به کار رفته
میباشد (
مؤلفه مخرج18 است). مقاله [28]، روش سنتز دقیق پیشنهادشده در [27] را در سطح جهانی بهبود داده و از نمودار تصمیمگیری چندمقداری کوانتومی19 برای نمایش ماتریس به صورت کارا و از گیتهای کتابخانه كلیفورد و
استفاده کرده و هدف اصلی آن، تولید مدار با تعداد حداقل گیت
است.
در [29] برای بهینهسازی هزینه معیار NNC از بهینهسازی چندهدفه استفاده شده که از الگوریتم تکاملی مبتنی بر NSGA-II بهره میگیرد. برای این منظور، دو هدف پیشنهاد گردیده است: به حداقل رساندن تعداد گیتهای SWAP اضافی و تعداد فرعیهای شبکه (اندازه شبکه). چون این دو هدف با هم تناقض دارند در نتیجه، یک الگوریتم تکاملی چندهدفه مبتنی بر NSGA-II برای حل این مشکل با در نظر گرفتن این دو هدف ایجاد شده است. در [30]، یک روش طراحی چندهدفه مدارهای کوانتومی مبتنی بر برنامهنویسی ژنتیک مطرح گردید. برای این منظور، سه هدف پیشنهاد شده است: هزینه مدار کوانتومی، هزینه نزدیکترین همسایه و عمق مدار. از دیگر نوآوریهای آن مقاله در نظر گرفتن همارزی فاز سراسری و همچنین استفاده از یک تابع برازش دومرحلهای را میتوان ذکر کرد که در مرحله اول، صحت عملکرد مدار ارزیابی میشود. سپس معیارهای هزینه مدارهای کوانتومی، عمق و نزدیکترین همسایه مجاور را مورد نظر قرار میدهد. نتایج اجرا بر روی مدارهای دو تا پنج کیوبیتی نشان دادند که روش مورد نظر قادر است در زمان کوتاه به یک جواب بهینه برای طراحی این مدارها بینجامد.
2-3 اصول محاسبات کوانتومی
2-3-1 کیوبیتها
حالات کوانتومی را میتوان بر حسب بردارها و یا با نماد معروفتر برا/کت20 نمایش داد. کتها همانند نمایشگر بردارهای ستونی هستند و عموماً برای توصیف حالات کوانتومی به کار میروند. حالت برا
، نمایشگر ترانهاده مزدوج21
است. حالات پایه
و
را میتوان
به صورت و
بیان کرد. هر ترکیبی از
و
را میتوان به فرم
نشان داد.
نمایشگر ضرب داخلی22 دو بردار است. برای نمونه چون
و
عمود هستند، داریم
. نماد
نشاندهنده ضرب خارجی23 دو بردار است.
یک کیوبیت24، برداری یکه در فضای دوبعدی مختلط است که برای این فضا، بردارهای پایه مشخص که با نماد و
نمایش داده میشوند، انتخاب شدهاند. بردارهای پایه
و
به ترتیب همتای کوانتومی بیتهای کلاسیک 0 و 1 میباشند. برخلاف بیتهای کلاسیک، کیوبیتها میتوانند در هر برهمنهی25 از
و
همانند
قرار بگیرند که
و
اعداد مختلطی هستند که
.
2-3-2 گیتهای کوانتومی
اعمال کوانتومی را میتوان با شبکهای از گیتها محقق کرد. هر گیت کوانتومی، یک تبدیل خطی است که با یک ماتریس یکانی26 مؤثر بر
روی فضای کیوبیتی تعریف میگردد. ماتریس
یکانی است اگر
که
، ترانهاده مزدوج ماتریس
میباشد. ماتریس یكانی عمومی كه بر روی
كیوبیت عمل میكند، با نماد
نمایش داده میشود.
از معروفترین گیتهای تککیوبیتی، اعضای مجموعه پائولی هستند که از چهار عملگر زیر تشکیل شدهاند
(1)
که تبدیل همانی27،
گیت چرخش بیت28،
گیت چرخش فاز29 و
ترکیبی از هر دو است.
از دیگر گیتهای پرکاربرد تککیوبیتی دیگر، گیتهای دوران به دور محورهای ،
و
با زاویه
هستند که به ترتیب با ماتریسهای (2) نمایش داده میشوند
(2)
از جمله گیتهای تککیوبیتی پرکاربرد دیگر، گیتهای هادامارد30 (H)، گیت فاز31 (Phase) و گیت است. ماتریسهای مربوط به این گیتها در (3) آورده شده است.
(3)
شکل 1: نمايش مداري گيت CNOT.
گیت معکوسکننده- کنترلی 32(CNOT)، یک گیت دوکیوبیتی است. کیوبیت اول در نقش کنترل و کیوبیت دوم در نقش هدف است. اگر کیوبیت کنترل، باشد، CNOT کیوبیت هدف را معکوس میکند و اگر کیوبیت کنترل،
باشد، کیوبیت هدف بدون تغییر خارج میشود. به عبارت دیگر، خروجی دوم، XOR کیوبیت کنترل و هدف میباشد. نمایش مداری گیت CNOT به صورت (4) است
(4)
شکل 1، نمایش مداری گیت CNOT را نشان میدهد.
یک مالتیپلکسر کوانتومی [31]، کیوبیت هدف و
کیوبیت انتخاب دارد و
ترکیب مختلف خطوط انتخاب، مشخص میکنند که چه گیت کوانتومی متفاوتی به خطوط هدف اعمال شود. در حالتی كه تنها یك كیوبیت هدف (با نام
) داریم و گیتهای كوانتومی اعمالشده در خط هدف
،
باشند، مالتیپلكسر كوانتومی،
مالتیپلكسشده نامیده میشود.
یك ماتریس مربعی، قطری نامیده میشود چنانچه درایههای خارج از قطر اصلی آن صفر باشند. یك گیت قطری كه بر روی كیوبیت اعمال میگردد، یك ماتریس یكانی
قطری دارد و با نماد
نمایش داده میشود.
2-3-3 مدارهای کوانتومی
یک مدار کوانتومی، از مجموعهای از سیمها (کیوبیتها) و یک توالی از گیتهای کوانتومی تشکیل میگردد. محاسبات کوانتومی که با مدارهای کوانتومی مدل گردیدهاند، در شکل 2 نشان داده شدهاند. یک مدار کوانتومی همواره از چپ به راست ارزیابی میشود و بنابراین حرکت
از چپ به راست در یک مدار کوانتومی به معنای حرکت به جلو در زمان است.
2-3-4 مسئله بهینهسازی چندهدفه
یک مسأله بهینهسازی چندهدفه33 را میتوان به صورت رابطه زیر فرمولبندی کرد
(5)
که در آن برداری از
متغیر و
فضای تصمیمگیری میباشد. هر مؤلفه از
، یک تابع هدف34 است و
برداری از
محدودیت35
شکل 2: محاسبات کوانتومي که با مدارهاي کوانتومي مدل شده است [32].
میباشد که یک ناحیه ممکن36 را تعریف میکند. هر نقطه از
، یک جواب ممکن37 است.
طبق این تعریف، یک مسأله بهینهسازی مقید دارای مجموعهای از متغیرها است که به عنوان متغیرهای بهینهسازی38 شناخته میشوند. یک تابع
با نام تابع هدف بر روی متغیرهای بهینهسازی اعمال میشود و این تابع بایستی کمینه گردد. همچنین مجموعهای از قیدها میتوانند به شکل تساوی
یا نامساوی
یا
روی متغیرهای بهینهسازی اعمال شوند. مجموعههای
به ترتیب به عنوان دامنههای متغیرهای
هستند که میتوانند به عنوان قیدهای دامنهای (یا محدودیت) در مسأله بهینهسازی مقید بیان شوند. این نکته لازم است عنوان گردد که محدودیت را میتوان در برخی موارد به صورت قیدهای تساوی و یا نامساوی نیز بیان کرد. به عنوان مثال، محدودیت نامنفیبودن متغیر
را میتوان به صورت قید نامساوی
نوشت. در بهینهسازی چندهدفه، هدف بهینهسازی همزمان بیشتر از یک تابع هدف مختلف و گاه متضاد است. از روشهای حل بهینهسازی چندهدفه، پیداکردن مجموعه جواب بهینه پرتو است که در آن مجموعه جوابهای غیر غالب در تمام فضای جستجو ارائه میشود. یک جواب، غیر غالب خوانده میشود اگر مقدار هیچ یک از توابع هدف آن نتواند بدون خرابکردن برخی دیگر از توابع هدف بهتر شود.
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 تولیدشده است.
- هزینه کل گیتها: این معیار برابر با تعداد کل گیتهای تولیدشده در روش سنتز منطقی مدارهای کوانتومی است.
- عمق مدار: گیتهای پایهای که در یک مدار کوانتومی میتوانند با هم اجرا شوند به عنوان یک سطح منطقی1 در نظر گرفته میشوند [34]. تعداد سطوح منطقی یک مدار، عمق منطقی2 مدار نامیده میشود. عمق یک مدار کوانتومی (نشان داده شده با
)، میتواند از (6) به دست آید که در آن
تعداد کل گیتها و
تعداد گیتهایی را که در مدار
موازی هستند نشان میدهد
(6)
3- روش پیشنهادی
در این بخش، یک روش پیشنهادی برای سنتز منطقی چندهدفه با هدف بهبود معیارهای ارزیابی مطرح میشود.
3-1 سنتز منطقی چندهدفه مدارهای کوانتومی
به طور رسمی، مسئله سنتز منطقی چندهدفه3 در مدل مداری کوانتومی را با استفاده از کتابخانه پایه به صورتی که در ادامه میآید، مدلسازی میکنیم. برای مثال، شکل 3 را یک مدار نمونه حاصل از سنتز منطقی ماتریس یکانی روی
کیوبیت متشکل از گیتهای
در نظر بگیرید که در آن
، شماره سطح منطقی هر گیت و
شماره آن گیت در آن سطح منطقی را نشان میدهد. گیتهای پایهای که در یک مدار کوانتومی میتوانند با هم اجرا گردند به عنوان یک سطح منطقی در نظر گرفته میشوند. پارامتر
برابر با تعداد کل سطوح منطقی (عمق) مدار است و
تعداد کل گیتها در سطح منطقی
ام را نشان میدهد.
میتوان مسئله سنتز منطقی این ماتریس یکانی به کتابخانه پایه را به صورت یک مسئله بهینهسازی مقید چندهدفه مدلسازی کرد
(7)
که در آن مجموعهای از توابع هدف است که به شرح (8) است
(8)
هدف این مسئله، بهینهسازی 3 معیار ارزیابی عمق مدار4، تعداد کل گیتها و تعداد گیتهای CNOT است.
در روش پیشنهادی، فضای جوابی از ترکیبهای مختلف روشهای تجزیه QSD و CSD ایجاد میشود. فضای جواب ایجادشده، یک فضا با اندازه نمایی بسیار بزرگ است. سپس با استفاده از یک رهیافت پایین به بالا از روش حل برنامهریزی پویای چندهدفه (MODP)، روشی ارائه میشود تا تنها بخشی از کل فضای جواب، برای یافتن مدارها با هزینههای بهینه پرتو جستجو شوند. این روش، 5MOQLS خوانده میشود.
برنامهریزی پویای چندهدفه6 [35]، روش حل مسأله برای یافتن نقاط بهینه پرتو در مسائل بهینهسازی چندهدفه با اعمال روش برنامهریزی پویا میباشد. این روش حل به مسائلی قابل اعمال است که یک مسأله را میتوان به صورت بازگشتی به زیرمسائلی شکست و بهینه پرتو بودن یک جواب به بهینه پرتو بودن جوابهای زیرمسائل آن منجر میشود.
روش پیشنهادی که برای ساختن فضای جواب، در آن از ترکیب دو روش QSD و CSD استفاده میگردد، 7SSG خوانده میشود. در این روش، ماتریس میتواند با روشهای 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 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، مقایسه بین تعداد حالات کل و
را به ازای
1: 2: if 3: then return 4: 5: 6: for 7: 8: for all 9: if by all 10: then 11: 12: if 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 مقاله علمی در مجلات معتبر و کنفرانس های ملی و بینالمللی و دهها گزارش فنی و طرح پژوهشی را به چاپ رسانیده است.