Multi-Objective Logic Synthesis of Quantum Circuits
Subject Areas : electrical and computer engineeringArezoo Rajaei 1 , Mahboobeh Houshmand 2 * , Seyyed Abed Hosseini 3
1 - Mashhad Branch, Islamic Azad University
2 - Mashhad Branch, Islamic Azad University, Mashhad, Iran
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.