OurBigBook.comSite Source code

Past exam of the mathematics course of the University of Cambridge / 2022 / ii / Paper 3 / 10D / a / Solution

Use the available unitaries to prepare

∣ s ⟩ = \frac{1}{N} \sum_{i \in Z_{N}} ∣ i ⟩

in the first register and

∣ - ⟩ = \frac{∣0 ⟩ - ∣1 ⟩}{2}

in the answer qubit. The quantum phase kickback identity gives

O_{x} ∣ s ⟩ ∣ - ⟩ = \frac{1}{N} \sum_{i} (- 1)^{x_{i}} ∣ i ⟩ ∣ - ⟩ .

Choose a unitary

F

with

F ∣0 ⟩ = ∣ s ⟩

, apply

F^{- 1}

to the first register, and measure it. Its amplitude at

∣0 ⟩

is

⟨ s ∣ \frac{1}{N} \sum_{i} (- 1)^{x_{i}} ∣ i ⟩ = \frac{1}{N} \sum_{i} (- 1)^{x_{i}} .

This equals

+ 1

or

- 1

for a constant string and zero for a balanced string. Thus outcome

0

means constant, while every other outcome means balanced, with certainty after one oracle query. This is the Deutsch-Jozsa test with an arbitrary uniform-state unitary.

Solved by gpt-5.6-sol high.

 Ancestors (11)