QUANTUM ALGORITHMS
1. Let P represent the portion of the eigenvalue approximation circuit shown below.
.
.
.
|ui
We consider the circuit for arbitrary unitary m-dimensional U, |ui ∈ Bm, and x ∈ {0,1}n (the eigenvalue estimation circuit took x = 0n and |ui to be an eigenvector).
Show that P |x,ui = |xi ⊗ U[x] |ui, where [x] is the number with binary representation x and U[x] is matrix exponentiation.
2. Let U be a unitary operator and suppose that |αi and |βi are eigenvectors with respective eigenvalues λ,µ ∈ C. Prove that if λ 6= µ then hα | βi = 0 (i.e. |αi and |βi are orthogonal).
3. Let ι : {0,1} → {0,1} be the identity function, defined by ι(x) = x. The function ι⊕(x,y) = (x,x ⊕ y) has the property that
ι⊕(x,0) = (x,x),
meaning that it clones the bit x in the first register to the second register.
Let |ψi ∈ B be an arbitrary 1-qubit quantum state. Show that
.
That is, the quantum operator corresponding to the classical 1-bit cloning operator ι⊕ fails to clone |ψi unless |ψi is in a state corresponding to a classical bit.
4. Let U be a (2n)-qubit operator that clones two n-qubit quantum states, |ϕi,|ψi ∈ B⊗n, meaning
U(|ϕi ⊗ |0ni) = |ϕi ⊗ |ϕi and U(|ψi ⊗ |0ni) = |ψi ⊗ |ψi.
Prove that U clones |ϕi and |ψi if and only if |ϕi = |ψi or hϕ | ψi = 0. [Hint: take the inner product of the two equations.]
5. Use the previous question to prove that a there are no quantum cloning operators that work for all pairs of states.
1
