I am trying to explain what an oracle is. In four paragraphs or so.
This is what I wrote.
Some algorithms are designed which contain special subroutines called oracles. An oracle is a black box operation which takes some input and produces an output. In order to use an oracle in a quantum algorithm, we must first encode the desired function into the oracle. There are two main ways to do this.
The first way is to define the oracle so that it takes an n-bit input and produces an m-bit output. This can be done by introducing a second register of m qubits to hold our answer. Then we will define the effect of the oracle on all computational basis states: for all x∈{0,1}n and y∈{0,1}m, O(|x⟩⊗|y⟩)=|x⟩⊗|y⊕f(x)⟩. Now O=O† by construction, thus we have resolved both of the earlier problems. To see that O=O†, note that O2=1 since a⊕b⊕b=a for all a,b∈0,1. As a result, O|x⟩|y⊕f(x)⟩=|x⟩|y⊕f(x)⊕f(x)⟩=|x⟩|y
The second way to define an oracle is to apply a phase based on the input to O. For instance, we might define O such that O|x>=(−1)f(x)|x>. If a phase oracle acts on a register initially in a computational basis state |x>, then this phase is a global phase and hence not observable. But such an oracle can be a very powerful resource if applied to a superposition or as a controlled operation.
Choosing the best way to implement an oracle depends heavily on how this oracle will be used within a given algorithm. For example, Deutsch-Jozsa's algorithm relies on the oracle implemented in the first way, while Grover's algorithm relies on the oracle implemented in the second way.
The question being I need the spoken format of x∈{0,1}n and y∈{0,1}m, O(|x⟩⊗|y⟩)=|x⟩⊗|y⊕f(x)⟩. Now O=O† by construction, thus we have resolved both of the earlier problems. To see that O=O†, note that O2=1 since a⊕b⊕b=a for all a,b∈0,1. As a result, O|x⟩|y⊕f(x)⟩=|x⟩|y⊕f(x)⊕f(x)⟩=|x⟩|y> and O such that O|x>=(−1)f(x)|x
Could someone help me convert these into spoken words?
x∈{0,1}n
(Spoken as) x belongs to set 0 comma 1 times n) and y∈{0,1}m (y belongs to the set 0 comma 1 times m
O( |x⟩⊗ |y⟩) = |x⟩ ⊗ |y⊕f(x)⟩
(Spoken as) O times the sum of open parenthesis ket x times the tensor product of ket y close parenthesis is equal to ket x times the tensor product of the ket y times the direct sum of f of x.
Now O=O† by construction, thus we have resolved both of the earlier problems. To see that O=O†, note that O2=1 since a⊕b⊕b=a for all a,b∈0,1. As a result, O|x⟩|y⊕f(x)⟩=|x⟩|y⊕f(x)⊕f(x)⟩=|x⟩|y>
(Spoken as) Now O is equal to O daggar by construction, thus we have resolve both of the earlier problems. To see that O is equal to O daggar, note that O times 2 is equal to 1. O times 2 is equal to 1 since a direct sum b direct sum b equals a for all a comma b sum of 0 comma 1. As a result, O ket x times y sum of f of x ket is equal to ket x times y direct sum of f of x times direct sum of f of x ket is equal to ket x times y.
O|x>=(−1)f(x)|x>
(Spoken as) O ket x is equal to open parenthesis negative 1 closed parenthesis times f of x times ket x.)