Quantum Matrix
Quantum Matrix#
We have seen that if we can quickly solve the period finding algorithm, then we can factor.
We have also seen that if we have a unitary matrix, we can find the phase of the eigenvalues.
Now we will find a unitary matrix
In future pages we will
Show that there exists a quantum circuit which quickly applies
to a stateShow that there exists a quantum circuit which quickly applies a controlled version of
to a stateImplement controlled-
as an atomic gate in our quantum simulator.Put everything together for Shor’s algorithm.
Let’s first remind ourselves what the period finding pieces we are building needs to do:
Period finding problem: Given
Our next step is going to be finding that there is a unitary operator
We are going to describe a unitary operator
We will assume we are working with a number of qubits of size
(this is just to define it all the way up to )
Notice that this is unitary.
Grading
Write code that generates this unitary matrix for an arbitrary co-prime
Because the matrix is unitary, the eigenvalues of the matrix are just phases (convince yourself this has to be true of any unitary matrix). We are now going to notice something additionally interesting about these phases. Take your function which generates this matrix and put it into your classical Shor’s algorithm code where you choose
Now, run your Shor’s algorithm code and find the vector
Grading
Verify that this is what you get. Paste your eigenvalues before and after you multiply by
(Think about why this is?)
What this means is that if you could find the phase (we will see soon how to use a quantum computer to do this) and if you could figure out what the
There is a general (fast classical) algorithm which takes a decimal number
from fractions import Fraction
Fraction(myDecimal).limit_denominator(the_largest_possible_value_of_r)
Notice, that there are two failure modes in this approach:
You might have a phase of 0. If you have a phase of 0, there’s no way to pull out
since .Suppose you were looking for
. The continuing fraction algorithm will give you which is true but not very helpful because the period isn’t two. Luckily this doesn’t happen because most and are co-prime.
If you hit one of these failure modes just start over with a new
Grading
Show that you can find the period
Now, let’s go ahead and modify your factoring algorithm so that instead of doing period finding the old way, it builds the matrix
Grading
Show that this works by factoring some numbers.