Abstract
The matrices that can be exactly represented by a circuit over the Toffoli-Hadamard gate set are the orthogonal matrices of the form \(M/\sqrt{2}{}^k\), where M is an integer matrix and k is a nonnegative integer. The exact synthesis problem for this gate set is the problem of constructing a circuit for a given such matrix. Existing methods produce circuits consisting of \(O(2^n\log (n)k)\) gates, where n is the dimension of the matrix. In this paper, we provide two improved synthesis methods. First, we show that a technique introduced by Kliuchnikov in 2013 for Clifford+T circuits can be straightforwardly adapted to Toffoli-Hadamard circuits, reducing the complexity of the synthesized circuit from \(O(2^n\log (n)k)\) to \(O(n^2\log (n)k)\). Then, we present an alternative synthesis method of similarly improved cost, but whose application is restricted to circuits on no more than three qubits. Our results also apply to orthogonal matrices over the dyadic fractions, which correspond to circuits using the 2-qubit gate \(H\otimes H\), rather than the usual single-qubit Hadamard gate H.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
References
Aharonov, D.: A simple proof that Toffoli and Hadamard are quantum universal. arXiv preprint quant-ph/0301040 (2003)
Amy, M., Glaudell, A.N., Ross, N.J.: Number-theoretic characterizations of some restricted Clifford+T circuits. Quantum 4, 252 (2020)
Arute, F., et al.: Quantum supremacy using a programmable superconducting processor. Nature 574(7779), 505–510 (2019)
Cory, D.G., et al.: Experimental quantum error correction. Phys. Rev. Lett. 81(10), 2152 (1998)
Dalla Chiara, M.L., Ledda, A., Sergioli, G., Giuntini, R.: The Toffoli-Hadamard gate system: an algebraic approach. J. Philos. Log. 42, 467–481 (2013)
Fedorov, A., Steffen, L., Baur, M., da Silva, M.P., Wallraff, A.: Implementation of a Toffoli gate with superconducting circuits. Nature 481(7380), 170–172 (2012)
Forest, S., Gosset, D., Kliuchnikov, V., McKinnon, D.: Exact synthesis of single-qubit unitaries over Clifford-cyclotomic gate sets. J. Math. Phys. 56(8), 082201 (2015)
Fredkin, E., Toffoli, T.: Conservative logic. Int. J. Theor. Phys. 21(3–4), 219–253 (1982)
Gajewski, D.C.: Analysis of groups generated by quantum gates. Ph.D. thesis, University of Toledo (2009)
Giles, B., Selinger, P.: Exact synthesis of multiqubit Clifford+T circuits. Phys. Rev. A 87(3), 032332 (2013)
Gottesman, D.: Stabilizer codes and quantum error correction. California Institute of Technology (1997)
Kay, A.: Tutorial on the quantikz package. arXiv preprint arXiv:1809.03842 (2018)
Kliuchnikov, V.: Synthesis of unitaries with Clifford+T circuits. arXiv preprint arXiv:1306.3200 (2013)
Kliuchnikov, V., Maslov, D., Mosca, M.: Fast and efficient exact synthesis of single-qubit unitaries generated by Clifford and T gates. Quantum Inf. Comput. 13(7–8), 607–630 (2013)
Kliuchnikov, V., Yard, J.: A framework for exact synthesis. arXiv preprint arXiv:1504.04350 (2015)
Li, S.M., Ross, N.J., Selinger, P.: Generators and relations for the group \({O}_n(\mathbb{Z} [1/2])\). arXiv preprint arXiv:2106.01175 (2021)
Nielsen, M.A., Chuang, I.L.: Quantum computation and quantum information. Phys. Today 54(2), 60 (2001)
Niemann, P., Wille, R., Drechsler, R.: Advanced exact synthesis of Clifford+T circuits. Quantum Inf. Process. 19(9), 1–23 (2020)
Paetznick, A., Reichardt, B.W.: Universal fault-tolerant quantum computation with only transversal gates and error correction. Phys. Rev. Lett. 111(9), 090505 (2013)
Reed, M.D., DiCarlo, L., Nigg, S.E., Sun, L., Frunzio, L., Girvin, S.M., Schoelkopf, R.J.: Realization of three-qubit quantum error correction with superconducting circuits. Nature 482(7385), 382–385 (2012)
Russell, T.: The exact synthesis of 1- and 2-qubit Clifford+T circuits. arXiv preprint arXiv:1408.6202 (2014)
Shi, Y.: Both Toffoli and controlled-NOT need little help to do universal quantum computing. Quantum Inf. Comput. 3(1), 84–92 (2003)
Vilmart, R.: A ZX-calculus with triangles for Toffoli-Hadamard, Clifford\(+\)T, and beyond. In: Chiribella, G., Selinger, P. (eds.) 15th International Conference on Quantum Physics and Logic (QPL 2018), pp. 313–344. Electronic Proceedings in Theoretical Computer Science (EPTCS 287), Halifax, Canada (2018). https://doi.org/10.4204/EPTCS.287.18. arXiv:1804.03084pdf
Vilmart, R.: Completeness of sum-over-paths for Toffoli-Hadamard and the dyadic fragments of quantum computation. In: Klin, B., Pimentel, E. (eds.) 31st EACSL Annual Conference on Computer Science Logic (CSL 2023). Leibniz International Proceedings in Informatics (LIPIcs), vol. 252, pp. 36:1–36:17. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, Dagstuhl, Germany (2023). https://doi.org/10.4230/LIPIcs.CSL.2023.36, https://drops.dagstuhl.de/opus/volltexte/2023/17497
Yoder, T.J.: Universal fault-tolerant quantum computation with Bacon-Shor codes. arXiv preprint arXiv:1705.01686 (2017)
Zhu, Q., et al.: Quantum computational advantage via 60-qubit 24-cycle random circuit sampling. Sci. Bull. 67(3), 240–245 (2022)
Acknowledgement
Part of this research was carried out during SML’s undergraduate honours work at Dalhousie University. The authors would like to thank Jiaxin Huang and John van de Wetering for enlightening discussions. The circuit diagrams in this paper were typeset using Quantikz [12].
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
A Proof of Proposition 7
A Proof of Proposition 7
Proposition 7. Let \(U\in \mathcal {L}_{8}\) with \({\text {lde}}_{\sqrt{2}}(U)\ge 2\). Then up to row permutation, column permutation, and taking the transpose, \(\overline{U}\) is one of the 14 binary patterns in Fig. 1.
Proof
Let \(u_i\) denote the i-th column of U, and \(u_i^\dagger \) denote the the i-th row of U, \(0 \le i < 8\). Let \(\Vert v \Vert \) denote the hamming weight of v, where v is a string of binary bits. Proceed by case distinctions.
Case 1. There are identical rows or columns in U. Up to transposition, suppose U has two rows that are identical. By Proposition 13, \(U \in \mathcal {B}_0\) up to permutation.
Case 2. There are no identical rows or columns in U. By Proposition 14, \(U \in \mathcal {B}_1\) up to permutation.
\(\square \)
1.1 A.1 Binary Patterns that are Either Row-Paired or Column-Paired
Definition 14
We define the set \(\mathcal {B}_0\) of binary matrices as \(\mathcal {B}_0 = \{A,B,C,D,E,\) \(F,G,H,I,J,K\}\), where
Proposition 13
Let \(U \in \mathbb {Z}_2^{8 \times 8}\). Suppose U satisfies Lemmas 6 and 5. If U has two rows that are identical, then \(U \in \mathcal {B}_0\) up to permutation and transposition.
Case distinction for \(\Vert u_0^\dagger \Vert = \Vert u_1^\dagger \Vert = 8\).
Case distinction for \(\Vert u_0^\dagger \Vert = \Vert u_1^\dagger \Vert = 4\).
Proof
Let \(u_i\) denote the i-th column of U, and \(u_i^\dagger \) denote the i-th row of U, \(0 \le i < 8\). Let \(\Vert v \Vert \) denote the hamming weight of v, where v is a string of binary bits. Up to permutation, suppose \(\Vert u_0^\dagger \Vert = \Vert u_1^\dagger \Vert \). By Lemma 5, \(\Vert u_0^\dagger \Vert = 8\) or \(\Vert u_0^\dagger \Vert = 4\). Proceed by case distinctions, we summarized the derivation of binary patterns in Fig. 2 and Fig. 3.
Case 1. \(\Vert u_0^\dagger \Vert = \Vert u_1^\dagger \Vert = 8\).
Subcase 1.1. \(\Vert u_0 \Vert = 8\).
Subcase 1.1.1. \(\Vert u_1 \Vert = 8\).
Subcase 1.1.1.1. \(\Vert u_2 \Vert = 8\).
Subcase 1.1.1.1.1. \(\Vert u_3 \Vert = 8\).
Subcase 1.1.1.1.1.1. \(\Vert u_4 \Vert = 8\), then
Subcase 1.1.1.1.1.2. \(\Vert u_4 \Vert = 4\), then
Subcase 1.1.1.1.2. \(\Vert u_3 \Vert = 4\). Let (x, y) be a pair of the entries in the i-th column of rows 2 and 3 as shown below, for \(4 \le i < 8\). By Lemma 6 with \(u_3\), \(x=y\). Hence \( u_2^\dagger = u_3 ^\dagger \).
Subcase 1.1.1.1.2.1. \(\Vert u_2^\dagger \Vert = 8\), then
Subcase 1.1.1.1.2.2. \(\Vert u_2^\dagger \Vert = 4\), then
Note that rows 3 and 4 violate Lemma 6, so this case is not possible.
Subcase 1.1.1.2. \(\Vert u_2 \Vert = 4\). Let (x, y) be a pair of the entries in the i-th column of rows 2 and 3 as shown below, for \(3 \le i < 8\). By Lemma 6 with \(u_2\), \(x=y\). Hence \( u_2^\dagger = u_3 ^\dagger \).
Subcase 1.1.1.2.1.
By Lemma 5 for rows 5, 6, and 7, we have
Subcase 1.1.1.2.2. \(\Vert u_2^\dagger \Vert = 4\), then up to column permutation,
Subcase 1.1.2. \(\Vert u_1 \Vert = 4\). Let (x, y) be a pair of the entries in the i-th column of rows 2 and 3 as shown below, for \(2 \le i < 8\). By Lemma 6 with \(u_1\), \(x=y\). Hence \( u_2^\dagger = u_3^\dagger \).
Subcase 1.1.2.1. \(\Vert u_2^\dagger \Vert = 8\), then
Subcase 1.1.2.2. \(\Vert u_2^\dagger \Vert = 4\). By Lemma 6 with row 3, for \(u_2\) and \(u_3\), precisely one of them has hamming weight 8, and the other has hamming weight 4. Up to column permutation, let \(\Vert u_2 \Vert = 8\) and \(\Vert u_3 \Vert = 4\).
Subcase 1.2. \(\Vert u_0 \Vert = 4\). Let (x, y) be a pair of the entries in the i-th column of rows 2 and 3 as shown below, for \(1 \le i < 8\). By Lemma 6 with \(u_0\), \(x=y\). Hence \( u_2^\dagger = u_3^\dagger \).
Subcase 1.2.1. \(\Vert u_2^\dagger \Vert = 8\). By Lemma 5, \(\Vert u_4^\dagger \Vert = 4\) or \(\Vert u_4^\dagger \Vert = 0\). Then we have
Subcase 1.2.1.1. \(\Vert u_4^\dagger \Vert = 4\), then
Subcase 1.2.1.2. \(\Vert u_4^\dagger \Vert = 0\), then
Subcase 1.2.2. \(\Vert u_2^\dagger \Vert = 4\), then the binary matrix is shown below. By Lemma 6, there can be two cases: precisely two of \(\{u_1, u_2, u_3\}\) have hamming weight 8, or all of \(\{u_1, u_2, u_3\}\) have hamming weight 4.
Subcase 1.2.2.1. Up to column permutation, let \(\Vert u_1 \Vert = \Vert u_2 \Vert = 8\) and \(\Vert u_3 \Vert = 4\).
Subcase 1.2.2.2.\( \Vert u_1 \Vert = \Vert u_2 \Vert = \Vert u_3 \Vert = 4\).
Case 2. \(\Vert u_0^\dagger \Vert = \Vert u_1^\dagger \Vert = 4\).
Subcase 2.1. \(\Vert u_0 \Vert = 8\).
Subcase 2.1.1. \(\Vert u_1 \Vert = 8\).
Subcase 2.1.1.1. \(\Vert u_2 \Vert = 8\), then
Subcase 2.1.1.1.1. \(\Vert u_2^\dagger \Vert = 8\), then
Subcase 2.1.1.1.2. \(\Vert u_2^\dagger \Vert = 4\). By Lemma 5, there can be two cases: precisely four of \(\{u_3^\dagger ,u_4^\dagger ,u_5^\dagger ,u_6^\dagger ,u_7^\dagger \}\) have hamming weight 8, or all of \(\{u_3^\dagger ,u_4^\dagger ,u_5^\dagger ,u_6^\dagger ,u_7^\dagger \}\) have hamming weight 4.
Subcase 2.1.1.1.2.1. Up to row permutation, \(\Vert u_3^\dagger \Vert = \Vert u_4^\dagger \Vert = \Vert u_5^\dagger \Vert = \Vert u_6^\dagger \Vert = 8\).
Subcase 2.1.1.1.2.2. \(\Vert u_3^\dagger \Vert = \Vert u_4^\dagger \Vert = \Vert u_5^\dagger \Vert = \Vert u_6^\dagger \Vert = \Vert u_7^\dagger \Vert =4\).
Subcase 2.1.1.2. \(\Vert u_2 \Vert = 4\). Let (x, y) be a pair of the entries in the i-th column of rows 2 and 3 as shown below, for \(3 \le i < 8\). By Lemma 6 with \(u_3\), \(x=y\). Hence \( u_2^\dagger = u_3 ^\dagger \).
Subcase 2.1.1.2.1. \(\Vert u_2^\dagger \Vert = 8\), then
Subcase 2.1.1.2.2. \(\Vert u_2^\dagger \Vert = 4\), then
Subcase 2.1.2. \(\Vert u_1 \Vert = 4\). Let x, y, z, w be the entries in U as shown below. By Lemma 6 with row 1, \(x=y\) and \(z=w\). By Lemma 6 with column 1, \(x=z\) and \(y=w\). Hence \(x=y=z=w\). Moreover, since (x, z) can be any pair of the entries coming from any column i of rows 2 and 3, for \(2 \le i < 8\), we have \(u_2^\dagger = u_3^\dagger \).
Subcase 2.1.2.1. \(x=y=z=w=1\), then
Subcase 2.1.2.1.1. \(\Vert u_2^\dagger \Vert = 8\), then
Subcase 2.1.2.1.2. \(\Vert u_2^\dagger \Vert = 4\), then
Subcase 2.1.2.2. \(x=y=z=w=0\), then we have what follows.
Let (x, y) be a pair of the entries in the i-th column of rows 4 and 5 as shown below, for \(4 \le i < 8\). By Lemma 6 with \(u_2\), \(x=y\). Hence \( u_4^\dagger = u_5^\dagger \).
Subcase 2.2. \(\Vert u_0 \Vert = 4\). Let (x, y) be a pair of the entries in the i-th column of rows 2 and 3 as shown below, for \(1 \le i < 8\). By Lemma 6 with \(u_0\), \(x=y\). Hence \( u_2^\dagger = u_3^\dagger \). By Lemma 6 with \(u_0^\dagger \), there must be oddly many 1’s in \(\{x,z,w\}\). Up to column permutation, consider the following two cases: \(x=z=w=1\) or \(x=1\), \(z=w=0\).
Subcase 2.2.1. \(x=z=w=1\), we have
Subcase 2.2.1.1. \(\Vert u_2^\dagger \Vert = 8\), then
By Lemma 6 with \(u_0^\dagger \), there must be evenly many columns among \(\{u_0,u_1,u_2,u_3\}\) that have hamming weight 8. Since \(\Vert u_0 \Vert = 4\), up to column permutation, there can be two cases.
Subcase 2.2.1.1.1. \(\Vert u_1 \Vert = \Vert u_2 \Vert = 8\) and \(\Vert u_3 \Vert = 4\).
Subcase 2.2.1.1.2. \(\Vert u_1 \Vert = \Vert u_2 \Vert = \Vert u_3 \Vert = 4\).
Subcase 2.2.1.2. \(\Vert u_2^\dagger \Vert = 4\), then
By Lemma 6 with \(u_0^\dagger \), there must be evenly many columns among \(\{u_0,u_1,u_2,u_3\}\) that have hamming weight 8. Since \(\Vert u_0 \Vert = 4\), up to column permutation, there can be two cases.
Subcase 2.2.1.2.1. \(\Vert u_1 \Vert = \Vert u_2 \Vert = 8\) and \(\Vert u_3 \Vert = 4\).
Subcase 2.2.1.2.2. \(\Vert u_1 \Vert = \Vert u_2 \Vert = \Vert u_3 \Vert = 4\). Depending on the hamming weight of \(u_4^\dagger \), consider what follows.
Subcase 2.2.1.2.2.1. \(\Vert u_4^\dagger \Vert = 4\), then
Subcase 2.2.1.2.2.2. \(\Vert u_4^\dagger \Vert = 0\), then
Subcase 2.2.2. \(x=1\), \(z=w=0\), we have
Subcase 2.2.2.1. \(\Vert u_1 \Vert = 8\), then we have what follows.
Let (x, y) be a pair of the entries in the i-th column of rows 4 and 5 as shown above, for \(4 \le i < 8\). By Lemma 6 with \(u_2\), \(x=y\). Hence \( u_4^\dagger = u_5 ^\dagger \).
Subcase 2.2.2.2. \(\Vert u_1 \Vert = 4\), then
Let (x, y) be a pair of the entries in the i-th column of rows 4 and 5 as shown above, for \(3 \le i < 8\). By Lemma 6 with \(u_2\), \(x=y\). Hence \( u_4^\dagger = u_5^\dagger \). Moreover, by Lemma 6 with \(u_0^\dagger \), we have
By Lemma 6 with \(u_2^\dagger \), \(x=z\) and \(y=w\). Since \(x=y\) and \(z=w\), \(x=y=z=w\).
Subcase 2.2.2.2.1. \(x=y=z=w=1\)
Subcase 2.2.2.2.2. \(x=y=z=w=0\).
\(\square \)
1.2 A.2 Binary Patterns that are neither Row-paired nor Column-paired
Definition 15
We define the set \(\mathcal {B}_1\) of binary matrices as \(\mathcal {B}_1 = \{L,M,N\}\), where
Proposition 14
Let \(U \in \mathbb {Z}_2^{8 \times 8}\). Suppose U satisfies Lemmas 6 and 5. If there are no identical rows nor columns in U, then \(U \in \mathcal {B}_1\) up to permutation and transposition.
Proof
Let \(u_i\) denote the i-th column of U, and \(u_i^\dagger \) denote the i-th row of U, \(0 \le i < 8\). Let \(\Vert v \Vert \) denote the hamming weight of v, where v is a string of binary bits. Since there are no identical rows nor columns in U, we proceed by case distinctions on the maximum hamming weight of a row vector in U.
Case 1. There is a row with hamming weight 8. Up to row permutation, \(\Vert u_0^\dagger \Vert = 8\).
Subcase 1.1. There is a row with hamming weight 0. Up to row permutation, \(\Vert u_1^\dagger \Vert = 0\).
Note that \(u_0 = u_1\), but it contradicts our assumption that there are no identical columns in U. Thus this case is not possible.
Subcase 1.2. There is no row with hamming weight 0. Up to row and column permutation, consider
Subcase 1.2.1. There is a column with hamming weight 8, consider
Subcase 1.2.2. There is no column whose hamming weight is 8. Up to row and column permutation, consider
Note that \(u_0 = u_1\), but it contradicts our assumption that there are no identical columns in U. Thus this case is not possible.
Case 2. There is no row with hamming weight 8. Up to row and column permutation, \(\Vert u_0^\dagger \Vert = 4\).
Subcase 2.1. There is a column with hamming weight 8, consider
Note that \(u_0^\dagger = u_3^\dagger \), but it contradicts our assumption that there are no identical rows in U. Thus this case is not possible.
Subcase 2.2. There is no column with hamming weight 8, consider
Subcase 2.2.1. \(x = 1\)
Subcase 2.2.2. \(x = 0\)
Hence, when there are no identical rows nor columns in U, \(U \in \mathcal {B}_1\) up to permutation. \(\square \)
Rights and permissions
Copyright information
© 2023 The Author(s), under exclusive license to Springer Nature Switzerland AG
About this paper
Cite this paper
Amy, M., Glaudell, A.N., Li, S.M., Ross, N.J. (2023). Improved Synthesis of Toffoli-Hadamard Circuits. In: Kutrib, M., Meyer, U. (eds) Reversible Computation. RC 2023. Lecture Notes in Computer Science, vol 13960. Springer, Cham. https://doi.org/10.1007/978-3-031-38100-3_12
Download citation
DOI: https://doi.org/10.1007/978-3-031-38100-3_12
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-031-38099-0
Online ISBN: 978-3-031-38100-3
eBook Packages: Computer ScienceComputer Science (R0)