18.435J Homework #2 Solutions

18.435/2.111 Homework # 2 Solutions What are the one- and two-bit conservative classical gates? Show that these are not sufficient to do universal classical computation, and thus cannot be used to make a Fredkin gate.   Solution: The two-bit conservative classical gates must take 00 to 00, must take 11 to 11, and must take 01 and 10 to a state with exactly one 1. This leaves four possibilities,   IN OUT IN OUT IN OUT IN OUT 00 00 01 10 01 01 01 10 01 01 10 01 10 01 10 10 10 10 01 01 10 01 10 10 11 11 11 11 11 11 11 11 The first of these gates is the identity and the second is the SWAP gate. Suppose you want to implement a 1-1 function whose output bits are not a fixed permutation of the input bits. The last two of these gates cannot be used as they map the inputs 01 and 10 to the same outputs, and so can not be used for the computation of a 1-1 function, as these would lead to fewer than 2^2 possible outputs. The identity and the SWAP gates merely change the order the bits. Thus, these four gates cannot compute (say) a Fredkin gate, which is a 1-1 conservative function that is not a permutation of the inputs.   The above proof does not allow for the use of extra workbits that can be initialized in the states 0 or 1, but it is easy to check that these don't help, as if a constant bit is one of the inputs to any of the above four gates, it behaves the same as either the identity gate or the SWAP gate. My attempt to build a Fredkin gate in problems 2-5 failed because of a sign error in Problem 4.   2. Find some conservative two-bit quantum gates. Gates which just change phase (diagonal unitary matrices) are conservative, as is the SWAP gate. Find a larger class of such gates. Find a square root of SWAP.   Solution: The most general two-qubit conservative gate cannot mix the three sub-spaces containing no 1)'s, containing one 1), and containing two 1)'s, and thus is composed of two arbitrary 1 x 1 unitary matrices and an arbitrary 2 x 2 unitary matrix. This can be expressed, for example, as ... (Continuation from the previous part) where the θ_i are real numbers, and a and b are complex numbers satisfying |a|² + |b|² = 1. The SWAP gate is [ \begin{pmatrix} 1 & 0 & 0 & 0 \ 0 & 0 & 1 & 0 \ 0 & 1 & 0 & 0 \ 0 & 0 & 0 & 1 \end{pmatrix} ] If you take its eigenvectors and eigenvalues, you find that |00⟩, |11⟩, and (|01⟩ + |10⟩)/√2 are eigenvectors with eigenvalue 1, while (|01⟩ - |10⟩)/√2 is an eigenvector with eigenvalue -1. If these eigenvectors are λ_i and |v_i⟩, the square root can be found by taking [\sum_{i} \sqrt{\lambda_{i}} |v_{i}\rangle \langle v_{i}|] which for one choice of square roots is [ \begin{pmatrix} 1 & 0 & 0 & 0 \ 0 & \frac{1}{2}(1+i) & \frac{1}{2}(1-i) & 0 \ 0 & \frac{1}{2}(1-i) & \frac{1}{2}(1+i) & 0 \ 0 & 0 & 0 & 1 \end{pmatrix} ] 3. Part 1: Multiply some of the gates found in (2) to build a quantum gate F which manipulates the bits in the same way as the Fredkin gate when operating on states in the canonical basis, but in which some phases might be different.   Solution: Let [ P = \begin{pmatrix} 1 & 0 & 0 & 0 \ 0 & 1 & 0 & 0 \ 0 & 0 & -1 & 0 \ 0 & 0 & 0 & -1 \end{pmatrix} ]   this is σ_z applied to qubit 1 tensored with the identity on qubit 2. Let Q be the square root of SWAP gate found in the solutions to problem 2. Then it is easy to check that   [ PQPQ = \begin{pmatrix} 1 & 0 & 0 & 0 \ 0 & 0 & 0 & 1 \ 0 & 0 & 1 & 0 \ 0 & 1 & 0 & 0 \end{pmatrix} ] Now, let Q₁₂ be Q (on qubits 1 and 2) tensored with the identity on qubit 3, and P_3→1 be the controlled-gate which applies P to the first qubit when the third qubit is a |0⟩, and the identity to the first qubit when the third qubit is a |1⟩. Then, P_3→1Q₁₂P_3→1Q₁₂ applies PQPQ to the first two qubits when the third qubit is a |0⟩, and SWAP to these two qubits when the third qubit is a |1⟩. This is a Fredkin gate, albeit with the incorrect phase of -i applied to the states |010⟩ and |100⟩. 3. Part 2: Show that there is an 8x8 diagonal unitary matrix which you can multiply by F to produce a Fredkin gate. Solution: No matter which states have incorrect phases, you can multiply the matrix with a diagonal matrix which changes the phase on the incorrect states. For example, in the solution above, we need to fix the phases on |010⟩ and |100⟩. The diagonal matrix with entries 1, 1, -1, 1, -1, 1, 1, 1 does this.   4. By combining two-qubit unitary diagonal matrices (these represent gates that just manipulate phases), which three-qubit diagonal matrices can you obtain? Show that if you augment these gates with the gates represented by diagonal matrices with entries 1, 1, (e^{i\theta}), 1, 1, 1, 1, 1 on the diagonal you can obtain all of the 3-qubit diagonal gates.   WARNING: I made a mistake in this homework problem. Both exponentials should be (e^{i\theta}). This means that problem 5 no longer works, so you don't have to do it. I don't know whether it's possible to build a Fredkin gate from conservative 2-qubit gates or not.   Solution: Let λ_b1b2b3 be the diagonal entry corresponding to the bit string b₁b₂b₃. We will show that we can achieve any diagonal matrix that satisfies [\lambda_{000}\lambda_{011}\lambda_{101}\lambda_{110}=\lambda_{001}\lambda_{010}\lambda_{100}\lambda_{111};] that is, the product of the eigenvalues for even parity bit strings is equal to the product of the eigenvalues for odd parity bit strings. We first show that this equation must be satisfied. This is true because it is satisfied for all 2-qubit diagonal matrices. For example, suppose we have a diagonal matrix D which is a two-qubit gate for the first two qubits. Then   [\lambda_{000}=\lambda_{001},] [\lambda_{010}=\lambda_{011},] [\lambda_{100}=\lambda_{101},] [\lambda_{110}=\lambda_{111},] so the equation above must be satisfied. Similar arguments apply to two-qubit gates which operate on the first and third qubits, and on the second and third qubits. We now show that we can achieve a diagonal matrix with arbitrary values in the first seven diagonal places. Consider the product   [\begin{pmatrix} a & 0 & 0 & 0 & 0 & 0 & 0 & 0 \ 0 & b & 0 & 0 & 0 & 0 & 0 & 0 \ 0 & 0 & c & 0 & 0 & 0 & 0 & 0 \ 0 & 0 & 0 & d & 0 & 0 & 0 & 0 \ 0 & 0 & 0 & 0 & e & 0 & 0 & 0 \ 0 & 0 & 0 & 0 & 0 & f & 0 & 0 \ 0 & 0 & 0 & 0 & 0 & 0 & g & 0 \ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 <2>end{pmatrix} \begin{pmatrix} 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \ 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \ 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 \ 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 \ 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 \ 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 \ 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 \ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 <2>end{pmatrix} \begin{pmatrix} 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \ 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \ 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 \ 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 \ 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 \ 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 \ 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 \ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \end{pmatrix} ]   By choosing the appropriate values for a,b,c,d,e,f,g (for example, we need (e=\lambda_{100}a^{-1}) and (g=\lambda_{110}e^{-1}c^{-1})), we can produce arbitrary values for all of the first seven entries on the diagonal. The λ₁₁₁ entry is determined by Eq. (1) above.