Dependencies

For a \(1\)-qubit unitary \(U\), there exists a product of at most four elements of \(G_2 \setminus G_1\) and any number of elements of \(G_1\) that equals \(CC(U)\) if and only if either the eigenvalues of \(U\) are equal or \(\det (U) = 1\).

Suppose \(u_0, u_1\) are complex numbers with \(|u_0| = |u_1| = 1\). An \(8 \times 8\) unitary \(U\) commutes with \(\operatorname {Diag}(u_0, u_1) \otimes I_2 \otimes I_2\) if and only if either \(u_0 = u_1\) or \(U = |0\rangle \langle 0| \otimes V_{00} + |1\rangle \langle 1| \otimes V_{11}\) for some \(4 \times 4\) unitaries \(V_{00}, V_{11}\).

Suppose \(u_0, u_1\) are complex numbers with \(|u_0| = |u_1| = 1\). There exist \(2 \times 2\) unitaries \(P, Q\) such that the eigenvalues of \(P \otimes Q\) are \(\{ 1, 1, u_0, u_1\} \) (as a multiset, up to permutation) if and only if either \(u_0 = u_1\) or \(u_0 u_1 = 1\).

Suppose \(u_0, u_1\) are complex numbers with \(|u_0| = |u_1| = 1\). There exist a \(2 \times 2\) unitary \(P\) and complex numbers \(c, d\) such that the eigenvalues of \((I_2 \otimes P) \cdot C(\operatorname {Diag}(u_0, u_1))\) are \(\{ c, c, d, d\} \) (each with multiplicity two) if and only if either \(u_0 = u_1\) or \(u_0 u_1 = 1\). Here \(C(\operatorname {Diag}(u_0, u_1))\) denotes the controlled-\(\operatorname {Diag}(u_0, u_1)\) gate.

Suppose \(u_0, u_1\) are complex numbers with \(|u_0| = |u_1| = 1\). There exist \(4 \times 4\) unitary matrices \(U, V\) and \(2 \times 2\) unitary matrices \(P_0, P_1, Q_0, Q_1\) such that

if and only if either \(u_0 = u_1\) or \(u_0 u_1 = 1\).

Suppose \(u_0, u_1\) are complex numbers with \(|u_0| = |u_1| = 1\). Suppose \(Q\) is a \(2 \times 2\) unitary and let \(|\beta \rangle = Q|0\rangle \) and \(|\beta ^\perp \rangle = Q|1\rangle \). There exist \(2 \times 2\) unitary matrices \(P_0, P_1\) such that

if and only if \(u_0 = 1\) and \(u_1 = 1\).

Suppose \(u_0, u_1\) are complex numbers with \(|u_0| = |u_1| = 1\). There exist \(4 \times 4\) unitary matrices \(V_1, V_2, V_3, V_4\) and \(2 \times 2\) unitary matrices \(P_0, P_1\), where \(V_1 = |0\rangle \langle 0| \otimes P_0 + |1\rangle \langle 1| \otimes P_1\), such that

if and only if either \(u_0 = u_1\) or \(u_0 u_1 = 1\).

Suppose \(u_0, u_1\) are complex numbers with \(|u_0| = |u_1| = 1\). There exist \(4 \times 4\) unitary matrices \(V_1, V_2, V_3, V_4\) and \(2 \times 2\) unitary matrices \(P_0, P_1\), where \(V_4 = |0\rangle \langle 0| \otimes P_0 + |1\rangle \langle 1| \otimes P_1\), such that

if and only if either \(u_0 = u_1\) or \(u_0 u_1 = 1\).

Suppose \(u_0, u_1\) are complex numbers with \(|u_0| = |u_1| = 1\). There exist \(2\)-qubit unitaries \(U_1, U_2, U_3, U_4\) such that \(U_1^{BC}\, U_2^{AC}\, U_3^{AB}\, U_4^{BC} = CC(\operatorname {Diag}(u_0, u_1))\) if and only if either \(u_0 = u_1\) or \(u_0 u_1 = 1\).

(Case analysis of a unitary.) For a 2-qubit unitary \(V\), either \(\exists |x\rangle : V(|x\rangle \otimes |0\rangle )\) is entangled, or \(\exists |\psi \rangle : \forall |x\rangle : \exists |z\rangle : V(|x\rangle \otimes |0\rangle ) = |z\rangle \otimes |\psi \rangle \), or \(\exists |\psi \rangle : \forall |x\rangle : \exists |z\rangle : V(|x\rangle \otimes |0\rangle ) = |\psi \rangle \otimes |z\rangle \).

