# Quantum circuit of stateful oracle

Suppose I have operator $$U_f$$ that maps state $$|x\rangle|y\rangle|0\rangle$$ to another state $$|x\rangle|y\rangle|f(x, y)\rangle$$.

The function $$f$$ has its internal state, that changes on each invocation, but is somewhat "hidden" from an entity that provides $$|x\rangle|y\rangle$$ and receives $$|x\rangle|y\rangle|f(x, y)\rangle$$.

I.e. $$f$$ acts like this: $$\begin{array}{l} \underline{\textbf{Algorithm } f(x, y)} \\ s_i = \textbf{GenerateNewState}(s_{i-1}, x, y) \\ \textbf{return } g(s_{i}, x, y) \end{array}$$

Which way of drawing a quantum circuit of an oracle implementing such operator is correct?

This

Or this

• Does the output $f(x, y)$ also depend on the internal state? Like, if you query the oracle twice on the same input, do you get the same output, or will it change since the internal state changed? Commented Apr 30 at 10:01
• @TristanNemoz It does. The state changes on each invocation of $f$. I.e. two different queries may result in different results even if inputs $x$ and $y$ are the same. But one who queries $f$ does not observe $f$'s internal state, i.e. it knows nothing about its value (and probably even about its existence) Commented Apr 30 at 10:09
• In that case, the first circuit doesn't work, but the second one does! Commented Apr 30 at 11:32
• @TristanNemoz Thank you a lot Commented Apr 30 at 11:49

To add a bit on my comments (and also to actually provide an answer to the post), you have to remember that $$U_f$$ is nothing more than a matrix. Querying the oracle is actually applying $$U_f$$ to the vector $$|x, y, 0\rangle$$. In particular, it is not possible to change the value of $$U_f|x, y,0\rangle$$ upon subsequent queries without adding another register.
This is exactly what your second oracle does: it adds a register over which the adversary has no control, and which allows to change the behavior of the oracle, since there are no reason why $$U_f\left|x,y,s_i,0\right\rangle$$ should be equal to $$U_f\left|x,y,s_{i+1},0\right\rangle$$.
One might add that one has to be careful with how you define the "internal state" of the oracle, but as long as $$s_{i+1}$$ is a classical bitstring if $$x$$, $$y$$ and $$s_i$$ are also classical bitstrings, you'll be good to go.
As a last detail, you might want to highlight the fact that the output $$f(x, y)$$ actually depends on the state of the oracle. Writing $$f\left(x,y,s_i\right)$$ highlights this fact and tells nothing about the adversary's control over this internal state.