پیاده‌سازی خودکار مدارهای کوانتومی روی QFPGA با هدف همانندسازی
محورهای موضوعی : مهندسی برق و کامپیوترمصطفی حیدرزاده 1 * , محمد دانایی‌فر 2
1 - دانشگاه صنعتی امیرکبیر
2 - دانشگاه صنعتي خواجه نصیرالدين طوسي
چکیده مقاله :
در این مقاله ابتدا به تعریف یک معماری بهینه برای FPGA با استفاده از روش‌های دقیق پرداخته شده و برای نیل به این هدف، جایابی و مسیریابی بهینه با استفاده از برنامه‌ریزی خطی به طور دقیق تعریف شده است. پس از بازتعریف معماری داخل سلول‌های منطقی، مدارهای کوانتومی توسط یک الگوریتم مکاشفه‌ای با هدف استفاده حداکثری از منابع داخل سلول‌های منطقی و کاهش تأخیر مسیرهایی که کیوبیت‌ها در مدار طی می‌کنند، افراز می‌شوند. نتایج به دست آمده پس از تعریف معماری FPGA نشان می‌دهد که تأخیر مسیرهای بحرانی در برخي مدارهاي كوانتومي به کمتر از نصف کاهش می‌یابد و تعداد کانال‌های مصرف‌شده برای مسیریابی در معماری جدید تا حد قابل توجهی کاهش یافته است. همچنین نتایج نشان می‌دهد افزایش تعداد ورودی‌های سلول‌های منطقی از 12 کیوبیت به 4 کیوبیت، می‌تواند تعداد کانال‌های مصرفی و تأخیر مدارها را تا حد زیادی کاهش دهد.
This paper defines an optimal architecture for the FPGA using exact methods. In order to achieve this goal, optimal placement and routing solutions are found using the integer linear programming techniques. After redefining the internal architecture of the logic blocks, quantum circuits are partitioned by a heuristic algorithm in order to reach maximum utilization of the resources inside logic blocks and minimum delay of the paths traversed by the q-bits in the circuit. Experimental results show that FPGA architecture modifications can result in the reduction of the delay of critical paths of circuits by up to half in some cases and in a considerable reduction of the number of channels used for routing. Furthermore, the results show that defining the logic blocks with 12 q-bits instead of 4 q-bits can decrease circuits delay and the number of used channels to a large extent.
[1] S. Imre and F. Balazs, Quantum Computing and Communications, John Wiley & Sons, 2005.
[2] A. Barenco, C. H. Bennett, R. Cleve, D. P. DiVincenzo, N. Margolus, P. Schor, T. Sleator, J. Smolin, and H. Weinfurter, "Elementary gates for quantum computation," Physical Review, vol. 52, no. 5, pp. 3457-3467, Nov. 1995.
[3] M. Udresco, L. Prodan, and M. Vladutiu, "Using HDLs for describing quantum circuits: a framework for efficient quantum algorithm simulation," in Proc. 1st ACM Conf. on Computing Frontiers, vol. 44, pp. 96-110, Apr. 2004.
[4] M. Fujishima, K. Saito, M. Onouchi, and H. Hoh, "High - speed processor for quantum - computing emulation and its applications," in Proc. IEEE Int. Symp. on Circuits and Systems, vol. 4, pp. 884-887, May 2003.
[5] M. Fujishima, "FPGA-based high - speed emulator of quantum computing," in Proc. IEEE Int. Conf. on Field-Programmable Technology, vol. 4, pp. 21-26, Dec. 2003.
[6] J. P. Hayes and I. L. Markov, Simulation, Synthesis, and Testing of Quantum Circuits, DARPA QuIST Annual Research Review, Beverly Hills, 2003.
[7] Stratix Device Handbook, vol. 1, http://www.altra.com
[8] A. Glassner, Quantum Computing Part 2, http://www.glassner.com, Sep. 2001.
[9] A. Abdollahi and M. Pedram, "Decision diagram-based representation and recursive bi-decomposition of quantum logic functions," IEEE Trans. on Computers, Under Review.
[10] J. Swartz, V. Betz, and J. Rose, "A fast routability - driven router for FPGAs," in Proc. Int. Symp. on Field Programmable Gate Arrays pp. 140-149, Monterey, CA, US, Mar. 1998.
[11] D. G. Luenberger and Y. Ye, Linear and Nonlinear Programming, Springer, 3rd Edition, pp. 79-90, 2008.
[12] م. امینیان، همانندسازی مدارهای کوانتومی با استفاده از FPGA، پایان‌نامه کارشناسی ارشد، دانشگاه صنعتی امیرکبیر، دانشکده مهندسی کامپیوتر و فن‌آوری اطلاعات، 1387.
[13] G. F. Viamontes, I. L. Markov, and J. P. Hayes, "Improving gate- evel simulation of quantum circuits," Quantum Information Processing, vol. 2, no. 5, pp. 347-380, Sep. 2003.
[14] A. U. Khalid, Z. Zilic, and K. Radecka, "FPGA emulation of quantum circuits," in Proc. IEEE Intl Conf. on Computer Design, pp. 310-315, 11-13 Oct. 2004.
[15] Wikipedia, "Timeline of quantum computers," Jul. 2007.