Suppose \(u_0, u_1\) are complex numbers such that \(|u_0| = |u_1| = 1\). For 2-qubit unitaries \(U_1, W_2, V_3, U_4\), if

\(V_3(|0\rangle \otimes |0\rangle ) = |0\rangle \otimes |0\rangle \), and for any \(|x_A\rangle \): \(U_1^{AC}(|x_A\rangle \otimes |0_B\rangle \otimes |0_C\rangle ) = U_4^{BC\dagger }\, V_3^{AC\dagger }(|x_A\rangle \otimes |0_B\rangle \otimes |0_C\rangle )\), then either \(u_0 = u_1\) or \(u_0 u_1 = 1\) or there exist 2-qubit unitaries \(W_1, W_3, W_4\) and a 1-qubit unitary \(P_3\) such that

and \(W_3 = I \otimes |0\rangle \langle 0| + P_3 \otimes |1\rangle \langle 1|\).

Suppose \(u_0, u_1\) are complex numbers such that \(|u_0| = |u_1| = 1\). For 2-qubit unitaries \(V_1, V_2, V_3, V_4\), if

\(\exists |\psi \rangle : \forall |x\rangle : \exists |z\rangle : V_2(|x\rangle \otimes |0\rangle ) = |z\rangle \otimes |\psi \rangle \), and \(V_3(|0\rangle \otimes |0\rangle ) = |0\rangle \otimes |0\rangle \), then either \(u_0 = u_1\) or \(u_0 u_1 = 1\) or there exist 2-qubit unitaries \(W_1, W_2, W_3, W_4\) and 1-qubit unitaries \(P_1, P_2, P_3, P_4, Q\) such that

where \(|\beta \rangle = Q|0\rangle \) and \(|\beta ^\perp \rangle = Q|1\rangle \).

(The second main lemma.) Suppose \(u_0, u_1\) are complex numbers such that \(|u_0| = |u_1| = 1\). There exist 2-qubit unitaries \(U_1, U_2, U_3, U_4\) such that

if and only if either \(u_0 = u_1\) or \(u_0 u_1 = 1\).

Suppose \(u_0, u_1\) are complex numbers with \(|u_0| = |u_1| = 1\). For a \(2\)-qubit unitary \(W\) and a \(3\)-qubit unitary \(U\), if \(CC(\operatorname {Diag}(u_0, u_1)) = W^{AB} \cdot U\), then there exists a \(2\)-qubit unitary \(V\) such that \(CC(\operatorname {Diag}(1, u_0^* u_1)) = V^{AB} \cdot U\).

Suppose \(u_0, u_1\) are complex numbers with \(|u_0| = |u_1| = 1\). If there exists a product of at most four elements of \(G_2 \setminus G_1\) and any number of elements of \(G_1\) that equals \(CC(\operatorname {Diag}(u_0, u_1))\), then either:

1. there exist \(2\)-qubit unitaries \(U_1, U_2, U_3, U_4\) and \((u_2, u_3) \in R(u_0, u_1)\) such that \(U_1^{BC}\, U_2^{AC}\, U_3^{AB}\, U_4^{BC} = CC(\operatorname {Diag}(u_2, u_3))\), or

2. there exist \(2\)-qubit unitaries \(U_1, U_2, U_3, U_4\) and \((u_2, u_3) \in R(u_0, u_1)\) such that \(U_1^{AC}\, U_2^{BC}\, U_3^{AC}\, U_4^{BC} = CC(\operatorname {Diag}(u_2, u_3))\).

Suppose \(u_0, u_1\) are complex numbers with \(|u_0| = |u_1| = 1\). Suppose \((u_2, u_3) \in R(u_0, u_1)\). If \(u_2 = u_3\) or \(u_2 u_3 = 1\), then \(u_0 = u_1\) or \(u_0 u_1 = 1\).

The Toffoli gate has an exact decomposition into five two-qubit gates.

No exact decomposition of Toffoli uses at most four two-qubit gates.

Suppose \(u_0, u_1\) are complex numbers with \(|u_0| = |u_1| = 1\). There exists a product of at most four elements of \(G_2 \setminus G_1\) and any number of elements of \(G_1\) that equals \(CC(\operatorname {Diag}(u_0, u_1))\) if and only if either \(u_0 = u_1\) or \(u_0 u_1 = 1\).

Five two-qubit gates are necessary and sufficient to implement a Toffoli gate exactly.