# zbMATH — the first resource for mathematics

Reducing the number of ancilla qubits and the gate count required for creating large controlled operations. (English) Zbl 1311.81074
Summary: In this paper, we show that it is possible to adapt a qudit scheme for creating a controlled-Toffoli created by T. C. Ralph, K. J. Resch and A. Gilchrist [“Efficient Toffoli gates using qudits”, Phys. Rev. A 75, No. 2, Article ID 022313, 5 p. (2007; doi:10.1103/PhysRevA.75.022313)] to be applicable to qubits. While this scheme requires more gates than standard schemes for creating large controlled gates, we show that with simple adaptations, it is directly equivalent to the standard scheme in the literature. This scheme is the most gate-efficient way of creating large controlled unitaries currently known; however, it is expensive in terms of the number of ancilla qubits used. We go on to show that using a combination of these standard techniques presented by A. Barenco et al. [“Elementary gates for quantum computation”, Phys. Rev. A 52, No. 5, 3457–3467 (1995; doi:10.1103/PhysRevA.52.3457)], we can create an $$n$$-qubit version of the Toffoli using less gates and the same number of ancilla qubits as recent work using computer optimization. This would be useful in any architecture of quantum computing where gates are cheap but qubit initialization is expensive.
##### MSC:
 81P68 Quantum computation 81P15 Quantum measurement theory, state operations, state preparations 68Q12 Quantum algorithms and complexity in the theory of computing
RevLib
Full Text:
##### References:
 [1] Shor, PW, Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer, SIAM J. Comput., 26, 1484, (1997) · Zbl 1005.11065 [2] Daskin, A; Kais, S, Decomposition of unitary matrices for finding quantum circuits: application to molecular Hamiltonians, J. Chem. Phys., 134, 144112, (2011) [3] Wang, H., Kais, S., Äsp$$\check{\rm {u}}$$rû Gŭzík, A., Hoffmann, M.R.: Quantum algorithm for obtaining the energy spectrum of molecular systems. Phys. Chem. Chem. Phys. 10(35), 5388 (2008). doi:10.1039/b804804e [4] Childs, A.M., Cleve, R., Deotto, E., Farhi, E., Gutmann, S., Spielman, D.A.: Exponential algorithmic speedup by a quantum walk. In: Proceedings of the Thirty-Fifth Annual ACM Symposium on Theory of Computing (ACM, New York, NY, USA, 2003), STOC ’03, pp. 59-68 (2003). doi:10.1145/780542.780552 · Zbl 1192.81059 [5] Barenco, A; Bennett, CH; Cleve, R; DiVincenzo, DP; Margolus, N; Shor, P; Sleator, T; Smolin, JA; Weinfurter, H, Complete methods set for scalable ion trap quantum information processing, Phys. Rev. A, 52, 3457, (1995) [6] Nielsen, M., Chuang, I.: Quantum Computation and Quantum Information. Cambridge University Press, Cambridge (2000) · Zbl 1049.81015 [7] Maslov, D; Dueck, G, Improved quantum cost for n-bit Toffoli gates, Electron. Lett., 39, 1790, (2003) [8] Maslov, D., Young, C., Miller, D., Dueck, G.: Quantum circuit simplification using templates. In: Design, Automation and Test in Europe, 2005. Proceedings, vol. 2, pp. 1208-1213 (2005). doi:10.1109/DATE.2005.249 [9] Scott, N.O., Dueck, G.W.: Pairwise decomposition of toffoli gates in a quantum circuit. In: Proceedings of the 18th ACM Great Lakes symposium on VLSI (ACM, New York, NY, USA, 2008), GLSVLSI ’08, pp. 231-236 (2008). doi:10.1145/1366110.1366168 [10] Wille, R., Grosse, D., Teuber, L., Dueck, G., Drechsler, R.: RevLib: an online resource for reversible functions and reversible circuits. In: Multiple Valued Logic, 2008. ISMVL 2008. 38th International Symposium on, pp. 220-225 (2008). doi:10.1109/ISMVL.2008.43 [11] Miller, D.M.: Lower cost quantum gate realizations of multiple-control Toffoli gates. In: IEEE Pacific Rim Conference on Communications, Computers and Signal Processing, 2009. 308-313 (2009). doi:10.1109/PACRIM.2009.5291355 [12] Miller, D.M., Wille, R., Sasanian, Z.: Elementary quantum gate realizations for multiple-control Toffoli gates. In: 41st IEEE International Symposium on Multipe-Valued Logic, pp. 288-293 (2011). doi:10.1109/ISMVL.2011.54 [13] Ralph, TC; Resch, KJ; Gilchrist, A, Efficient Toffoli gates using qudits, Phys. Rev. A, 75, 022313, (2007) [14] Lanyon, BP; Barbieri, M; Almeida, MP; Jennewein, T; Ralph, TC; Resch, KJ; Pryde, GJ; O’Brien, JL; Gilchrist, A; White, AG, Simplifying quantum logic using higher-dimensional Hilbert spaces, Nat. Phys., 5, 134, (2008) [15] Shende, V.V., Markov, I.L.: On the CNOT-cost of TOFFOLI gates. Quant. Inf. Comput. 9, 461 (2009). http://arxiv.org/abs/0803.2316 · Zbl 1170.81019 [16] Margolus, N.: Simple quantum gates. unpublished manuscript c. (1994) [17] DiVincenzo, D.P.: Quantum gates and circuits. In: Proceedings of the Royal Society of London. Series A: Mathematical, Physical and Engineering Sciences 454(1969), 261 (1998). doi:10.1098/rspa.1998.0159 · Zbl 0919.68040 [18] Peres, A, Reversible logic and quantum computers, Phys. Rev. A, 32, 3266, (1985) [19] Gosset, D., Kliuchnikov, V., Mosca, M., Russo, V.: An algorithm for the T-count. Quant. Inf. Comput. 14, 15-16 (2014). http://arxiv.org/abs/1308.4134
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.