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?


enter image description here

Or this

enter image description here

  • $\begingroup$ 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? $\endgroup$
    – Tristan Nemoz
    Commented Apr 30 at 10:01
  • $\begingroup$ @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) $\endgroup$ Commented Apr 30 at 10:09
  • 1
    $\begingroup$ In that case, the first circuit doesn't work, but the second one does! $\endgroup$
    – Tristan Nemoz
    Commented Apr 30 at 11:32
  • $\begingroup$ @TristanNemoz Thank you a lot $\endgroup$ Commented Apr 30 at 11:49

1 Answer 1


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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.