Let be any Boolean function on input bits

PHYSICS · Multi-part · Fermi University Physics · Quantum Information & Technology · Quantum states, measurement and entanglement · The quantum circuit model and quantum algorithms

Quantum Information and Technology, Ch Oracles, quantum parallelism and the first algorithms

Problem

Let f:{0,1}n→{0,1}f:\{0,1\}^n\to\{0,1\} be any Boolean function on nn input bits, with bit oracle Uf∣x⟩∣y⟩=∣x⟩∣y⊕f(x)⟩U_f|x\rangle|y\rangle=|x\rangle|y\oplus f(x)\rangle for y∈{0,1}y\in\{0,1\}. ((a)) Starting from the definition of UfU_f, show that Uf(∣x⟩∣−⟩)=(−1)f(x)∣x⟩∣−⟩U_f\big(|x\rangle|-\rangle\big)=(-1)^{f(x)}|x\rangle|-\rangle for every basis state ∣x⟩|x\rangle of the input register. ((b)) Let ∣ψ⟩=∑xcx∣x⟩|\psi\rangle=\sum_xc_x|x\rangle be any state of the input register. Using linearity and part (a), show that Uf(∣ψ⟩∣−⟩)=(Of∣ψ⟩)∣−⟩U_f\big(|\psi\rangle|-\rangle\big)=\big(O_f|\psi\rangle\big)|-\rangle, where Of∣x⟩=(−1)f(x)∣x⟩O_f|x\rangle=(-1)^{f(x)}|x\rangle, so that on states of this form UfU_f acts exactly as Of⊗IO_f\otimes I. ((c)) Explain, using part (b), why a single copy of ∣−⟩|-\rangle, prepared once at the start of an algorithm, can serve as the output register for every one of that algorithm's later queries, however many input qubits there are.

Browse the problem library