Efficient Quantum Circuit Synthesis and Optimization
Explore the efficient algorithm for synthesizing quantum circuits and optimization, along with fundamental quantum computation functions, experimental results, and the history of quantum computing. Dive into classical and quantum computation, reversible circuits, quantum cost, and CNT library for quantum gates such as C-NOT, NOT, Toffoli, and more.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
Kuantum KuantumDevre Optimizasyonu Optimizasyonu i in Devre Sentezi Sentezi ve i in Verimli Verimli Bir Algoritma Algoritma ve Bir mercan Susam Mustafa Altun An Efficient Algorithm to Synthesize Quantum Circuits and Optimization An Efficient Algorithm to Synthesize Quantum Circuits and Optimization
erik Kuantum Hesaplama Algoritma Temel Fonksiyonlar S ralama Optimizasyon Deneysel Sonu lar Sonu
erik Kuantum Hesaplama Algoritma Temel Fonksiyonlar S ralama Optimizasyon Deneysel Sonu lar Sonu
Kuantum Hesaplama IBM 3 Milyar $ Yat r m Google Kuantum Yapay Zeka Laboratuvar Lockheed Martin Karma k Sistemlerin Do rulanmas
Kuantum Hesaplama 1982 de Richard Feynman taraf ndan nerildi. Shor faktorizasyon algoritmas Grover arama algoritmas Richard Feynman Feynman, R. P. (1982). Simulating physics with computers. International journal of theoretical physics, 21(6), 467-488.
Bit - Kbit Bit K Bit 0 1 0 ya da 1 s perpozisyon 0 1 ?,? ? 1 0 ? = ? 0 + ? 1 0 1 1 0 ?2+ ?2= 1 0 1 ?2 0 ?2 1 ? ? Bloch K resi Nielsen, M. A., & Chuang, I. L. (2010). Quantum computation and quantum information. Cambridge university press.
Klasik Hesaplama Kuantum Hesaplama 1-bit Tam Toplay c Klasik Devre Kuantum Devre = ???? = ?
Tersinir Devreler Y ksek verimlilik Optik Hesaplama DNA Hesaplama Landauer, Rolf. "Irreversibility and heat generation in the computing process." IBM journal of research and development 5.3 (1961): 183-191.
Kap Sembolleri ve Matrisler Kuantum Maliyet
CNT (C-NOT,NOT,Toffoli) Ktphanesi NOT C-NOT Toffoli CC-NOT Giri ??? 000 001 010 011 100 101 110 111 k ? ? ? 0 0 1 0 0 0 0 1 1 0 1 0 1 0 1 1 0 0 1 1 1 1 1 0 Giri ??? 000 001 010 011 100 101 110 111 k ? ? ? 0 0 0 0 0 1 0 1 1 0 1 0 1 0 0 1 0 1 1 1 1 1 1 0 Giri ??? 000 001 010 011 100 101 110 111 k ? ? ? 0 0 0 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 1 1 1 0
Kuantum Lojik Fonksiyonlar ? 2? Sat r say s 2?! Olu turulabilecek t m fonksiyonlar n say s Bit say s ? = 3, 23= 8, 23! = 40320 8? 7? 6? 5? 4? 3? 2? 1 = 40320 Giri ??? 000 001 010 011 100 101 110 111 k ? ? ? 0 0 0 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1 Giri ??? 000 001 010 011 100 101 110 111 k ? ? ? 0 0 0 - 0 0 1 - 0 1 0 - 0 1 1 - 1 0 0 - 1 0 1 - 1 1 0 - 1 1 1 0 0 0 - 0 0 1 - 0 1 0 - 0 1 1 - 1 0 0 - 1 0 1 - 1 1 0 0 0 0 - 0 0 1 - 0 1 0 - 0 1 1 - 1 0 0 - 1 0 1 0 0 0 - 0 0 1 - 0 1 0 - 0 1 1 - 1 0 0 0 0 0 - 0 0 1 - 0 1 0 - 0 1 1 0 0 0 - 0 0 1 - 0 1 0 0 0 0 - 0 0 1 0 0 0 1 2 3 4 5 6 7 8
erik Kuantum Hesaplama Algoritma Temel Fonksiyonlar S ralama Optimizasyon Deneysel Sonu lar Sonu
Temel Fonksiyon Nedir? Olu abilecek ikili gruplar ? ? ? 0 0 1 - 0 1 0 - 0 1 1 - 1 0 0 - 1 0 1 - 1 1 0 - 1 1 1 0 1 0 - 0 1 1 - 1 0 0 - 1 0 1 - 1 1 0 - 1 1 1 0 1 1 - 1 0 0 - 1 0 1 - 1 1 0 - 1 1 1 1 0 0 - 1 0 1 - 1 1 0 - 1 1 1 1 0 1 - 1 1 0 - 1 1 1 1 1 0 - 1 1 1 1 1 1 ??? 000 001 010 011 100 101 110 111 7 + 6 + 5 + 4 + 3 + 2 + 1 = 28 Fonksiyonlar Bit Say s Temel Fonksiyon # 6 28 120 469 2016 Toplam Fonksiyon # 24 40320 20922789888000 2.613308e + 35 1.268869e + 89 2 3 4 5 6 ? = 3, 23= 8, ?23 =8 7 2= 28 2
Temel Fonksiyonlar Giri ??? 000 001 010 011 100 101 110 111 Giri ??? 000 001 010 011 100 101 110 111 Giri ??? 000 001 010 011 100 101 110 111 ?1 ?2 ? ? ? ? 0 0 0 0 0 1 0 1 0 1 0 1 1 0 0 0 1 1 1 1 0 1 1 1 ? ? ? 1 0 0 0 0 1 0 1 0 0 1 1 0 0 0 1 0 1 1 1 0 1 1 1 ? ? ? 1 0 0 0 0 1 0 1 0 1 0 1 0 0 0 0 1 1 1 1 0 1 1 1 1 2 3 4 5 6 7 8 1 2 3 6 5 4 7 8 1 2 3 4 5 6 7 8 5 2 3 4 1 6 7 8 1 2 3 4 5 6 7 8 5 2 3 6 1 4 7 8
Temel Fonksiyon rnek Giri ??? 000 001 010 011 100 101 110 111 k ??? 000 001 110 111 100 101 010 011 k ??? 000 001 110 101 100 111 010 011 k ??? 000 001 010 101 100 011 110 111 111 k ??? 000 001 010 101 100 111 110 011 k ??? 000 101 010 001 100 011 110 111 k ??? 000 101 110 001 100 111 010 011 ?1 ??? 000 001 010 101 100 011 110 ?2 ??? 100 001 010 101 000 011 110 111 ? ? ? ? 100 001 010 101 000 011 110 111 1 2 3 4 5 6 7 8 ?1 ?2
erik Kuantum Hesaplama Algoritma Temel Fonksiyonlar S ralama Optimizasyon Deneysel Sonu lar Sonu
Sralama 3 3 Se meli S ralama Kullan lacak temel fonksiyon say s olacakt r. Maksimum = 2? 1 Birle tirmeli S ralama Alt k meler i erisnde yap lacak olan her yerde i ikli i bir temel fonksiyon kullan m gerektirdirir. Eklemeli S ralama Yap lacak olan her kayd rma i lemi ek temel fonksiyon kullan m na neden olur. 4 3 2 1 1 3 2 4 1 2 3 4 4 3 2 1 1 4 3 2 4 4 1 1 2 2 4 3 2 1 1 2 3 4 4 3 2 1 3 3 4 4 2 2 1 1 3 2 4 1 2 3 4 1 . . .
Optimum Sralama Yukar dan A a ya Optimum f f 000 111 001 010 100 101 110 011 Temel Fonksiyon Maliyet 0 7 1 2 4 5 6 3 0 1 7 2 4 5 6 3 0 1 2 7 4 5 6 3 0 1 2 3 4 5 6 7 000 111 001 010 100 101 110 011 Temel Fonksiyon Maliyet 0 7 1 2 4 5 6 3 0 3 1 2 4 5 6 7 0 1 3 2 4 5 6 7 0 1 2 3 4 5 6 7 1-7 2-7 3-7 7-3 1-3 2-3 4 4 1 9 1 2 2 5
erik Kuantum Hesaplama Algoritma Temel Fonksiyonlar S ralama Optimizasyon Deneysel Sonu lar Sonu
Optimizasyon ?1 ?2
Kuantum Optimizasyon - ablonlar Toffoli Kap s ? = ?2e er ? = ? ,? = ? Kuantum Maliyet Metri i : NCV - 111 ? = ( ?)?, ?? = ?
erik Kuantum Hesaplama Tersinir Devreler Algoritma Temel Fonksiyonlar S ralama Optimizasyon Deneysel Sonu lar Sonu
nerilen Yntem Optimum PN- CNT CNT PN-CNT CNT Deneysel Sonu lar Boyut TDS TDS EK OPT OPT 28 27 26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0 4 29 90 207 436 791 1252 1954 2523 3349 3772 4125 4211 3842 3522 2835 2308 1706 1239 843 547 340 194 111 52 25 9 3 1 10 31 145 238 682 1031 1625 2720 3129 4022 4383 4179 4126 3528 3104 2389 1772 1203 818 531 322 181 80 43 18 9 1 nerilen Y ntem Optimum Boyut CNT PN-CNT CNT PN-CNT 1 0 5 47 167 473 1283 2748 4657 6018 6586 5696 4347 3137 2178 1354 825 438 208 100 42 9 1 Tersinir Maliyet A.O. KuantumMaliyet A.O. S re (saniye) 15.97 10.58 5.86 4.57 4 22 132 249 1126 1758 2988 4686 5158 5945 5752 4485 3512 2321 1190 615 286 78 12 1 34.26 30.43 13.88 - 8 14 40 ? 1 64 364 1160 2500 5820 8756 8656 6837 3996 1611 452 90 12 1 %38.26 13.10 %5.61 yile tirme 577 10253 17049 8921 2780 625 102 12 1 Optimum S ralama 3236 20480 13282 2925 369 27 1 CNT PN-CNT T.M. A.O. 11.55 7.31 K.M. A.O. S re T.M. A.O. 15.97 14.82 11.55 9.79 7.31 5.86 4.57 21.74 28.97 K.M. A.O. S re 34.14 21.74 32.85 28.97 13.88 - 5d59s 6d33s 21 5d59s 8 8 6d33s 40 ?
erik Kuantum Hesaplama Tersinir Devreler Algoritma Temel Fonksiyonlar S ralama Optimizasyon Deneysel Sonu lar Sonu
Sonu nerdi imiz sentezleme y ntemini, optimum y ntemlerle k yaslad m zda, al ma s relerimizin her zaman daha iyi kt n g rd k. Literat rde hen z 5 bit devreler i in dahi optimum sentezleme algoritmas bulunmamaktad r. 4 bit devreleri optimum sentezlemek i in sunulmu olan en iyi algoritmay , 5 bit i in uygulasayd k, t m fonksiyonlar zmemiz 447x1018y l m z alacakt . leriye y nelik amac m z, belirli kuantum hesaplama y ntemleri i in daha d k seviyede devre sentezlerini ger ekle tirmek.
Teekkrler 2210-C ncelikli Alanlara Y nelik Yurt i Y ksek Lisans Burs Program stanbul Teknik niversitesi Bilimsal Ara t rma Projeleri
Referanslar R.P. Feynman, "Simulating physics with computers." International journal of theoretical physics, pp. 467-488, June 1982. P. W. Shor, "Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer," AT&T Research, Santa Fe, NM, 1995. L. K. Grover, "A fast quantum mechanical algorithm for database search," in 28th Annual ACM Symposium on the Theory of Computing, Murray Hill NJ, 1996. Landauer, Rolf. "Irreversibility and heat generation in the computing process." IBM journal of research and development 5.3 (1961): 183-191. Maslov, Dmitri, Gerhard W. Dueck, and D. Michael Miller. "Toffoli network synthesis with templates." Computer-Aided Design of Integrated Circuits and Systems, IEEE Transactions on 24.6 (2005): 807-817. M.A. Nielsen, I.L. Chuang. Quantum computation and quantum information. Cambridge University press, 2010. A. Barenco, et al. "Elementary gates for quantum computation." Physical Review A 52, November 1995. V.V. Shende, A.K. Prasad, I.L. Markov, J.P. Hayes, "Synthesis of reversible logic circuits." Computer-Aided Design of Integrated Circuits and Systems, IEEE Transactions, pp. 710-722, June 2003. Wille, Robert, et al. "Exact synthesis of Toffoli gate circuits with negative control lines." Multiple-Valued Logic (ISMVL), 2012 42nd IEEE International Symposium on. IEEE, 2012.
