The goal of the following is to familiarize yourself with the notion of superposition of states and with the notion of gates (which have nothing to do with stars or other intergalactical spaceships). It is by no mean mandatory, as the talk is self-contained. But as I will go through some concepts rather fast, you might want to give it a quick glance beforehand. It contains a few notations and conventions, and small exercises to play with the concepts. (1) Classical circuit ================= For the purpose of this homework, a piece of classical data is a string of bits (0 (false) and 1 (true)), conveniently represented in ascii form horizontally from left to right: 0100 and vertically from top to bottom: 0 1 0 0 In this homework (and in the forthcoming talk), a classical circuit is a bunch of horizontal wires connected with boxes. Bits flows on the wires from left to right. For example, the circuit +---+ +---+ ----| N |------x-----|T1 | +---+ | +---+ | (*) +---+ +-+-+ |I0 |----| N |----------- +---+ +---+ has one input and one output, and it contains 4 boxes: * a gate on one wire (bit -> bit) called N; * a gate on two wires (bit x bit -> bit x bit) consisting of a N-box and a vertical link to the upper-wire, connected with "x". * a gate creating a wire, called I0 (type () -> bit); * a gate terminating a wire, called T1 (type bit -> ()). There are three kinds of elementary gates from which one builds general circuits: * initialization gates: I0 and I1, of type () -> bit. These gates create bits in state 0 (resp. 1) out of nothing. * termination gates: T0 and T1, of type bit -> (). These gates annihilate the bit on the wire, while serving as an assertion: if the bit is not in the described state (0 if T0; 1 if T1) then the procedure fails. * N-gate: of type (bit -> bit). Flips the input wire. * (possibly multi-)controlled-N-gates: fire the N-gate on the corresponding wire only if the controlled wires are in the right states. Controls are "x" for "state 1", and "o" for "state 0". Example 1: In the above diagram, the control wire is the upper-one. The semantics of the controlled-N-gate is 00 |-> 00 (unchanged) 01 |-> 01 (unchanged) 10 |-> 11 11 |-> 10 Example 2: The gate ------o------ | +---+ ----| N |---- +---+ | ------x------ has semantics: 001 |-> 011 011 |-> 001 s |-> s i.e. the middle bit is flipped iff the upper one is 0 and the lower one is 1. Example of circuit, with semantics outlined below: +---+ ----------------+------|T0 | | +---+ +---+ +---+ |I0 |----| N |--------- +---+ +---+ With input 0: (in) 0------0--------0-------- (ok) 0--------0----------0 (out) The circuit sends 0 to 0. With input 1: (in) 1------1--------1-------- (FAIL) 0--------1----------1 (out) So the circuit fails with input 1. Example: the following circuit implements the conjunction, with garbage: b1 ------x----- b1 | b2 ------x----- b2 | +--+ +---+ |I0|----| N |--- b1 /\ b2 +--+ +---| i.e. it does not delete any wires. EXERCISE 1.1: What is the semantics of the first 4-gate circuit (*) given above? EXERCISE 1.2: Can you come up with a circuit to compute the disjunction? You are allowed to carry garbage. So the semantics of the circuit should be myor : bit x bit --> garbage x bit (b1, b2) |-> (garbage, b1 or b2) EXERCISE 1.3: can you find a circuit generating the reversible map rev_and : bit x bit x bit ---> bit x bit x bit (b1, b2, b3) |--> (b1, b2, (b1 /\ b2) \oplus b3) ? and a circuit implementing the reversible map rev_or : bit x bit x bit ---> bit x bit x bit (b1, b2, b3) |--> (b1, b2, (b1 \/ b2) \oplus b3) ? (2) Quantum data ============ Now, instead of just strings of bits, we consider complex, linear combinations of strings of bits: strings of bits with complex coefficients. This is what we will call "quantum data". So for example, one could have 0.5 * 001 + 0.5 * 100 - 0.5 * 010 - 0.5 * 101 as a piece of quantum data. This is what we would call a state of a 3-quantum bit system (or simply "3 qubits"). The coefficient of a quantum state should satisfy a normalization properties: the sum of the square of their absolute value should be equal to 1. In practice, if a * 001 + b * 010 + c * 011 + d * 100 + e * 101 + f * 110 + g * 111 is a quantum state, one should have |a|^2 + |b|^2 + |c|^2 + |d|^2 + |e|^2 + |f|^2 + |g|^2 = 1 Think of a quantum superposition as some sort of generalized probabilistic sum. (3) Quantum gates ============= As for classical data, one can write quantum circuit to describe modifications of a quantum state. Apart from the gates we saw in Section 1, there are gates specific to quantum systems. For example, the gate Hadamard (denoted with H) acts on one quantum bit (i.e. one wire) and perform the operation 0 |--> sqrt(2)/2 * 0 + sqrt(2)/2 * 1 1 |--> sqrt(2)/2 * 0 - sqrt(2)/2 * 1 What happen when the gate is inserted into a larger circuit, e.g. if one apply H on the first quantum bit of the 2-qubit state 00 ? One just works on the first quantum bit, without considering the other bits. So we get sqrt(2)/2 * 00 + sqrt(2)/2 * 10. If we work with the most generic state for 2-qubit: a * 00 + b * 01 + c * 10 + d * 11 this is modified piecewise, not touching the other quantum bits as in the simple case: a * 00 |--> a * ( sqrt(2)/2 * 00 ) (+ sqrt(2)/2 * 10 ) + b * 01 |--> b * ( sqrt(2)/2 * 01 ) (+ sqrt(2)/2 * 11 ) + c * 10 |--> c * ( sqrt(2)/2 * 00 ) (- sqrt(2)/2 * 10 ) + d * 11 |--> d * ( sqrt(2)/2 * 01 ) (- sqrt(2)/2 * 11 ) after distributing multiplication: a * sqrt(2)/2 * 00 + a * sqrt(2)/2 * 10 + b * sqrt(2)/2 * 01 + b * sqrt(2)/2 * 11 + c * sqrt(2)/2 * 00 - c * sqrt(2)/2 * 10 + d * sqrt(2)/2 * 01 - d * sqrt(2)/2 * 11 we match the strings together: (a * sqrt(2) + c * sqrt(2))/2 * 00 + (b * sqrt(2) + d * sqrt(2))/2 * 01 + (a * sqrt(2) - c * sqrt(2))/2 * 10 + (b * sqrt(2) - d * sqrt(2))/2 * 11 EXERCISE 3.1: What is the result of applying the gate H on the state sqrt(2)/2 * 0 + sqrt(2)/2 * 1 ? EXERCISE 3.2: What is the result of applying the gate H twice on the state 0? EXERCISE 3.3: what happen if you apply the H gate on the two qubits of the state 00? Try by doing first +---+ ---| H |--------------- +---+ +---+ --------------| H |---- +---+ (i.e. H on qubit 1, then on qubit 2) then convince yourself that doing it the other way doesn't change the result: +---+ -------------| H |--- +---+ +---+ ---| H |------------- +---+ (4) Measurements ============ The hadamard gate is a unitary gate: an operation that is reversible, that sends valid quantum states to valid quantum states and that does not generate classical data. To generate classical data out of a quantum state, one measures one (or several) quantum bits. The measurement is a probabilistic operation that returns a classical information and modifies the state of the system. The rule of thumb is that the probability of getting a particular classical result is dependent on their coeeficients in the quantum state. Example : measuring a * 0 + b * 1 * with probability |a|^2: - return false (0) - change the state of the system to 0 * with probability |b|^2: - return true (1) - change the state of the system to 0 Example : measuring all qubits in a * 00 + b * 01 + c * 10 + d * 11 * with probability |a|^2: - return 00 - change the state of the system to 00 * with probability |b|^2: - return 01 - change the state of the system to 01 * with probability |c|^2: - return 10 - change the state of the system to 10 * with probability |d|^2: - return 11 - change the state of the system to 11 Example : measuring qubit 3 in the system a * 000 + b * 010 + c * 100 + d * 011 + e * 001 + f * 101 * with some probability: - return 0 - change the system to a * 000 + b * 010 + c * 100 * with some other probability: - return 1 - change the system to + d * 011 + e * 001 + f * 101 in particular: if for all strings with a non-zero coefficient in the state, qubit 3 is in the same value, then measuring the system does not modify it. I.e. if one measures qubit 3 in the state a * 001 + b * 101 we get back the state unmodified, and the result of the measurement is always 1. EXERCISE 4.1: What is the probability of getting 1 then 0 when measuring the state sqrt(2)/2 * 00 + sqrt(2)/2 * 11 if you measure the qubits either all at once, or separately? (5) Classical function and quantum data =================================== Some very useful operations are designed by mapping classical functions onto quantum functions: if f is one-to-one on strings of bits, one wants U(f) to be the unitary map sending a * ...00 + b * ...01 + c * ...10 + d * ...11 + ... to a * f(...00) + b * f(...01) + c * f(...10) + d * f(...11) + ... Note that f really needs to be one-to-one for this to be unitary. EXERCISE 5.1: What would go wrong if f were the conjunction? EXERCISE 5.2: We're still trying to get the conjunction: we have a nice classical circuit conjunction_with_garbage for it. Consider the operation that first applies this circuit and then measures the input wires: ---------x----- then measure | ---------x----- then measure | +--+ +---+ |I0|----| N |--- result +--+ +---| For which states does this compute the right function? What is wrong with the other states?