Deutsch Algorithm Circuit

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? 😉


1 Answer 1


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.


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).


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.


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.