(text courtesy of my colleague Chris Granade)
A quantum oracle O is a "black box" operation that is used as input to another algorithm. Often, such operations are defined using a classical function f: {0, 1}n → {0, 1}m which takes n-bit binary input and produces an m-bit binary output. To do so, consider a particular binary input x = (x0, x1, ..., xn - 1). We can label qubit states as 
.
We may first attempt to define O so that 
, but this has a couple problems. First, f may have a different size of input and output (n ≠ m), such that applying O would change the number of qubits in the register. Second, even if n = m, the function may not be invertible: if f(x) = f(y) for some x ≠ y, then 
but 
. This means we won't be able to construct the adjoint operation 
, and oracles have to have an adjoint defined for them.
We can deal with both of these problems 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 
and 
, \begin{align*} O(|x \rangle \otimes |y \rangle) = |x \rangle \otimes |y \oplus f(x) \rangle. \end{align*} Now 
by construction, thus we have resolved both of the earlier problems.
Importantly, defining an oracle this way for each computational basis state 
also defines how O acts for any other state. This follows immediately from the fact that O, like all quantum operations, is linear in the state that it acts on. Consider the Hadamard operation, for instance, which is defined by 
and 
. If we wish to know how H acts on 
, we can use that H is linear:
\begin{align*} H |+ \rangle = \frac{1}{\sqrt{2}} H(|0 \rangle + |1 \rangle) = \frac{1}{\sqrt{2}} (H |0 \rangle + H |1 \rangle) = \frac{1}{\sqrt{2}} (|+ \rangle + |- \rangle) = |0 \rangle \end{align*}
In the case of defining our oracle O, we can similarly use that any state 
on n + m qubits can be written as
Thus, the effect of the oracle O on this state is
Is there a reason you'd want to use m > 1 output qubits for a binary function?
Yes, why not?
The size of the output depends on what kind of computation the oracle implements. For example, an oracle for Simon's problem has m = n.
Oh sorry, I didn't see that the function did have m bits of output. I assumed it was a regular 1-bit boolean function.
Is XOR used only for satisfying inversability? If so, Can XOR(CNOT gate) be replaced by any another two-bit unitary operation?
The construction of the oracle depends on the algorithm in which you want to use it.
Deutsch-Jozsa algorithm relies on an oracle which maps
to 
, so the oracle-related tasks in the contest use the same format. In fact, once you've implemented the oracles for problems G and H, you can use them to test your implementation of Deutsch-Jozsa algorithm.
Grover's algorithm, on the other hand, relies on so-called "phase oracle", which maps
to 
(changing the phase of the qubit). This kind of oracle would likely be implemented using Controlled Z operation.
Oh I see.. So the type of oracle should be determined by kind of "behavior of the function". Thanks!
http://lapastillaroja.net/wp-content/uploads/2016/09/Intro_to_QC_Vol_1_Loceff.pdf
Just as a side note, Here the Quantum Oracle is explained in somewhat more detail, with examples. Maybe that'll help.
I have done problem I in Warmup round by simply implementing the Deutsch-Jozsa algorithm. However, I don't understand some details.
In the above formula for quantum oracle, the quantum oracle has no effect on the first n qubits, i.e. the input qubits. But in the algorithm, only the first n qubits are considered after applying the quantum oracle. The formulae in the Wikipedia page of Deutsch-Jozsa algorithm look fine to me but I don't understand why the first n qubits can already provide enough information to us.
Can someone point my misconception?
After all the gates are applied, the last qubit y doesn't actually carry any information, since it's always unentangled from the x register and is in
state.
We focus on measuring the first n qubits to figure out whether we measured a
state or some other non-zero basis state. If the function is constant, the amplitude of 
basis vector in their state is +1 or -1, and (since overall state of the qubits has to have unit norm) amplitudes of the rest of the basis vectors are 0; thus we will only measure 
. If the function is balanced, the amplitude of 
basis vector is 0, thus we will measure any basis vector except 
.
The key is that the phase is a property of the entire state, not of each qubit in it. So
is the same thing as 
. The oracle query maps the final qubit of a state from 
to either 
or 
. But then we can move the sign of the result to the group of input bits, because that's just an algebraic manipulation.
Also recall that the phase of a state by itself is meaningless. The phase only matters when you have a superposition: then the relative differences in the phases is what's important.
So you mean the ancilla bit has information about the result which is result = (result + initial value). And we can get the answer by using that 'information' ?
Uhm, so I think I understand what an oracle is now, but I don't think that what I implemented in problem G and H was an oracle. The main difference is that an actual oracle should modify both x and y, while my solution to G and H only modifies y. Is it correct that we haven't implemented any actual oracles in problem G and H?
Operations implemented in problems G and H are actual oracles. They modify the joint state of x and y, entangling qubits of x with y (unless x was in a basis state, in which case indeed only y was modified). Thus you can't really say in general case that x is not modified.
Ah ok, thanks, I was thinking that doing
wouldn't affect x, but clearly it does.
Hi,
When I was first tried to solve Problem G I made a bit of a boo boo and implemented a not so quantum oracle.
Have since realised my mistake and got the correct answer. However, I'm not sure why that attempt isn't passing the tests. Unless I'm misinterpreting the test inputs, they appear to be using basis states for the xs so my classic solution should be leaving the input/output states in the correct state.
The oracle should work not only on inputs which are basis states, but also on inputs which are in superposition. Otherwise you can't really use this oracle in any meaningful quantum algorithms :-)
Hi, thanks for the reply!
Yep, I appreciate that. Hence referring to my first attempt as a boo boo! What I don't understand is, given the particular tests are using basis states, why it is that my initial attempt didn't pass those tests?
As long as none of the input qubits are in a superposition it seems to me that the resulting quantum states should be the same.
That's not given. The test input seems like a seed to an entangled non-basis state generator and then N = 1, k = 0. That you got "Expected: Zero" doesn't indicate anything about your input state — if the checker converts x... back to all
states by an adjoint transformation and then measures something, it makes sense that your measurement would mess up the input state after the adjoint transformation, making it not all Zero.
Ah! I had been taking the 6 digit int used as test input to be a decimal representation of a binary string corresponding to a basis state. As I said previously "_Unless I'm misinterpreting the test inputs_"...
That int being a seed does seem much more likely. Thanks very much for your help!
That's what I first thought too, but it doesn't make much sense to represent one qubit with a six-digit int, especially if it's either in state 0 or state 1.
Does this definition allow using auxiliary qubits (beyond even the additional answer register) during the oracle computation?
Yes, so long as your auxiliary (or "ancilla") qubit is set to a purely zero state afterwards. This could be done by reversing the operations you did to it. You cannot set the qubit back to zero by measuring or with Reset if that causes other qubits to collapse as well.