Since $T^{|k\rangle}_{|l\rangle}$ is built from the Pauli gate $X$ and the Toffoli gates $T^{(n)}_k$ (as in Figure 2), it is enough to show that each $T^{(n)}_k$ can be built from CNOT and 1-gates. By the symmetry of wire switching, it is therefore even enough to show that each Toffoli $n$-gate (see the figure for $n=4$) can be built from CNOT and 1-gates.
If $n \ge 4$, there is a quantum circuit, with $n-3$ ancillary qubits and consisting only of Toffoli 3-gates, to compute the Toffoli $n$-gate.
Proof. One verifies, by computing the outputs for each computational basis state input, that the following circuit computes the Toffoli 4-gate:
If $n > 4$, we insert after the first Toffoli 3-gate another Toffoli 3-gate with control qubits $|i_3\rangle$ and the first ancillary qubit, and with target qubit the second ancillary qubit; and if $n > 5$, we insert after the last one another Toffoli 3-gate with control qubits $|i_4\rangle$ and the second ancillary qubit, and with target qubit the third ancillary qubit; etc. The last Toffoli 3-gate is the one with control qubits $|i_{n-1}\rangle$ and the last ancillary qubit, and with target qubit $|i_n\rangle$. $\qed$
By Lemma 1, we only need to build the Toffoli 3-gate from CNOT and 1-gates.
Let $U$ be a 1-gate. Then we can build the 3-gate c-c-$U^2$ using only 1-gates and CNOT.
Proof. One verifies, by computing the outputs for each computational basis state input, that the following circuit computes c-c-$U^2$:
By Corollary 4.2.1 of the book, both c-$U$ and c-$U^\dagger$ can, in turn, be built using only 1-gates and CNOT. This proves the lemma. $\qed$
There exists a 1-gate $U$ such that $U^2 = X$.
Proof. Direct computation shows that we can take $U = \frac12\begin{pmatrix} 1+i & 1-i \\ 1-i & 1+i \end{pmatrix}$. $\qed$
We denote the 1-gate obtained in Problem 11 as $\sqrt{X}$. Since the Toffoli 3-gate is just c-c-$X$, we conclude:
The Toffoli 3-gate can be built using $\sqrt{X}$ and CNOT. $\qed$
Combining the corollary with Lemma 1 and this post, we have now proved the following special case of Theorem 4.4.3 of the book:
Every $n$-gate can be built from 1-gates and CNOT. $\qed$
]]>The goal of this post is to prove that $U$ can be designed using only Toffoli gates and gates of the form $(I_{n} \otimes A)$, for various 1-gates $A$. By this post, we only need to show that $U$ can be designed using Toffoli gates and controlled gates c$_n$-$A$, for various 1-gates $A$.
Assume that $a_{21} \ne 0$, and set $$V:= \frac1{\sqrt{a_{11}\bar{a_{11}} + a_{21}\bar{a_{21}}}} \begin{pmatrix}
\bar{a_{11}} & \bar{a_{21}} \\ a_{21} & -a_{11}
\end{pmatrix}.$$
Then:
Proof. Part 1 is left as an exercise. Part 2 follows from the observation that $$\text{c}_n\text{-}V = \begin{pmatrix} V & 0 \\ 0 & I_{2^{n+1}-2} \end{pmatrix}$$ in block form. $\qed$
Assume that $a_{31} \ne 0$, and set $$V:= \frac1{\sqrt{a_{11}\bar{a_{11}} + a_{31}\bar{a_{31}}}} \begin{pmatrix}
\bar{a_{11}} & \bar{a_{31}} \\ a_{31} & -a_{11}
\end{pmatrix}.$$
Then:
Proof. Multiplying c$_n$-$V$ on the right by $T^{|1\rangle}_{|2\rangle}$ exchanges the 2nd and 3rd columns of c$_n$-$V$, while multiplying it on the left by the same matrix exchanges the 2nd and 3rd rows of c$_n$-$V$. So $$T^{|1\rangle}_{|2\rangle}(\text{c}_n\text{-}V)T^{|1\rangle}_{|2\rangle} = \begin{pmatrix} \frac{\bar{a_{11}}}{\sqrt{a_{11}\bar{a_{11}} + a_{31}\bar{a_{31}}}} & 0 & \frac{\bar{a_{31}}}{\sqrt{a_{11}\bar{a_{11}} + a_{31}\bar{a_{31}}}} & 0 & \cdots \\ 0 & 1 & 0 & 0 & \cdots \\ \frac{a_{31}}{\sqrt{a_{11}\bar{a_{11}} + a_{31}\bar{a_{31}}}} & 0 & \frac{-a_{11}}{\sqrt{a_{11}\bar{a_{11}} + a_{31}\bar{a_{31}}}} & 0 & \cdots \\ \\ 0 & 0 & 0 && I_{2^{n+1}-3} \end{pmatrix};$$ Lemma 2 now follows arguing as in the proof of Lemma 1. $\qed$
Replacing 3 in the previous lemma by any $k \in \{2, \dots, 2^{n+1}\}$ and arguing along the same lines, we obtain the following:
Assume that $a_{k1} \ne 0$, and set $$V:= \frac1{\sqrt{a_{11}\bar{a_{11}} + a_{k1}\bar{a_{k1}}}} \begin{pmatrix}
\bar{a_{11}} & \bar{a_{k1}} \\ a_{k1} & -a_{11}
\end{pmatrix}.$$
Then:
To simplify phrasing, we call an $(n+1)$-gate simple if it is the product of Toffoli gates and controlled 1-gates c$_n$-$A$, for various $A$. (So we are trying to show that every $(n+1)$-gate is simple.)
There are a simple $(n+1)$-gate $U_1$ and a unitary $((2^n-1) \times (2^n-1))$-matrix $V$ such that $$U_1 U = \begin{pmatrix} 1 & 0 \\ 0 & V \end{pmatrix}$$ in block form.
Proof. For each $k \in \{2, \dots, 2^{n+1}\}$, we choose a simple $(n+1)$-gate $U_{1,k}$ by induction on $k$ as follows:
Our choice of each $U_{1,k}$ and Lemma 3 imply that there are a positive real number $b_{11} > 0$ and complex numbers $b_{12}, \dots, b_{1,2^n}$ and a $((2^n-1) \times (2^n-1))$-matrix $V$ such that $$U_{1,2^n} \cdots U_{1,2} \cdot U = \begin{pmatrix} b_{11} & b_{12} & \cdots & b_{1,2^n} \\ 0 \\ \vdots && V \\ 0 \end{pmatrix}.$$ However, each $U_{1,k}$ is unitary, and since products of unitary operators are again unitary, the gate $U_{1,2^n} \cdots U_{1,2} \cdot U$ is unitary; in particular, its first column is a unit vector. Since the only nonzero entry in the first column is the positive real number $b_{11}$, it follows that $b_{11} = 1$. Since the first row is also a unit vector, we then have $$1+ b_{12}\bar{b_{12}} + \cdots + b_{1,2^n}\bar{b_{1,2^n}} = 1;$$ since $b_{1k}\bar{b_{1k}} \ge 0$ for each $k$, it follows that $b_{1k}\bar{b_{1k}} = 0$, that is, $b_{1k} = 0$, for each $k$. This, in turn, implies that $V$ is also unitary, so the proposition is proved. $\qed$
Our proof of Proposition 1 and Lemma 3 also shows the following: if $k \ge 2$ is such that $a_{1k} = 0$, then the matrices $U$ and $U_1U$ have the same entries in the $k$-th row. This observation suggests how we can replace the second row and column in $U_1U$ by $\begin{pmatrix} 0 & 1 & 0 & \cdots & 0\end{pmatrix}$ and its transpose:
In other words, there is a simple gate $U_2’$ such that the matrix $T^{|1\rangle}_{|0\rangle}U_2’T^{|1\rangle}_{|0\rangle} U_1 U T^{|1\rangle}_{|0\rangle}T^{|1\rangle}_{|0\rangle}$ has block form $\begin{pmatrix} I_2 & 0 \\ 0 & V \end{pmatrix}$, for some unitary $((2^{n+1}-2) \times (2^{n+1}-2))$-matrix $V$. Since $T^{|1\rangle}_{|0\rangle}$ is its own inverse, it follows that there are a simple gate $U_2$ (namely, the gate $T^{|1\rangle}_{|0\rangle}U_2’T^{|1\rangle}_{|0\rangle}$ above) and a unitary $((2^{n+1}-2) \times (2^{n+1}-2))$-matrix $V$ such that $$U_2U_1U = \begin{pmatrix} I_2 & 0 \\ 0 & V \end{pmatrix}$$ in block form.
Iterating this last procedure for each $k \in \{2, \dots, 2^{n+1}\}$, using the respective Toffoli gate $T^{|k-1\rangle}_{|0\rangle}$, we obtain the following:
There are simple $(n+1)$-gates $U_1, \dots, U_{2^{n+1}-1}$ such that $\ U_{2^{n+1}-1} \cdots U_1 \cdot U = I_{2^{n+1}}$. $\qed$
Exercise: Show that a product of simple gates is a simple gate, and that the multiplicative inverse of a simple gate is a simple gate. [Hint question: what is the multiplicative inverse of a c$_n$-$A$ gate?]
Combining Proposition 2 with the previous exercise, we achieve our goal:
The gate $\ U$ is simple. $\qed$
]]>Assume from now on that $U$ is a $1$-gate. We define the $(n+1)$-gate c$_n$-$U$ by induction on $n$ as follows:
Here is the c$_3$-$U$ gate:
Example: from the figure above with $X = U$, we get that c$_n$-$X = T^{(n+1)}_1$.
The goal of this post is to show that every c$_n$-$U$ gate can be designed using only c$_n$-$X$ and gates of the form $I_n \otimes A$, where $A$ is a 1-gate.
For a matrix $A$ and nonzero $k \in \NN$, we define $A^{\otimes k}$ by induction on $k$ as follows:
$$\text{c}_n\text{-}U = |0\rangle\langle0| \otimes I_n + |1\rangle\langle 1| \otimes |0\rangle\langle 0| \otimes I_{n-1} + \cdots + |1\rangle\langle 1|^{\otimes (n-1)} \otimes |0\rangle\langle 0| \otimes I_1 + |1\rangle\langle 1|^{\otimes n} \otimes U.$$
Proof. By induction on $n$; the case $n=1$ is this lemma. So assume that $n>1$ and Lemma 1 holds with $n-1$ in place of $n$ (inductive hypothesis). Then
$$\text{c}_n\text{-}U = \text{c-(c}_{n-1}\text{-}U) = |0\rangle\langle 0| \otimes I_n + |1\rangle\langle 1| \otimes (\text{c}_{n-1}\text{-}U)$$ by this lemma, so by the inductive hypothesis,
$$\text{c}_n\text{-}U = |0\rangle\langle0| \otimes I_n + |1\rangle\langle1| \otimes \left(|0\rangle\langle0| \otimes I_{n-1} + \cdots + |1\rangle\langle 1|^{\otimes (n-2)} \otimes |0\rangle\langle 0| \otimes I_1 + |1\rangle\langle 1|^{\otimes n} \otimes U\right)$$
$$= |0\rangle\langle0| \otimes I_n + |1\rangle\langle 1| \otimes |0\rangle\langle 0| \otimes I_{n-1} + \cdots + |1\rangle\langle 1|^{\otimes (n-1)} \otimes |0\rangle\langle 0| \otimes I_1 + |1\rangle\langle 1|^{\otimes n} \otimes U,$$ as claimed. $\qed$
Next, let $A$, $B$ and $C$ be 1-gates obtained for $U$ from this corollary, that is, such that $$U = AXBXC \quad\text{and}\quad ABC = I_1.$$
$$\text{c}_n\text{-}U = (I_n \otimes A)(\text{c}_n\text{-}X)(I_n \otimes B)(\text{c}_n\text{-}X)(I_n \otimes C).$$
Proof. Using Lemma 1 with $X$ in place of $U$, we get $$(I_n \otimes A)(\text{c}_n\text{-}X) = (I_n \otimes A)\big(|0\rangle\langle0| \otimes I_{n-1} \otimes I_1 + \cdots + |1\rangle\langle 1|^{\otimes (n-1)} \otimes |0\rangle\langle 0| \otimes I_1 + |1\rangle\langle 1|^{\otimes n} \otimes X\big)$$ $$=|0\rangle\langle0| \otimes I_{n-1} \otimes A + \cdots + |1\rangle\langle1|^{\otimes (n-1)} \otimes |0\rangle\langle0| \otimes A + |1\rangle\langle 1|^{\otimes n} \otimes AX.$$ Multiplying by $(I_n \otimes B)$ on the right gives $$|0\rangle\langle0| \otimes I_{n-1} \otimes AB + \cdots + |1\rangle\langle1|^{\otimes (n-1)} \otimes |0\rangle\langle0| \otimes AB + |1\rangle\langle 1|^{\otimes n} \otimes AXB.$$ Multiplying this on the right by c$_n$-$X$ and using Lemma 1, we obtain $$|0\rangle\langle0| \otimes I_{n-1} \otimes AB + \cdots + |1\rangle\langle1|^{\otimes (n-1)} \otimes |0\rangle\langle0| \otimes AB + |1\rangle\langle 1|^{\otimes n} \otimes AXBX,$$ because $|0\rangle\langle0||1\rangle\langle1|$ is the zero operator, and any tensor product with the zero operator is also a zero operator. Finally, multiplying this on the right by $(I_n \otimes C)$ then gives $$|0\rangle\langle0| \otimes I_{n-1} \otimes ABC + \cdots + |1\rangle\langle1|^{\otimes (n-1)} \otimes |0\rangle\langle0| \otimes ABC + |1\rangle\langle 1|^{\otimes n} \otimes AXBXC;$$ since $ABC = I_1$ and $AXBXC = U$, it follows from Lemma 1 that this is equal to c$_n$-$U$, and the lemma is proved. $\qed$
Exercise: if the matrix representing $U$ is $\begin{pmatrix} a & b \\ c & d \end{pmatrix}$, then what does the matrix representing c$_n$-$U$ look like?
Lemma 2 achieves the goal of this post:
The $(n+1)$-gate c$_n$-$U$ can be designed using the Toffoli gate c$_n$-$X$ as well as gates of the form $I_n \otimes A$, for various 1-gates $A$. $\qed$
]]>The quantum Toffoli $n$-gate is the unique $n$-qubit gate that maps the computational basis state $|i_n \dots i_1\rangle$ to the computational basis state $|(i_n \oplus i_1 \cdots i_{n-1}) i_{n-1} \dots i_1\rangle$. So quantum CNOT is the quantum Toffoli 2-gate; and here is the quantum Toffoli 4-gate:
The effect of the Toffoli $n$-gate on the set of all computational basis states is that of the following transposition: switch $|01\dots1\rangle$ with $|1\dots11\rangle$ and leave all other computational basis states the same.
More generally, let $k \in {1, \dots, n}$. The Toffoli gate $T^{(n)}_k$ is the $n$-gate obtained from the Toffoli $n$-gate after switching the $k$th and $n$th wires in the diagram:
So the effect of the Toffoli gate $T^{(n)}_k$ on the set of all computational basis states is the transposition that switches $|1\dots1\rangle$ with $|1\dots101\dots1\rangle$ (where the 0 is the $k$th digit in the label of the second state) and leaves all other computational basis states the same.
Let $|i_n\dots i_1\rangle$ be any one of the computational basis states and $k \in \{1, \dots, n\}$. Then there exists an $n$-gate $T^{|i_n \dots i_1\rangle}_k$, built from $T^{(n)}_k$ and the Pauli $X$ gates, that switches the states $|i_n\dots i_{k+1} i_k i_{k-1} \dots i_1\rangle$ and $|i_n \dots i_{k+1}\ (i_k \oplus 1)\ i_{k-1} \dots i_1\rangle$, i.e., that flips the $k$th digit in the labels of these two states, and that leaves all other computational basis states the same.
Proof. For $l \in \{1, \dots, n\}$, we denote by $X_l$ the $n$-gate $I_{l-1} \otimes X \otimes I_{n-l}$, that is, the $n$-gate obtained by applying the Pauli $X$ gate to the $l$-th qubit. Let $I$ be the set of all $l \in \{1, \dots, n\}$ such that $l \ne k$ and $i_l = 0$. Then we first apply the product $\Pi_{j \in I} X_j$, changing each $i_j$ with $j \in I$ to 1. Then apply $T^{(n)}_k$. Follow this again by the product $\Pi_{j \in I} X_j$, changing each $i_j$ with $j \in I$ back to 0. Since $T^{(n)}_k$ only switches the basis states $|1\cdots101\cdots 1\rangle$ and $|1\cdots1\rangle$, the resulting circuit only switches the states $|i_n\dots i_{k+1} i_k i_{k-1} \dots i_1\rangle$ and $|i_n \dots i_{k+1}\ (i_k \oplus 1)\ i_{k-1} \dots i_1\rangle$. $\qed$
Let $|i_n\dots i_1\rangle$ and $|j_n\dots j_1\rangle$ be any two computational basis states. Then there exists and $n$-gate $T^{|i_n\dots i_1\rangle}_{|j_n\dots j_1\rangle}$ that switches $|i_n\dots i_1\rangle$ and $|j_n\dots j_1\rangle$ and leaves all other computational basis states the same.
Proof. Let $l \in \{1, \dots, n\}$ and $1 \le p_1 < p_2 < \cdots < p_l \le n$ be such that $i_{p_q} \ne j_{p_q}$ for each $q=1, \dots, l$, while $i_p = j_p$ for all other indices $p$. We start by applying $T^{|i_n \dots i_1\rangle}_{p_1}$, then $T^{|i_n \dots i_{p_1+1} j_{p_1} i_{p_1-1} \dots i_1\rangle}_{p_2}$, then continuing in this way until finally applying $T^{|i_n \dots i_{p_{l-1}+1} j_{p_{l-1}} i_{p_{l-1}-1} \dots i_{p_1+1} j_{p_1} i_{p_1-1} \dots i_1\rangle}_{p_l}$. At this point, the state $|i_n \dots, i_1\rangle$ has been moved to the state $|j_n \dots j_1\rangle$, but the latter has not yet been moved to the former, only to $|i_n \dots i_{p_{l-1}+1} j_{p_{l-1}} i_{p_{l-1}-1} \dots i_{p_1+1} j_{p_1} i_{p_1-1} \dots i_1\rangle$. To move it all the way to $|i_n \dots i_1\rangle$, we apply again the remaining operators from before, except for the last one, in reverse order: $T^{|i_n \dots i_{p_{l-2}+1} j_{p_{l-2}} i_{p_{l-2}-1} \dots i_{p_1+1} j_{p_1} i_{p_1-1} \dots i_1\rangle}_{p_{l-1}}$ followed by $\dots$ followed by $T^{|i_n \dots i_1\rangle}_{p_1}$. This “going back down the ladder” also has the effect that all the other states are put back into their original place, as required. $\qed$
For notational simplicity, we also denote the compositional basis states by $|0\rangle, \dots, |2^n-1\rangle$ and the Toffoli gates from Problem 2 by $T^{|k\rangle}_{|l\rangle}$, for $k,l \in {0, \dots, 2^n-1}$.
Exercise. Let $k,l \in \{0, \dots, 2^n-1\}$.
For the sake of completeness, we also convene that $T^{|k\rangle}_{|k\rangle} = I_{2^n}$, for $k \in {1, \dots, 2^n}$.
]]>The goal here is to show how we can simulate the classical probabilistic algorithm coded by $S$ as a quantum algorithm.
The naïve idea is to replace each $a_{ij}$ by $\sqrt{a_{ij}}$; the columns of the resulting matrix $U$ are then all quantum state vectors, and applying the operator $U$ to the basis state $|i\rangle$ produces the quantum state $\sum_{j=0}^{2^n-1} \sqrt{a_{ij}} |j\rangle$. After a von Neumann measurement of this outcome with respect to the computational basis, this means we obtain state $|j\rangle$ with probability $a_{ij}$, which appears to effectively simulate the classical probabilistic algorithm coded by $S$.
However, the problem is that $U$ is not an $n$-qubit operator in general, as it may not be unitary; for instance, the columns of $U$ may not be orthonormal. To simulate the classical probabilistic algorithm coded by $S$ in general, we need “more room” in the form of $n$ ancillary qubits.
So we are looking for a $2n$-qubit operator $U$ that somehow simulates the classical probabilistic algorithm coded by $S$ on the first $n$ qubits.
To do so, we let $|s_i\rangle := \sum_{j=0}^{2^n-1} \sqrt{a_{ij}} |j\rangle$ be the $i$-th column vector of the failed operator $U$ above. Using the Gram-Schmidt procedure, we complete each $|s_i\rangle$ into an orthonormal basis $\{|s_{i0}\rangle = |s_i\rangle, |s_{i1}\rangle, \dots, |s_{i(2^n-1)}\rangle\}$ of the Hilbert space $\CC^{2^n}$. Then we let $U$ be the unique $2n$-qubit operator such that $$U|j\rangle|i\rangle := |i\rangle|s_{ij}\rangle.$$
Remark: In other words, for $i,j \in \{0, \dots, 2^n-1\}$, the $\left(j\cdot2^n + i\right)$-th column of $U$ is $|i\rangle|s_{ij}\rangle$; in particular, the $i$-th column is $|i\rangle|s_i\rangle$.
Let’s check that this $U$ is unitary: given $i,j,k,l \in \{0, \dots, 2^n-1\}$, we have $$\langle i|\langle s_{ij}||k\rangle|s_{kl}\rangle = \langle i|k\rangle \langle s_{ij}|s_{kl}\rangle = \begin{cases} 1 &\text{if } i=k \text{ and } j=l, \\ 0 &\text{otherwise.} \end{cases},$$ as required.
Finally, if we set the ancillary qubits to $|0\rangle$, this $U$ effectively simulates the classical probabilistic algorithm coded by $S$: for $i \in \{0, \dots, 2^n-1\}$, we have $$U|0\rangle|i\rangle = |i\rangle|s_{io}\rangle = |i\rangle|s_i\rangle = \sum_{j=0}^{2^n-1} \sqrt{a_{ij}} |i\rangle|j\rangle.$$ After measuring the first $n$ qubits, this means they are in state $|j\rangle$ with probability $a_{ij}$, as needed.