wk6 Flashcards
What is Deutsch’s algorithm
A quantum algorithm to determine if a function is balanced or constant by a single pass
What is the circuit used in deutsch’s algorithm
two qubits. The top qubit can be any arbitrary state but both are usually set to |0>. but the second qubit has an X rotation applied to it so it flips to |1>. Then a Hadamard is applied to both to get |+> and |->. They both go through the oracle and if the function is constant, the output of the gate will output |0>, if balanced it will |1>
Explain how we arrive at the result of Deutsch’s algorithm
Oracle must be a unitary funciton of the form U|x>|y> = |x> | y (mod2 addition) f(x). Consider first qubit being in arbitrary state x after hadamard and second qubit will be in state |->
The unitary transformation is equal to (deriving from |x->)
U( |x0> -|x1> / root(2)) = ( U|x0> - U|x1> ) / root(2))
Expanding this unitary transformation will show that if f(x) is 0, then the function is |x0> - |x1> = |x-> and if f(x) =1 then we get |x1> - |x0> which is equal to -|x->
This can be simplified to (-1)^f(x) * |x->
The output states after the oracle are then
1/root(2) ( (-1)^f(x) |0-> + (-1)^f(x) |1-> ) if first register has |0> and second register has |1>
If f is constant ( f(0) = f(1) ). the above simplifies to ( ( |0> + |1> ) tensor |-> ) = |+->
If f is balanced then it simplifies to ( ( |0> - |1> ) tensor |-> ) = |–>
On the first register, we apply a final hadamard. if constant then state in top register is |+> and we get |0>. Else top register has |-> to give us |1> ( function is balanced)
How does the problem in Deutsch Jozsa differ compared to the Deutsch algorithm
Deutsch jozsa has n bit string which evaluates to true or false rather than than a single input output.
What is the circuit used in deutsch jozsa
N number of input qubit |0> each hadamarded and input into oracle. Finally, there is also a |1> qubit entered into the oracle. Output is of oracle has a Hadamard for each of the output |x> qubits, and the final register has nothing additional, identity
How does the Deutsch Jozsa algorithm work
We know that every register of 0 will be in |+> state. So before entering oracle we have |+>^(* n) (*) |->. If we replace |0> with arbitrary |x> this can be written as 1/2^n sum |x> tensor |->
We know from deutsch algorithm that oracle applied to form |x - > gives (-1)^f(x) |x->. So we after the qubit pass through the oracle the state will be 1/2^n sum (-1)^f(x) |x ->
The two hadamard basis can be shortend to H|x>=1/root(2) sum_z={0,1} (-1)^(x . z) |z>
For many hadamard this simplifies to:
H^(tensor n )|x> = 1/2^(n/2) sum over all Z (where z is 0 or 1 computational basis state) (-1)^X.Z |z>
Substituting this into the previous equation for result of oracle transformation. we get 1/2^n sum_x sum_z (-1)^(f(x)) (-1)^(x . z) |z> |->
the amplitude is 1/2^n sum_x (-1)^(f(x)). If the function is constant, all signs of f(x) will be the same so the total will sum to positive or negative 2^n. Which cancels with the scalar factor. and probability is the absolute value of the amplitude which give us probability of 1. If the function is constant then we are guaranteed to get an output string of all 0’s.
If the function is balanced, then the positive and negative signs must cancel each other out. So probability of outputting all 0’s is 0.
So inputting an all 0 bit string can immediately tell us if function is constant or balanced
How does Grovers Algorithm work (high level)
Given an oracle representing function f(x) where if x is the desired element to be found, function outputs 1, else, 0. algorithm finds the desired value in O(root(n)).
Oracle ( O ) acts as follows:
O|x> = (-1)^(f(x)) |x>
If the element is the one we are looking for, it flips its phase. All others are left unaffected.
The phases are then amplified by the distance from the mean. The further the distance from the mean, the higher the amplitude.
The desired phase will be far away from the rest, so it will be most amplified. Performing a measurement on this superposition will most likely give the desired value
How does the Grover’s algorithm circuit work
1) apply hadamard to all qubits
2) Oracle flips desired qubit’s amplitude
3) amplify phases around the mean via another oracle
4) perform measurement in X basis
What does Quantum Fourier transform do at a high level
Maps some |x> representing an integer to a superposition which is uniform in magnitude ( the z basis for the int |x> ) but varies in phase
outline the high level steps of QFT
1) |x> is mapped to the superposition of all of its possible basis states where each basis state has its associated frequency component that corresponds to amplitude
2) the amplitudes may interfere constructively or destructivley
What is period finding in quantum computing
if there is a periodical function we can efficiently find it’s period.
What is period finding circuit in quantum computing
if there is a periodical function we can efficiently find it’s period
1) prepare two-qubit registers size n, prepare both to be |0> so composite system is |00>
2) Apply QFT to the first register
3) then apply unitary operator that acts on both registers U_f |x 0> = |x>|f(x)>
4) the total state of the system is then 1 / root (n) ( sum^(w-1)_x=0 |x> |f(x)>)
5) Make measurement on second register to get f(x) = u. This collapses the first register into a superposition of all values of x that give f(x) = u
6) first register is therefore somehow periodic so we can apply QFT to obtain the spectrum
7) measurement on final state is likely to give a maxima result k2^n/r. r is easy to calculate classically if j and r have no common factors. If they do we have to start again
Name the steps to Shor’s algorithm, where the factoring number is N
1) check if N is prime or even, if so give up or return 2 respectively
2) Determine if N = y^b for integers y>=1, b>=2, if so return y
3) choose ‘a’ between 1 and N-1. If gcd(a,N) > 1, return gcd(a,N), else move onto quantum part
4) preform period finding for period ‘r’ of f(x) = a^x mod N
5) if r is even and a^(r/2) mod N is not equal to -1 Mod N. Then compute gcd(a^(r/2) plus/minus 1, N). For most cases a and a^( r / 2 ) +- 1 will share a common factor with n. If not try again
Explain in more detail the quantum element of Shor’s factoring algorithm
1) Load two quantum register |r1 r2 >. such that reg1 can represent numbers up to chosen number ‘a’ -1 and register 2 can represent up to N -1
2) apply period finding of a where a^x mod N for each number stored in reg1, and store result in reg 2, call it k
3) perform a measurement on reg2 which will collapse reg 1 to equal superposition of values between 0 and a-1 that satisfy a^x mod N = k
4) reg1 is therefore somehow periodic, we apply QFT to register 1
5) measure register 1 to get some value m, which has a high probability of being a factor of ‘a’/r
6) next is classical post processing to determine r
explain classical pre-processing steps to Shor’s algorithm
1) check N is not even or prime or
2) choose random num ‘a’ between 1 and N
3) find gcd(a,N) and check if equal to 1
