Homework 3: More about basic gates and mea- surements, XOR and Phase Oracles The goal of this homework is to review unitary operations and measurements and to ensure you are comfortable manipulating xor and phase oracles. You are permitted to discuss these problems with classmates and at office hours, as well as to avail yourself of any other resource. However, you are to write down your final solutions on your own, not to copy or write collaboratively. The grader is permitted to grade you down if your work is poorly written, illegible, or difficult to follow. It is your responsibility to write in a succinct rigorous understandable way. Be careful to not confuse the letters and v. Exercise 1 (6 points): CNOT in the X basis The “controlled not” gate acting on two qubits where the first is the deemed "control" and the second is deemed "target" can be written as CNOT = 0 0 0 0 1 0 0 0 0 1 0 0 1 0 in the basis Z {100), |01), |10), |11)}. • • • √2 (3 points) Consider the X basis of a single qubit |+) = 10)+11), |-) : |0)-|1) √2 What is the result of CNOT gate acting on each of the states |++), |+ −), | − +), | − −)? (1 point) What is the matrix representation of the CNOT gate in the X basis (please also write down the sequence of basis vectors so we know how you ordered them)? (2 points) Going back to the Z basis representation, how does the CNOT gate look like if you swap the target and control qubits. Exercise 2 (7 points): Poorman's Quantum Tomography Say you have a set A of many copies of the state (0) +11) and a set B of random selections of the states (0) and (1) (again many copies, in a 50-50 distribution). You are given these two sets, but you are not told which one is which. √2 1. (1 point) If you are permitted to perform measurements in the computa- tional basis (the Z basis), can you say which set is which? Why? 2. (1 point) Does your answer change if you can perform measurements in the X basis? Why? 1 Consider the state |Y) = a|0) + ß|1). 3. (1 point) What constraints do a and ẞ obey? 4. (1 point) What is the unique state (D) which is orthonormal to the state |V)? 5. (3 points) Say you have a set C of many copies of the state (V) and a set D of a random selection of the states (0) and (1) (state |0) is a fraction |a|2 of all states in the set D while the rest are states (1)). Again, you are given these two sets but you do not know which one is which and you need to perform repeated measurements in order to distinguish them. What is the circuit you would use for that, i.e. what is the circuit which you can use (maybe repeated uses) in order to distinguish the sets C and D? For gate notation, consult Aaronson's lecture notes. You can use other notations as long as you explain their meaning. Exercise 3 (6 points): Converting between Oracles Consider the classical function f which takes n bits and returns 1 bit. 1. (1 point) Consider the unitary gate Uxor corresponding to the XOR oracle for f. How many qubits does this gate act on (i.e. how many lines pass through the rectangle representing the gate in circuit notation)? How large is the unitary matrix corresponding to this gate? 2. (1 point) Consider the unitary gate Up corresponding to the phase oracle for f. How many qubits does this gate act on (i.e. how many lines pass through the rectangle representing the gate in circuit notation)? How large is the unitary matrix corresponding to this gate? 3. (2 points) Draw a circuit that is equivalent to the Uxor gate, but it uses only the Up gate and potentially other "standard" gates (e.g. some of the gates defined in the Aaronson lecture notes). If necessary, you are permitted to have some extra “auxiliary” qubits lying around at the end (as long as they are not entangled with the rest of the system at the end, i.e. as long as you can factor them out). 4. (2 point) Draw a circuit that is equivalent to the Up gate, but it uses only the Uxor gate and potentially other "standard" gates (e.g. some of the gates defined in the Aaronson lecture notes). If necessary, you are permitted to have some extra “auxiliary” qubits lying around at the end (as long as they are not entangled with the rest of the system at the end, i.e. as long as you can factor them out). Exercise 4 (13 points): Necromancy-hardness Quantum Necromancy and The circuits involved in this problem are shown at the end. 2 When quantum mechanics was being developed, the notion of superposition seemed preposterous. Schroedinger suggested a thought experiment exemplifying how ridiculous superposition is. In modern parlance the thought experiment is as follows: Imagine a qubit in the (+) state. That qubit is connected to a trigger that can kill a cat. The trigger does nothing if the qubit is in state |0) and it kills the cat if it is in state (1), i.e. the trigger acts as a "control-kill” gate, with the aforementioned qubit as control and the state of the cat as a target. You can think of the cat as "a very large number of degrees of freedom, i.e., a very large number of qubits to be kept in memory”. In this setup, after the control-kill gate, the state of the cat would have to be a superposition of alive and dead. We have never observed such a cat state in the real world, therefore quantum mechanics is preposterous and probably wrong. In this problem we will untangle (pun intended) this paradox. We will use computational complexity theory as a way to provide a non- preposterous explanation of the thought experiment. We will prove that the following two capabilities are equally “difficult”, where the difficulty is some measure of the circuit complexity to perform each: • • Distinguishing: Capability of keeping superposition of two orthogonal states in memory / proving it is actual superposition (e.g. by distinguishing different phases in the superposition). Rotating: Capability of deterministically rotating between the two or- thogonal states. The two orthogonal states in question will be |A) and (D) standing for Alive and Dead. Think of them as very large states, an immense number of qubits (necessary to fully define the complete state of a cat), and potentially difficult to keep in memory without them "decohering". and Defining the first capability: proving/distinguishing superpositions |A)+|D) Schroedinger says it is preposterous to imagine that states like |0): √2 |4) = |A)-|D) could exist and be observable. Let us define what "be observable" means: it means, having a circuit capable of distinguishing whether the circuit input is ) or 4) or simply a classical 50/50 mixture of |A) and (D) (repeated executions of the circuit might be necessary). √2 (1 point) Are (0) and (v) orthogonal? (2 point) Express |A) and |D) in terms of 6) and 4). Let us write down the simplest such circuit: It requires one additional auxiliary qubit in addition to the large number of qubits representing the cat. The circuit involves one single gate U, acting on the entire system (auxiliary qubit and cat), with the following properties: • | U |0] × |ø) = |0) ☆ |ø) • | U |0) |v) = |1) × |V] 3 As you know, to fully define a gate, you need to know how it acts on all vectors in a given basis. The gate also needs to be a unitary operation. (3 points) The above does not fully define the gate. Which of the following is a possible way to complete the definition of the gate? Why or why not? • U |1) × |ø) = |1) × |ø) and U |1) × |V) = • U |0)|6) = |1)|0) and U |0) × |V) |0) 4) |0) |4) • U |1] × |ø) = |1) × |ø) and U |1) × |v) |1)|4) Now we will use the gate U (the one we have defined above) to distinguish superposition from a classical probability distribution. Consider three possibilities: S1 we are given many copies of the state |0); S2 we are given many copies of the state (4); S3 we are given a large set of states, randomly half of them being |A) and half of them being |D). We will use an auxiliary qubit prepared in state |0). We will perform the gate U and then measure the auxiliary qubit in the Z basis. Prove that this circuit leads to the following results: • • • (1 point): If we are given S1, then when repeating the circuit on new states from the given set will lead to a measurement result that is always 0. (1 point): If we are given S2, then when repeating the circuit on new states from the given set will lead to a measurement result that is always 1. (1 point): If we are given S3, then when repeating the circuit on new states from the given set will lead to randomly getting either 0 or 1 with equal probability each time we run the measurement. Thus we can use a circuit involving one extra qubit, a U gate and a single Z measurement to check whether we have a true quantum superposition, or just a classical probability distribution over two possible states. Defining the second capability: rotating between states Having a gate that turns |A) into (D) and vice versa is what the rotation capability is all about. Such a gate implies we have defeated death and we can resurrect the dead. We intuitively know this is rather difficult. Capability of detection of large superpositions implies capability of resurrection Consider now the ancillary qubit being in state |+) and the cat being in state |D). We perform the circuit UZU, i.e. we apply the gate U followed by the single-qubit gate Z acting on the first qubit followed by applying U again. (1 point) What is the state of the full system (qubit and cat) after the first U gate? 4 (1 point) What is the state of the full system after the Z gate acts on the qubit? (2 point) Prove that the state of the system after the second U gate is |—)|A). The cat is resurrected! Congratulations, you used the gate U (originally designed simply to be able to distinguish superposition from classical probability distribution) to do a very different task: to rotate between the two states that might be in superposition. You turned the state |D) into the state |A). You did not simply defeat Death, you proved that being able to observe macroscopic quantum superposition is at least as difficult as reversing macroscopic chaotic processes (like undoing death or unscrambling eggs). Thus the answer to Schroedinger's incredulity is: "indeed, the technology necessary to observe a macroscopic superposition of dead and alive is as difficult to create as the technology to reverse death". In this problem we did not prove that macroscopic superposition does or does not exist, rather we just explained why it is difficult to sustain it: We proved that sustaining macroscopic superposition is at least as difficult as another difficult problem. This type of reduction of complexity is very common in theoretical computer science. However, instead of discussing space-complexity or time-complexity or query-complexity, we used necromancy-complexity. auxiliary quilit (G) cat's state 3 Z Checking for superposition <+1 ☑ Reviving 10>{ и 5