How do bitstring oracles work in quantum circuits?

In most diagrams of oracles for basic algorithms such as Deutsch-Jozsa (e.g., https://qiskit.org/textbook/ch-algorithms/deutsch-jozsa.html) the inputs are bitstrings $$x$$ and $$y$$, and outputs are bitstrings $$x$$ and $$y \oplus f(x)$$.

When used in a quantum circuit, the oracle is given quantum states, $$|x\rangle$$ and $$|y \rangle$$, where $$|x\rangle$$ is often in superposition, and $$|y\rangle$$ is an eigenvector of the oracle. The output of the oracle can be seen as the result of phase kickback (https://people.vcu.edu/~sgharibian/courses/CMSC491/notes/Lecture%206%20-%20Deutsch's%20algorithm.pdf):

$$U_f|x\rangle|-\rangle = (-1)^{f(x)}|x\rangle|-\rangle$$

I have a question:

The oracle's inputs and outputs are shown as bitstrings, not states. Where, and how, are the circuit's input states $$|x\rangle$$ and $$|y\rangle$$ turned into bitstrings $$x$$ and $$y$$ before the oracle, and then back into states after? Or should the diagram be showing a quantum version of the oracle, and the input/output labels should be states?

The input states $$|x\rangle$$ and $$|y\rangle$$ are vectors, but you can also interpret them as bitstrings using the computational basis $$\{|0\rangle,|1\rangle\}$$. For example, if $$x=010$$, then we can encode that bitstring as $$|x\rangle=|0\rangle|1\rangle|0\rangle=|010\rangle$$. In the Deutsch-Jozsa algorithm, the input state $$|x\rangle$$ for the unitary $$U_f$$ is actually the superposition of all $$2^n$$ bitstring states: $$\frac{1}{\sqrt{2^{n}}}\sum_{x\in\{0,1\}^n}|x\rangle$$. Starting from the all zeros state $${|0\rangle}^{\otimes n}$$, this state can be obtained by applying a Hadamard gate $$H=\frac{1}{\sqrt{2}}\begin{pmatrix} 1 & 1 \\ 1 & -1 \end{pmatrix}$$ to each of the $$n$$ qubits.
• Thank you. This makes sense to me. But there's still a piece missing. As drawn, the output of the oracle is a bitstring. Even if we interpret that as a tensor product of the basis states, bitstrings don't have a sign (as far as I know). But the sign change on some states is essential to an algorithm like D-J. As drawn, there's no explicit way to attach that $-1$ to some output bitstrings, and thus some states. Is this diagram, as drawn, not therefore incomplete? Commented Feb 22, 2022 at 8:05
• @Eleeza Isn't the result of D-J, $|0\rangle ^{\otimes n} = "0 \cdots 0"$ if $f(x)$ is constant or something else if $f(x)$ is balanced. I don't see where a negative sign is required here. Mathematically, there can be a negative sign in the superposition when representing it in the basis ${|0\rangle, |1\rangle}$, but as you said, the output needs to be one of the basis states. Commented Feb 22, 2022 at 15:02
• Thanks! My question is not about the algorithm, but that the diagram and algorithm don't match. The diagram shows the upper qubits going into $H$ gates, then an oracle which (as drawn) outputs the same bitstring $x$ it receives as input, then more $H$ gates. The oracle (as drawn) is thus an identity on the upper register, the two $H$ sets invert one another, and so the upper register (again, as drawn) isn't changed in any way. But we know that it does change - that's the whole point, and the role of the $-1$ in my original post. So this standard circuit diagram must be missing something, no? Commented Feb 22, 2022 at 17:21
• @Eleeza I think you can find the answer to your question in this paragraph. They explain this intuitively in the second part. As you said if the function is constant nothing happens with the oracle, so you end with $|0\rangle ^{\otimes n}$. However as you said, with a balanced function, we end, before the last $H$ gates, with $\tfrac{1}{\sqrt{2^n}}\begin{bmatrix} -1 \\ 1 \\ -1 \\ \vdots \\ 1 \end{bmatrix}$ which if you do the calculation is orthogonal to $|0\rangle ^{\otimes n}$. Commented Feb 23, 2022 at 13:42
• As the $H$ gate is unitary, it does not affect the scalar product and thus after applying it, we will still have a gate that is orthogonal to $|0\rangle ^{\otimes n}$ and thus will never measure $|0\rangle ^{\otimes n}$ and have a different bit-string. Commented Feb 23, 2022 at 13:47