Q3L10a.txt

#
# File:   content-mit-8371x-subtitles/Q3L10a.txt
#
# Captions for 8.421x module
#
# This file has 165 caption lines.
#
# Do not add or delete any lines.  If there is text missing at the end, please add it to the last line.
#
#----------------------------------------

The quantum Fourier transform is a core component
of all known exponentially fast quantum algorithms.
It is defined as a unitary transform which maps basis
states j to superpositions over basis states
k with a phase factor here omega to the jk divided by n.
The phase factor is conveniently captured by defining omega
as e to the 2 pi i.
There are little n qubits and capital N is 2 to the n.
As an example, the Fourier transform
maps the 0 state to an equal superposition over all states
in the Hilbert space.
It also maps 1 to a superposition
but with a different set of phase factors
which linearly increases and maps
2 to a equal superposition with phase factors
which go as omega squared, omega fourth and so forth.
These examples show how different frequencies
result just like in a classical Fourier
transform from inputs which are delta functions.
How does the circuit complexity of the quantum Fourier
transform compare with the classical?
Let us look at the quantum Fourier transform circuit.
It is helpful for this to define the bitwise representations
of various quantities.
Let j, the input state, be decomposed as bits j sub a.
So j1 is the first bit, the most significant bit,
and jn is the least significant bit.
Let us also define the fraction, phi, which is 0.j1,
j2, j3 all the way out to jn representing
j divided by capital N. This is what
is known as a binary fraction representation
where, for example, 0.1 is 1/2, 0.11 is 3/4, and so forth.
Let us use this binary fraction notation
to simplify the way we write omega to the jk over N.
Consider j times 2 to the minus l.
It is convenient to write this as phi times
2 to the n minus l, which turns out to be 0.jn minus l plus 1
all the way up through jn.
This is a subset of the bits of j
and it happens because omega to an integer is equal to 1
and phi here is equal to j divided by N.
We use this representation next to construct
what is remarkably simple and intuitively appealing
quantum circuit for the Fourier transform.
I claim that the quantum Fourier transform
can be represented as a map between basis states
which have bits say j1 through jn
to a form which has first 0 plus omega to the 0.jn times 1,
tensored with 0 plus omega to the jn minus 1 jn times 1,
next tensored again with another term of the same form,
a single qubit of structure 0 plus omega
to the binary fraction, one more bit shifted in and so forth.
This structure is remarkable.
It looks like a sequence of single qubits in superposition
all tensored together.
First, let's prove this fact.
Let us work forward from the definition of the quantum
Fourier transform, that is it maps a basis
state to a superposition of phase weighted basis states,
omega to the jk divided by n.
For simplicity, I drop norms and use a binary representation
of k as well, so k sub l will be the lth bit of k.
Writing k out now bit by bit, the sum
becomes n sums over the bits of k
and let us also express the exponent of the phase
factor in terms of the bits k sub l of k.
Now, this expression can further be
simplified by rewriting this state k
as a tensor product over the individual qubits of k,
so that's kl going from l equals 1 to n.
Again, k is now the tensor product of the n bits kl.
Now, we may now flip the order of summation and the tensor
product such that we bring the tensor product out front
and each element of the tensor product
will be a sum over kl going from 0 to 1 over a single qubit's
state with phase factor omega to the jk sub l times two
to the minus l.
Remember this is the state of a single qubit
and we may explicitly write out the two cases, 0 plus omega
to the j times 2 to the minus l times ket 1.
Now, we have a tensor product of these states
and this expression is exactly what was claimed above,
namely that we have a tensor product of single qubit states
where the phases now will depend on other qubits,
but we have found this interesting remarkable
decomposition of the quantum Fourier transform.
Eddie Farhi likes to say that this
expresses the bitty nature of the quantum Fourier transform.
Let us use this representation to now construct
a quantum circuit for the quantum Fourier transform.
The baseline for our evaluation of this circuit complexity
will be the classical fast Fourier transform,
which takes n times 2 to the n steps or capital N log capital
N, which might be more familiar.
The quantum Fourier transform is different.
For a single qubit, it maps j1, that's
1 bit to 0 plus omega to the 0.j1 times 1
according to our claim above.
This is just a single Hadamard acting on the single qubit.
That is a single qubit circuit.
For n equal 2, we have j1, j2, the two
bits of the input mapping to 1 qubit
which is just like the one previous,
but with j2 instead of j1 and tensored with a second qubit,
which now has 0.j1, j2 in the exponent,
the first term is straightforward.
It's a Hadamard.
How do we get the second qubit?
Let's look at the quantum circuit.
From the n equal 1 case, we have a Hadamard
acting on the j1 qubit and then nothing on j2.
This gives us a state which has a 0 plus
omega to the 0.j1 acting on 1.
Now, this is not what we wanted so far
because this first term here has a Hadamard acting on j2,
not j1.
What we actually want is a single qubit phase rotation with
omega to the 0.0j2 such that we would get these two terms
for the second qubit.
And we can obtain that if we apply a controlled rotation
that does an omega to the 0.01 when j2 is equal to 1 applied
on the first qubit.
Let's call this an R2 gate and it is controlled from j2.
Now, applying a Hadamard on j2, we
obtain the full quantum Fourier transform circuit for n equal 2.
Let's generalize this to n equal to 3.
Here we have 3 qubits as input, j1 through j3
and the first term we want is a Hadamard on j3
and then a qubit which looks like the n equal 2 case
with an omega to the j2, j3 and then a new term,
which is an omega to the 0.j1, j2, j3.
Now, recall that j is 2 to the n times phi
and furthermore let us define a generalization of the rotation
we had R2 as Rk where we get a rotation omega to a 2
to the minus k.
Our 3 qubit quantum Fourier transform circuit
takes in the three qubits, j1, j2, j3,
applies a Hadamard and a controlled rotation R2,
just as was done for the n equal 2 case,
but now we wish to rotate an extra amount,
controlled R3, control based on j3
and this produces the third term in the tensor product above.
For j2, j3, we just apply the n equal 2 circuit that
involves a controlled R2 from j3 and it gives us
the middle qubit shown above in the superposition
and that has an omega to the 2 phi.
Finally, for the third qubit, we simply
apply the Hadamard getting the first term
on the left which has an omega to the 0.j3, which
is just omega to the 4 phi.
It is straightforward to generalize
this recursive procedure to the n qubit case.
This requires all pairs to interact,
meaning n times n plus 1 divided by 2 gates
and this order n squared gate requirement should be compared
with that the classical fast Fourier transform,
which goes as 2 to the n, exponentially more.
This is one of the reasons why the quantum Fourier
transform has been so appealing, but of course, there
is a catch.
Naively, the QFT is exponentially smaller, faster
than the FFT, but measurement causes collapse of the output
and thus only one of the Fourier transform results is sampled.
Thus something more clever is required to make use of the potential of the quantum Fourier transform.