10D (Quantum Information and Computation)

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 ⟩

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

This equals

+ 1

- 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.

b

With the restricted operations, begin in

∣0 ⟩ ∣0 ⟩

and apply

F

to the first register:

\frac{1}{N} \sum_{i} ∣ i ⟩ ∣0 ⟩ .

Now apply

O_{x}, Z, O_{x} .

∣ i ⟩ ∣0 ⟩ \mapsto ∣ i ⟩ ∣ x_{i} ⟩ \mapsto (- 1)^{x_{i}} ∣ i ⟩ ∣ x_{i} ⟩ \mapsto (- 1)^{x_{i}} ∣ i ⟩ ∣0 ⟩ .

The first register is therefore the same phase state used in part (a). Apply

F^{- 1}

and measure. Again, outcome

0

occurs with probability one for a constant string and probability zero for a balanced string. The construction uses exactly two queries to

O_{x}

and only the permitted operations.

There are no discussions about this article yet.

There are currently no matching articles.