Quantum Algorithms Flashcards
Quantum algorithm
Take advantage of the quantum power
Runs on a realistic model of quantum computation: eg circuit model
show that it is provably faster then if was done on a classical computer
Deutsch Algorithm
Evaluate boolean function Take boolean and output a boolean possible combinationations Constant 1. f(1) = 0 f(0) = 0 2. f(1) = 1 f(0) = 1 Non-Constant 3. f(1) = 0 f(0) = 1 4. f(1) = 1 f(0) = 0
Predict if constant or not given a function
Query complexity 2 (just query the function twice and see pattern) but with Quantum only 1 !
Circuit: input bit |x> and control bit |y> can both either be 0 or 1. Hadamard on x and y
unitary transformation
Hadamard on x
output |x> and y (+) f(x)
have |x> (x) |y> -> |x> (x) y (+) f(x)
XOR has no impact if y is 0
4 possible output give us the permutations of the 4 basis elements. With just 1 query we can now (write them out)
control bit |y>
makes sure we have a unitary transformation
it controls the output
Deutsch Josza Algorithm
Generalization of Deutsch
input is a binary vector and the output is a binary
Find if f is constant or non constant.
This would require to see half the possibilities + 1 to be sure. This means 2^(n-1) + 1. This gets exponentially high on a classical computer but only 1 request is needed in quantum computing !
circuit: n wires in parallel of the n elements of the input vector and the control bit y.
Hadamard dimension n for vector x, Hadamard for y, unitary transformation transformation for both, Hadamard dimension n for x
output |x0> (x) … (x) |xn> and |y (+) f(x0,…,xn)>
Generalized Hadamard
Kronecker product of Hadamard
H^(x) n
1/sqrt(2) [ H^(x) n-1 H^(x) n-1; H^(x) n-1 H^(x) n-1]
Simon’s problem
input is binary vector and the output is binary vector.
f(x)=f(y) iff y=x or y=x(+)s
thus f(x)=f(y)=f(x(+)s)
s is a secret string. how to find s
s cannot be all 0 otherwise not periodic
we get pairs of inputs
XOR on more than 2 bits
apply xor individually on each index of the sequence
1001 (+) 1010 = 0011
