Quantum-Logic Synthesis Using Improved Block-Based Approach
Subject Areas : electrical and computer engineering
K.
Marjoei
1
M.
Houshmand
2
M.
Saheb Zamani
3
(Amirkabir University of Technology)
M.
Sedighi
4
Keywords: Quantum computing quantum circuits logic-synthesis optimization constrained-optimization,
Abstract :
Quantum-logic synthesis refers to generating a quantum circuit for a given arbitrary quantum gate according to a specific universal gate library implementable in quantum technologies. Previously, an approach called block-based quantum decomposition (BQD) has been proposed to synthesize quantum circuits by using a combination of two well-known quantum circuit synthesis methods, namely, quantum Shannon decomposition (QSD) and cosine-sine decomposition (CSD). In this paper, an improved block-based quantum decomposition (IBQD) is proposed. IBQD is a parametric approach and explores a larger space than CSD, QSD, and BQD to obtain best results for various synthesis cost metrics. IBQD cost functions for synthesis are calculated in terms of different synthesis cost metrics with respect to the parameters of the proposed approach. Furthermore, in order to find optimum results according to these functions, IBQD synthesis approach is defined as a constrained-optimization model. The results show that IBQD can lead to the minimum total gate cost among all the proposed approaches for the specific case of 4-qubit quantum circuit synthesis. Moreover, for the first time, the depth costs of the CSD, QSD, BQD, and IBQD synthesis approaches are evaluated and it is shown that IBQD makes a trade-off between the total gates and depth costs for the synthesized quantum circuits.
[1] M. Nielsen and I. L. Chuang, Quantum Computation and Quantum Information, Cambridge University Press, 2011.
[2] N. S. Yanofsky and M. A. Mannucci, Quantum Computing for Computer Scientists, Cambridge University Press, 2008.
[3] M. Nakahara and T. Ohmi, Quantum Computing: From Linear Algebra to Physical Realizations, Taylor & Francis, 2008.
[4] P. W. Shor, "Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer," SIAM J. on Computing, vol. 26, no. 5, pp. 1484-1509, Oct. 1997.
[5] L. K. Grover, "A fast quantum mechanical algorithm for database search," in Proc. 28th Annual ACM Symposium on the Theory of Computing, pp. 212-219, Philadelphia, PA, USA, 22-24 May 1996.
[6] A. Barenco, et al., "Elementary gates for quantum computation," Physical Review A, vol. 52, no. 5, pp. 3457-3467, Nov. 1995.
[7] G. Cybenko, "Reducing quantum computations to elementary unitary operations," Computing in Science and Engineering, vol. 3, no. 2, pp. 27-32, Mar./Apr. 2001.
[8] V. V. Shende, I. L. Markov, and S. S. Bullock, "Minimal universal two-qubit quantum circuits," Physical Review A, vol. 69, pp 062321-062329, Jub. 2004.
[9] M. Mottonen, J. J. Vartiainen, V. Bergholm, and M. M. Salomaa, "Quantum circuits for general multiqubit gates," Physical Review Letters, vol. 93, p. 130502, Sep. 2004.
[10] 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.
[11] 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.
[12] A. M. Steane, "Error correcting codes in quantum theory," Phys. Rev. Lett., vol. 77, no. 5, pp. 793-797, Jul. 1996.
[13] 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.
[14] G. D. Forney, M. Grassl, S. Guha, "Convolutional and tail-biting quantum error-correcting codes," IEEE Trans. on Information Theory, vol. 53, no. 3, pp. 865-880, Mar. 2007.
[15] M. Houshmand, S. Hosseini-Khayat, and M. M. Wilde, "Minimal-memory, non-catastrophic, polynomial-depth quantum convolutional encoders," IEEE Trans. on Information Theory, vol. 59, no. 2, pp. 1198-1210, Feb. 2013.
[16] 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.
[17] B. Giles and P. Selinger, "Exact synthesis of multiqubit clifford+T circuits," Physical Review A, vol. 87, no. 3, p. 032332, Mar. 2013.
[18] C. Lin and A. Chakrabarti, "FTQLS: fault-tolerant quantum logic synthesis," IEEE Trans. on VLSI Systems, vol. 22, no. 6, pp. 1350-1363, Jun. 2014.
[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] R. Wille, M. Saeedi, and R. Drechsler, "Synthesis of reversible functions beyond gate count and quantum cost," in Proc. 18th Int. Workshop on Logic and Synthesis, pp. 43-49, Aug. 2009.
[21] M. Mohammadi and M. Eshghi, "On figures of merit in reversible and quantum logic designs," Quantum Information Processing, vol. 8, no. 4, pp. 297-318, Aug. 2009.
[22] M. Saeedi and I. L. Markov, "Synthesis and optimization of reversible circuits-a survey," ACM Computing Surveys (CSUR), vol. 45, no. 2, 34 pp., 2013.
[23] E. P. Chong and S. H. Zak, An Introduction to Optimization, 4th Ed. Wiley, 2013.
[24] V. V. Shende, I. L. Markov, and S. S. Bullock, "Smaller two-qubit circuits for quantum communication and computation," Design Automation and Test in Europe, pp. 980-985, Feb. 2004.