Chapter 6
Concluding Remarks
A physical error of a logic operation is considered as one of the biggest problems for researchers to realize a quantum computer. Recently, topological quantum computation is considered as the most promising model of computation to overcome the problem and the most promising way to realize a quantum computer. Throughout this thesis, the design methods for topological quantum circuit have been studied. To date, many optimization methods have been proposed to support the design framework for topological quantum computation. However, this thesis found some new efficient optimization methods that can at least improve two important levels of the design framework, the quantum circuit level and the logical layer level.
In Chapter 1, this thesis gives reasons why the realization of topological quantum com-putation are much anticipated and the need of efficient design methods to support the circuit model for topological quantum computation. Chapter 2 discusses the necessary background for this thesis.
Chapter 3 of this thesis presents the design framework for topological quantum com-putation which starts from the quantum algorithm level, and ends at the physical hardware level. The presented design flow are similar to that of conventional quantum computation.
But the main differences are in the quantum circuit level and the logical layer level, where logical operations are encoded as defects, and a topological quantum computer makes it possible to arrange quantum bits two-dimensionally. This thesis also includes an approach to support the proposed design flow in this chapter. The main contributions of this thesis are on the quantum circuit level and the logical layer level of the proposed design flow, which are discussed in Chapter 4 and Chapter 5, respectively.
When designing quantum circuits, a so-called quantum cost is often regarded as an important criterion to evaluate the quality of a quantum circuit. Therefore, how to lower the quantum cost for quantum circuits is regarded as one of the main challenges for the researchers to build a quantum computer. This is because quantum gates such as Toffoli gates are often expensive. To develop an efficient optimization method to reduce the quan-tum cost for circuits in topological quanquan-tum computation model was this thesis first main motivation. Over the years, many ESOP minimization-based quantum circuit optimization methods have been proposed, however, this thesis is the only work that formally discusses how ESOP expressions can be manipulated to reduce the quantum cost of the correspond-ing circuit by makcorrespond-ing temporary changes to the original function. Chapter 4 in this thesis demonstrates that the proposed method that can be considered as a goodpre-optimization method. The proposed method makes temporary changes to the function, in contrast to the existing methods that keep the function unchanged. The temporary changes is made to the original function by adding MPMCT gates, so that the changed function leads to a smaller quantum circuit. Later, the proposed method evaluates ”good” temporary changes
and picks the one that reduces the total quantum cost, including the additional MPMCT gates, as much as possible. Further, to make the proposed method practical, based on the idea, this thesis also proposes an iterative heuristic method to reduce the quantum cost for practical circuits. The experimental results clearly shown that the proposed method could reduce the quantum cost in most cases.
In topological quantum computation model, a large number of physical qubits can be arranged in a three-dimensional space in lattice, and thus it is possible to arrrange the qubits in two dimensions. Thus, Chapter 5 discusses how to reduce the computational time steps by utilizing the properties of braiding operations. This chapter also shows the difference between the uses of two-dimensional qubit layout and one-dimensional qubit layout that is often used in conventional topological quantum circuit for reducing the computational time steps for topological quantum computation. A preliminary study in this thesis clearly shows that the proposed method is very useful to reduce the computational time steps com-pared to existing methods which make use of only one dimensional layouts. To evaluate the usefulness of two-dimensional qubit layout, this thesis also conducts a case study for practical ICM circuit, and based on the results it can be concluded that the qubit layout is likely very important for larger cases.
For further improvement of the topological quantum computation circuit design, the future works of this thesis will be focusing on developing more optimization methods that can be combined together with the proposed methods discussed in this thesis, especially in order to minimize the geometric description volume/computational steps for topological circuit. It can be seen in Chapter 5 that although the method proposed in this thesis can find a good two-dimensional qubit layout systematically, the method to solve the second sub-problem is limited, and thus it cannot deal with a large problem. Therefore, one of the
possible future works is to develop an efficient method to solve the second sub-problem.
Additionally, another possible future work is to find a method that can be used to reduce the quantum cost for quantum circuit. So far, the techniques used in this thesis to demon-strate the usefulness of making temporary changes to the original function is by inserting MPMCT gates only, thus one possible work is to investigate how useful the idea would be when applied to other quantum gates (i.e., controlled-V and controlledV†, where V andV†
are referred to as the square root of NOT gates; applying V twice and applyingV†twice are both equivalent to a NOT operation).
Acknowledgements
Alhamdulillah (Praise to God),
Foremost, I want to thank our God, Allah, for the wisdom He bestowed upon me, the strength, peace of mind and good health in order to finish this research. This thesis be-comes a reality with the kind support and help of many individuals, and I would like to extand my sincere thanks to all of them. I would like to thank my PhD advisor, Professor Shigeru Yamashita for accepted me as a PhD candidate into his lab and for his guidance throughout my PhD degree years from April 2014 to September 2017 at Ritsumeikan Uni-versity. He has been a great mentor to me and provided me with great advice. There are many members of the NGC Lab that I want to thank you especially the quantum group.
Among them the people that I worked with and learned from are Koutarou Hoshi, Kouhei Kushida, Kentaro Haneda, Masato Onada and Ding Jing Wen, thank you for your con-tinued support. I would like to thank Yayasan Pelajaran Mara (YPM), which supported my doctoral degree studies through the Japanese Assosiate Degree (JAD) program. My sincere thanks to Professor Hiroyuki Oochi, Professor Hideyuki Takada and Dr. Yasuhiro Takahashi for their careful reading, valuable comments and suggestions regarding this the-sis. I also thank my friends (too many to list but you know who you are) for listening to me and always be there for me. Finally, last but not least, I would like to give my most sincere appreciation to my loving parents, my caring younger brother, and my all time cheerful younger sisters for always supporting me and believing in me. I know I always have my family to count on when times are rough, thank you and I love you all dearly.
Nurul Ain Binti Adnan September, 2017. Shiga, Japan.
Bibliography
[1] Jack S. Kilby. Invention of the integrated circuit. InIEEE Transactions on electron devices, Volume 23, No. 7, pp. 648–654, 1976.
[2] Robert R. Schaller. Moore’s law: past, present and future. InIEEE spectrum, Vol. 34, No. 6, pp. 52–59, 1997.
[3] Jens Eisert, and Michael M. Wolf. Quantum computing. In Handbook of nature-inspired and innovative computing, pp. 253–286, 2006.
[4] Eleanor Rieffel, and Wolfgang Polak. An introduction to quantum computing for non-physicists. InACM Computing surveys, Vol. 32, No. 3, pp. 300–335, 2000.
[5] Jozef Gruska. Quantum computing. McGraw-Hill London, Vol. 2005, 1999.
[6] Alexandru Paler, Simon Devitt, Kae Nemoto, and Ilia Polian. Cross-level validation of topological quantum circuits. International Conference on Reversible Computation, pp. 189–200, 2014.
[7] Mathias Soeken, Martin Roetteler, Nathan Wiebe, and Giovanni D. Micheli. Design Automation and Design Space Exploration for Quantum Computers. InarXiv preprint arXiv:1612.00631, 2016.
[8] Anne Broadbent, and Elham Kashefi. Parallelizing quantum circuits. In heoretical computer science, Vo. 410, No. 26, pp. 2489–2510, 2009.
[9] Michael A. Nielsen, and Isaac L. Chuang. Quantum computation and Quantum infor-mation. InCambridge University Press India, 2000.
[10] Peter W. Shor. Fault-tolerant quantum computation. In Foundations of Computer Science., 37th Annual Symposium on IEEE. pp. 56–65, 1996.
[11] Jiannis K. Pachos. Introduction to topological quantum computation. Cambridge University Press, 2012.
[12] Robert Raussendorf, and Jim Harrington. Fault-tolerant quantum computation with high threshold in two dimensions. Physical review letters, APS, Vol. 98, No. 19, pp.
190504, 2007.
[13] Shigeru Yamashita. An optimization problem for topological quantum computation.
InTest Symposium (ATS), 2012 IEEE 21st Asian, pp. 61–66, 2012.
[14] Ashok Muthukrishnan. Classical and Quantum Logic Gates: An Introduction to Quantum Computing Quantum Information Seminar. InCiteseer, 1999.
[15] Zahra Sasanian, and D. Micheal Miller. Reversible and quantum circuit optimization:
A functional approach. InReversible Computation 4th International Workshop, RC 2012. Revised Papers, pages 112-124, 2013.
[16] Adam Paetznick, and Austin G. Fowler. Quantum circuit optimization by topological compaction in the surface code. InarXiv preprint arXiv:1304.2807, 2013.
[17] Keisuke Fujii. Quantum Computation with Topological Codes: from qubit to topo-logical fault-tolerance. InSpringer, Vol. 8, 2015.
[18] Austin G. Fowler, Matteo Mariantoni, John M. Martinis, and Andrew N. Cleland. Sur-face codes: Towards practical large-scale quantum computation. InPhysical Review A, APS, Vol. 86, No. 3, pp. 032324, 2012.
[19] Austin G. Fowler, Ashley M. Stephens, and Peter Groszkowski. High-threshold uni-versal quantum computation on the surface code. InPhys. Rev. A 80:052312, 2009.
[20] Alexandru Paler, Ilia Polian, and Simon J. Devitt. A compiler for fault-tolerant high level quantum circuits. InarXiv preprint arXiv:1509.02004, 2015.
[21] Lov K. Grover. A fast quantum mechanical algorithm for database search. In Pro-ceedings of the twenty-eighth annual ACM symposium on Theory of computing, pp.
212-219, 1996.
[22] Emma Strubell. An introduction to quantum algorithms. In COS498 Chawathe Spring, 2011.
[23] Shigeru Yamashita, Shin-ichi Minato, and D. Micheal Miller. DDMF: An efficient decision diagram structure for design verification of quantum circuits under a practical restriction. InIEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, Vol. 91, No. 2, pp. 3793-3802, 2008.
[24] D. Micheal Miller, Dmitri Maslov, and Gerhard W. Dueck. A transformation based algorithm for reversible logic synthesis. InProceedings of the 40th annual Design Automation Conference,pp. 318–323, IEEE 2003.
[25] Mathias Soeken, Gerhard W. Dueck, and D. Micheal Miller. A Fast Symbolic Trans-formation Based Algorithm for Reversible Logic Synthesis. InReversible Computa-tion 2016, pp. 307–321, 2016.
[26] Mona Arabzadeh, Mehdi Saeedi, and Morteza Saheb Zamani. Rule-based optimiza-tion of reversible circuits. InDesign Automation Conference (ASP-DAC), 2010 15th Asia and South Pacific, pp. 849-854, IEEE 2010.
[27] Kamalika Datta, Gaurav Rathi, Indranil Sengupta, and Hafizur Rahaman. An im-proved reversible circuit synthesis approach using clustering of esop cubes. InACM Journal on Emerging Technologies in Computing Systems (JETC), Vo. 11, No. 2, pp.
15, November 2014.
[28] Kenneth Fazel, Mitchell A. Thornton, and Jacqueline E. Rice. Esop-based Toffoli gate cascade generation. InIEEE Pacific Rim Conference on Communications, Computers and Signal Processing, pp. 206–209, 2007.
[29] Mehdi Saeedi, and Igor L. Markov. Synthesis and Optimization of Reversible Cir-cuits; a survey. InACM Comput. Surv.,, Vol.45, No. 2, pp. 21, March 2013.
[30] Anindita Banerjee, and Anirban Pathak. An algorithm for minimization of quantum cost. InarXiv preprint arXiv:0910.2129, 2009.
[31] Nabila Abdessaied, Mathias Soeken, and Rolf Drechsler. Quantum circuit optimiza-tion by Hadamard gate reducoptimiza-tion. InInternational Conference on Reversible Compu-tation, pp. 149–162, Springer, 2014.
[32] Marek Szyprowski, and Pawel Kerntopf. An approach to quantum cost optimization in reversible circuits. In 11th IEEE Conference on Nanotechnology (IEEE-NANO), pp. 1521–1526, 2011.
[33] Marek Szyprowski, and Pawel Kerntopf. Reducing quantum cost in reversible Toffoli circuits. InarXiv preprint arXiv:1105.5831, 2011.
[34] Dmitri Maslov, Sean M. Falconer, and Michele Mosca. Quantum circuit placement.
InIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, Vol. 27, No. 4, pp. 752–763, 1992.
[35] Alexandru Paler, Simon J. Devitt, Kae Nemoto, and Ilia Polian. Mapping of topolog-ical quantum circuits to phystopolog-ical hardware. InScientific reports, Nature Publishing Group, vol. 4, 2014.
[36] Alexandru Paler, Ilia Polian, Kae Nemoto, and Simon J. Devitt. A fully fault-tolerant representation of quantum circuits. InInternational Conference on Reversible Com-putation, pp. 139–154, 2015.
[37] Soonchil Lee, Lee Seong-Joo, Kim Lee Taegon, Jacob Biamonte, and Marek Perkowski. The cost of quantum gate primitives. InJournal of Multiple Valued Logic and Soft Computing, Vol. 12, pp. 561–573, 2006.
[38] Adriano Barenco, Charles H. Bennett, Richard Cleve, David P. DiVincenzo, Norman Margolus, Peter Shor, Tycho Sleator, John A. Smolin, and Harald Weinfurter. Ele-mentary gates for quantum computation. In Physical review A, Vol. 52, No. 5, pp.
3457–3467, 1995.
[39] Md. Selim Al Mamun, and David Menville. Quantum cost optimization for reversible sequential circuit. InarXiv preprint arXiv:1407.70981, 2014.
[40] Dmitri Maslov, Gerhard W. Dueck, and D. Micheal Miller. Toffoli network synthe-sis with templates. InIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, Vol. 24, No. 6, pp. 807–817, 2005.
[41] Dmitri Maslov, Christina Young, Gerhard W. Dueck, and D. Micheal Miller. Quantum circuit simplification using templates. InDesign, Automation and Test in Europe, pp.
1208–1213, 2005.
[42] Nurul Ain B. Adnan, Kouhei Kushida, and Shigeru Yamashita. A pre-optimization technique to generate initial reversible circuits to reduce the low quantum cost. In IEEE International Symposium on Circuits and Systems (ISCAS), Vol. 12, No. 1, pp.
2298-2301, 2016.
[43] Zahra Sasanian, and D. Micheal Miller. Reversible and quantum circuit optimization, A functional approach. InInternational Workshop on Reversible Computation, pp.
112–124, 2012.
[44] Alan Mishchenko. Two-level exclusive sum-of-product minimization.
http://web.cecs.pdx.edu/ alanmi/research/min/minESOP.htm.
[45] Shigeru Yamashita. An optimization problem for topological quantum computation.
InTest Symposium (ATS), IEEE 21st Asian, pages 61-66, 2012.
[46] Daniel Br´elaz. New methods to color the vertices of a graph. InCommun. ACMVol.
22, No. 4, pp. 251256, 1979,
[47] Shin-Ichi Minato. πDD: A new decision diagram for efficient problem solving in per-mutation space. InProc. of 14th International Conference on Theory and Applications of Satisfiability Testing (SAT-2011) (LNCS 6695, Springer), pp. 90-104, 2011.
[48] Emile Aarts and Jan Korst. Simulated annealing and Boltzmann machines. In John Wiley and Sons, pp. 3–75, 1989.