Efficient Algorithm for Quantum Circuit Synthesis and Optimization
Explore the efficient algorithm for synthesizing quantum circuits and optimizing quantum computation. Delve into essential functions, sorting, and experimental results in quantum computation. Discover the advancements in quantum computation led by IBM, Google, and Lockheed Martin. Learn about the fundamentals of quantum computation and reversible computation, along with gate symbols and CNT library for quantum circuits.
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
An Efficient Algorithm to An Efficient Algorithm to Synthesize Quantum Circuits and Synthesize Quantum Circuits and Optimization Optimization mercan Susam Mustafa Altun
Outline Quantum Computation Algorithm Essential Functions Sorting Optimization Experimental Results Conclusion
Outline Quantum Computation Algorithm Essential Functions Sorting Optimization Experimental Results Conclusion
Quantum Computation IBM 3 Billion $ Investment Google Quantum Artificial Intelligence Lab. Lockheed Martin Complex System Correction
Quantum Computation Richard Feynman suggested the idea in 1982. Shor factorization algorithm Grover searching algorithm Richard Feynman Feynman, R. P. (1982). Simulating physics with computers. International journal of theoretical physics, 21(6), 467-488.
Bit - Qubit Bit Qubit 0 1 0 or 1 superposition 0 1 ?,? ? 1 0 ? = ? 0 + ? 1 0 1 1 0 ?2+ ?2= 1 0 1 ?2 0 ?2 1 ? ? Bloch Sphere Nielsen, M. A., & Chuang, I. L. (2010). Quantum computation and quantum information. Cambridge university press.
Classical vs Quantum Computation 1-bit Full Adder Classical Circuit Quantum Circuit = ???? = ?
Reversible Computation High Efficiency Optical Computation DNA Computation Landauer, Rolf. "Irreversibility and heat generation in the computing process." IBM journal of research and development 5.3 (1961): 183-191.
Gate Symbols Quantum Cost
CNT (C-NOT, NOT, Toffoli) Library NOT C-NOT Toffoli CC-NOT Input ??? 000 001 010 011 100 101 110 111 Output ? ? ? 0 0 1 0 0 0 0 1 1 0 1 0 1 0 1 1 0 0 1 1 1 1 1 0 Input ??? 000 001 010 011 100 101 110 111 Output ? ? ? 0 0 0 0 0 1 0 1 1 0 1 0 1 0 0 1 0 1 1 1 1 1 1 0 Input ??? 000 001 010 011 100 101 110 111 Output ? ? ? 0 0 0 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 1 1 1 0
Quantum Logic Functions ? 2? Row number 2?! All possible functions Bit size ? = 3, 23= 8, 23! = 40320 8? 7? 6? 5? 4? 3? 2? 1 = 40320 Input ??? 000 001 010 011 100 101 110 111 Output ? ? ? 0 0 0 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1 Input ??? 000 001 010 011 100 101 110 111 Output ? ? ? 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
Outline Quantum Computation Algorithm Essential Functions Sorting Optimization Experimental Results Conclusion
Essential Functions Possible pairs ? ? ? 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 Functions Bit Size # of Essential Functions # of Total Functions 2 3 4 5 6 6 28 120 469 2016 24 40320 ? = 3, 23= 8, ?23 20922789888000 2.613308e + 35 1.268869e + 89 =8 7 2= 28 2
Essential Functions Input ??? 000 001 010 011 100 101 110 111 Input ??? 000 001 010 011 100 101 110 111 Input ??? 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
Essential Function Example Input ??? 000 001 010 011 100 101 110 111 Output ??? 000 001 110 111 100 101 010 011 Output ??? 000 001 110 101 100 111 010 011 Output ??? 000 001 010 101 100 011 110 111 111 Output ??? 000 001 010 101 100 111 110 011 Output ??? 000 101 010 001 100 011 110 111 Output ??? 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
Outline Quantum Computation Algorithm Essential Functions Sorting Optimization Experimental Results Conclusion
Sorting 3 3 3 4 Selection Sort Maximum essential function number for this method is = 2? 1 Merge Sort Each sorting in subsets requires essential function usage resulted with cost increase. Insertion Sort Every sliding process means extra function usage. 4 3 2 1 1 3 2 4 1 2 3 4 4 3 2 1 1 1 1 2 2 2 1 4 3 2 4 4 4 3 2 1 1 2 3 4 3 3 4 3 4 2 4 2 1 1 1 4 3 2 1 2 3 2 4 1 2 3 4 1 . . .
Optimum Sorting Top-Down Optimum f f 000 111 001 010 100 101 110 011 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 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 Essential Function Cost Essential Function Cost 1-7 2-7 3-7 7-3 1-3 2-3 4 4 1 9 1 2 2 5
Outline Quantum Computation Algorithm Essential Functions Sorting Optimization Experimental Results Conclusion
Optimization ?1 ?2
Quantum Optimization - Templates Toffoli Gate ? = ?2, ? = ? ,? = ? Quantum Cost Metric : NCV - 111 ? = ( ?)?, ?? = ?
Outline Quantum Computation Algorithm Essential Functions Sorting Optimization Experimental Results Conclusion
Suggested Method Optimum PN- CNT CNT PN-CNT CNT Experimental Results Size TD TD SP 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 Suggested Method Optimum Size 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 Reversible Cost W.A. Quantum Cost W.A. Time (seconds) 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% Reduced 577 10253 17049 8921 2780 625 102 12 1 Optimum Sorting 3236 20480 13282 2925 369 27 1 CNT PN-CNT R.C. A.O. 11.55 7.31 Q.C. A.O. Time R.C. A.O. 15.97 14.82 11.55 9.79 7.31 5.86 4.57 21.74 28.97 Q.C. A.O. Time 34.14 21.74 32.85 28.97 13.88 - 5m59s 6m33s 21 5m59s 8 8 6m33s 40 ?
Outline Quantum Computation Algorithm Essential Functions Sorting Optimization Experimental Results Conclusion
Conclusion We show that our method has better run time when compared with optimal approaches in the literature. Optimal circuit synthesis can be achieved only up to 4 bits in the literature. If we would apply same method for 5 bits, that would take 447x1018 years to synthesize each circuit. Low level circuit synthesis is one of our primary aims to reduce quantum operations in quantum computers. As a future work we will seek deeper optimization methods with using elementary gates and pulse signals.
Acknowledgments The Scientific and Technological Research Council of Turkey (T B TAK) (2210-C) Scientific Research Projects Agency of Istanbul Technical University (BAP)
References 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.
