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?