# Why does the definition of the oracle in Deutsch's algorithm fail to specify its action on superpositions?

I’m trying to understand the Deutsch algorithm. I can see that the math shows the algorithm to be correct, but I don’t understand how the math represents the given conditions.

The oracle is supposed to accept an input of 0 or 1 and output a value of 0 or 1. So what does it mean to pass a qubit in super position? I don’t see how this is defined, and so I don’t see how this algorithm can claim to test both input states at once. In my world, this is an invalid input and not defined by the function and that’s that - like 10/0. I guess the quantum world is a bit different? 😉

## Oracle's action on computational basis

The oracle's action is defined by the equation $$U_f|x\rangle|y\rangle = |x\rangle|y\oplus f(x)\rangle\tag1$$ where $$x\in\{0,1\}^n$$ and $$y\in\{0,1\}$$ are bitstrings of lengths $$n$$ and $$1$$, respectively, so that $$|x\rangle$$ and $$|y\rangle$$ are computational basis states.

## Misconception

The question appears to be based on incorrect interpretation of $$(1)$$ as defining $$U_f$$ by specifying its action on every input in its domain. If this were true, then $$U_f$$ would be a function defined on computational basis states only. Consequently, every other state, i.e. every non-trivial superposition of computational basis states, would lie outside of $$U_f$$'s domain and hence constitute invalid input.

## Extension by linearity

However, this interpretation is incorrect. In quantum computing, as in linear algebra more generally, linear functions, including quantum operations, are often defined by specifying their action on a basis and then extending by linearity.

Consider a linear function $$f:V\to W$$ from vector space $$V$$ to vector space $$W$$ over some field of scalars $$\mathbb{K}$$. Linearity means that $$f$$ satisfies two conditions \begin{align} f(x+y)&=f(x)+f(y)\tag2\\ f(ax)&=af(x)\tag3 \end{align} where $$x,y\in V$$ and $$a\in\mathbb{K}$$.

A straightforward, but very important consequence of linearity is that every set of equations $$f(x_i)=y_i$$ with $$x_i$$ ranging over a basis of $$V$$ completely defines $$f$$ in the sense that there is one and only one$$^1$$ function that satisfies $$f(x_i)=y_i$$.

This allows us to be parsimonious in specifying the action of $$f$$ on its input: it is sufficient to specify the action on any basis of the input vector space. This is very convenient because a basis is typically much smaller than the input space (in quantum computing the basis is typically finite, but the input space is uncountably infinite) and because a basis can often be chosen to be very simple (e.g. one can choose a basis without entangled states).

## Example

Consider for example the CNOT gate defined as $$\text{CNOT}|x\rangle|y\rangle = |x\rangle|x\oplus y\rangle\tag4$$ where $$x,y\in\{0,1\}$$ and $$\oplus$$ denotes addition modulo $$2$$. Equation $$(4)$$ specifies the action of CNOT on the computational basis. Let's try to exploit the fact that CNOT must be linear$$^2$$, i.e. that it must satisfy $$(2)$$ and $$(3)$$, to infer its action on some other input not covered by the specification $$(4)$$ such as $$|+\rangle|-\rangle$$. We have \begin{align} \text{CNOT}|+\rangle|-\rangle&=\text{CNOT}\frac{1}{\sqrt2}(|0\rangle+|1\rangle)\frac{1}{\sqrt2}(|0\rangle-|1\rangle)\tag5\\ &=\frac12\text{CNOT}(|0\rangle+|1\rangle)(|0\rangle-|1\rangle)\tag6\\ &=\frac12\text{CNOT}(|00\rangle-|01\rangle+|10\rangle-|11\rangle)\tag7\\ &=\frac12(\text{CNOT}|00\rangle-\text{CNOT}|01\rangle+\text{CNOT}|10\rangle-\text{CNOT}|11\rangle)\tag8\\ &=\frac12(|00\rangle-|01\rangle+|11\rangle-|10\rangle)\tag9\\ &=|-\rangle|-\rangle\tag{10} \end{align} where we used the definition of $$|\pm\rangle$$ states, equation $$(3)$$, distributivity of the tensor product over addition, equation $$(2)$$, specification of the action of CNOT on the computational basis states given by equation $$(4)$$, and finally the definition of $$|\pm\rangle$$ states once more.

$$^1$$ This is related to another convenient way of specifying linear functions: matrices.
$$^2$$ By the postulates of quantum mechanics.