Past exam of the mathematics course of the University of Cambridge / 2012 / iii / Paper 67 / 4 / a

Solution

Put

M = 2^{m}

and prepare

m

control qubits in

∣0 ⟩^{\otimes m}

and the target in the supplied eigenstate

∣ ψ ⟩

. Apply a Hadamard gate to every control qubit. Let

k = \sum_{j = 0}^{m - 1} 2^{j} k_{j}

denote the integer encoded in that quantum register.

For every

j

U^{2^{j}}

with control

k_{j}

and the same target. The quantum phase kickback yields

\frac{1}{M} \sum_{k = 0}^{M - 1} ∣ k ⟩ U^{k} ∣ ψ ⟩ = \frac{1}{M} \sum_{k = 0}^{M - 1} e^{2 πik x / M} ∣ k ⟩ \otimes ∣ ψ ⟩ = QFT_{M} ∣ x ⟩ \otimes ∣ ψ ⟩ .

Applying

QFT_{M}^{- 1}

to the controls therefore produces

∣ x ⟩

x

with certainty, and the algorithm outputs

ϕ = x / 2^{m} .

This is exact quantum phase estimation; exactness uses the finite dyadic phase promise, not a rounding argument.

Only a controlled-U gate is supplied as a primitive. Its

2^{j}

repetitions implement controlled-

U^{2^{j}}

, so the total number of black-box uses is

\sum_{j = 0}^{m - 1} 2^{j} = 2^{m} - 1

There are no discussions about this article yet.

There are currently no matching articles.