Deutsch Oracle Problem

2022/11/10 | by Alex Laurent | quantum

Intro

Here is a small introduction about quantum computing and how it works. Knowing almost nothing about this part of computer science, I decided to dig into the rabbit hole and read more about it. I’m still very new at this (a noob) so I hope that this article makes some kind of sense. I found that the best way for me to understand a concept is to explain it completely so here it is!

In this article/tutorial, we’re going to discover qubits, why are they different from classical bits, how we can build quantum logic gates, and we’re going to solve a simple problem where quantum computers actually outperform classical computers. Pretty awesome.

Also the quantum world is actually hard to conceptualize usually. I read that our native languages are not fit for it, therefore it’s usually easier to see the math.

Let’s jump into the quantum realm.

Classical bits representation

Classical bits are units that represent 2 states: 0 or 1. It’s the foundation of classical computing.

For the rest of the article, we’re going to use a vector notation:

• bit 0: $\left(\begin{array}{c}1\\ 0\end{array}\right)$ or using the Dirac vector notation: $|0⟩$
• and bit 1: $\left(\begin{array}{c}0\\ 1\end{array}\right)$ or: $|1⟩$

A good way to remember which bit is which, you can think of the vector as an array with 1 at the index of the bit.

Now there are 4 operations we can apply to a bit: Identity, Negation, Set 0, Set 1. We can actually use a matrix as a transformation operator.

Identity

f(x) = x

$f(|0⟩)=|0⟩$	$f(|1⟩)=|1⟩$
$\left(\begin{array}{cc}1& 0\\ 0& 1\end{array}\right)\left(\begin{array}{c}1\\ 0\end{array}\right)=\left(\begin{array}{c}1\\ 0\end{array}\right)$	$\left(\begin{array}{cc}1& 0\\ 0& 1\end{array}\right)\left(\begin{array}{c}0\\ 1\end{array}\right)=\left(\begin{array}{c}0\\ 1\end{array}\right)$

Negation

f(x) = ¬x

$f(|0⟩)=|1⟩$	$f(|1⟩)=|0⟩$
$\left(\begin{array}{cc}0& 1\\ 1& 0\end{array}\right)\left(\begin{array}{c}1\\ 0\end{array}\right)=\left(\begin{array}{c}0\\ 1\end{array}\right)$	$\left(\begin{array}{cc}0& 1\\ 1& 0\end{array}\right)\left(\begin{array}{c}0\\ 1\end{array}\right)=\left(\begin{array}{c}1\\ 0\end{array}\right)$

Set 0

f(x) = 0

$f(|0⟩)=|0⟩$	$f(|1⟩)=|0⟩$
$\left(\begin{array}{cc}1& 1\\ 0& 0\end{array}\right)\left(\begin{array}{c}1\\ 0\end{array}\right)=\left(\begin{array}{c}1\\ 0\end{array}\right)$	$\left(\begin{array}{cc}1& 1\\ 0& 0\end{array}\right)\left(\begin{array}{c}0\\ 1\end{array}\right)=\left(\begin{array}{c}1\\ 0\end{array}\right)$

Set 1

f(x) = 1

$f(|0⟩)=|1⟩$	$f(|1⟩)=|1⟩$
$\left(\begin{array}{cc}0& 0\\ 1& 1\end{array}\right)\left(\begin{array}{c}1\\ 0\end{array}\right)=\left(\begin{array}{c}0\\ 1\end{array}\right)$	$\left(\begin{array}{cc}0& 0\\ 1& 1\end{array}\right)\left(\begin{array}{c}0\\ 1\end{array}\right)=\left(\begin{array}{c}0\\ 1\end{array}\right)$

Multiple bits

To represent multiple classical bits and keep consistency with each of the operations, we can use the tensor product of multiple vectors, each vector representing a single bit.

For 2 bits, it looks like: $\left(\begin{array}{c}a\\ b\end{array}\right)\otimes \left(\begin{array}{c}c\\ d\end{array}\right)=\left(\begin{array}{c}ac\\ ad\\ bc\\ bd\end{array}\right)$

For 3 bits: $\left(\begin{array}{c}a\\ b\end{array}\right)\otimes \left(\begin{array}{c}c\\ d\end{array}\right)\otimes \left(\begin{array}{c}e\\ f\end{array}\right)=\left(\begin{array}{c}ace\\ acf\\ ade\\ adf\\ bce\\ bcf\\ bde\\ bdf\end{array}\right)$

Example:

$|00⟩=\left(\begin{array}{c}1\\ 0\end{array}\right)\otimes \left(\begin{array}{c}1\\ 0\end{array}\right)=\left(\begin{array}{c}1\\ 0\\ 0\\ 0\end{array}\right)$

$|01⟩=\left(\begin{array}{c}1\\ 0\end{array}\right)\otimes \left(\begin{array}{c}0\\ 1\end{array}\right)=\left(\begin{array}{c}0\\ 1\\ 0\\ 0\end{array}\right)$

$|10⟩=\left(\begin{array}{c}0\\ 1\end{array}\right)\otimes \left(\begin{array}{c}1\\ 0\end{array}\right)=\left(\begin{array}{c}0\\ 0\\ 1\\ 0\end{array}\right)$

$|11⟩=\left(\begin{array}{c}0\\ 1\end{array}\right)\otimes \left(\begin{array}{c}0\\ 1\end{array}\right)=\left(\begin{array}{c}0\\ 0\\ 0\\ 1\end{array}\right)$

And again we see that $|N⟩$ is a vector with a 1 at the Nth index.

Multi bits gates

CNOT gate

One common gate is called the CNOT gate. It takes 2 bits in input and “returns” 2 bits. The 1st bit is called the control bit and the 2nd bit is called the target bit. It behaves like this:

• If the control bit is 0, the target bit is left unchanged.
• If the control bit is 1, the target bit is flipped.

It can be represented as a matrix as well: $\left(\begin{array}{cccc}1& 0& 0& 0\\ 0& 1& 0& 0\\ 0& 0& 0& 1\\ 0& 0& 1& 0\end{array}\right)$

$C(|00⟩)=|00⟩$	$C(|01⟩)=|01⟩$	$C(|10⟩)=|11⟩$	$C(|11⟩)=|10⟩$
$\left(\begin{array}{cccc}1& 0& 0& 0\\ 0& 1& 0& 0\\ 0& 0& 0& 1\\ 0& 0& 1& 0\end{array}\right)\left(\begin{array}{c}1\\ 0\\ 0\\ 0\end{array}\right)=\left(\begin{array}{c}1\\ 0\\ 0\\ 0\end{array}\right)$	$\left(\begin{array}{cccc}1& 0& 0& 0\\ 0& 1& 0& 0\\ 0& 0& 0& 1\\ 0& 0& 1& 0\end{array}\right)\left(\begin{array}{c}0\\ 1\\ 0\\ 0\end{array}\right)=\left(\begin{array}{c}0\\ 1\\ 0\\ 0\end{array}\right)$	$\left(\begin{array}{cccc}1& 0& 0& 0\\ 0& 1& 0& 0\\ 0& 0& 0& 1\\ 0& 0& 1& 0\end{array}\right)\left(\begin{array}{c}0\\ 0\\ 1\\ 0\end{array}\right)=\left(\begin{array}{c}0\\ 0\\ 0\\ 1\end{array}\right)$	$\left(\begin{array}{cccc}1& 0& 0& 0\\ 0& 1& 0& 0\\ 0& 0& 0& 1\\ 0& 0& 1& 0\end{array}\right)\left(\begin{array}{c}0\\ 0\\ 0\\ 1\end{array}\right)=\left(\begin{array}{c}0\\ 0\\ 1\\ 0\end{array}\right)$

We can see the 2 parts in the matrix with $\left(\begin{array}{cc}1& 0\\ 0& 1\end{array}\right)$ reflecting the identity part (leaving the target unchanged) and the $\left(\begin{array}{cc}0& 1\\ 1& 0\end{array}\right)$ reflecting the flipping part.

Qubits

Qubits are physical objets (ions, photons, nucleus, electrons, …) that can be used as units of quantum measurement. The difference with classical bits is that qubits can represent states that are neither 0 or 1, but a proportion of both 0 and 1 at the same time.

That weird state is called superposition.

And because we’re in the quantum world, it’s only when we measure a qubit that it collapses with a probability to finally be 0 or 1.

Now the way I understand it is with an example, if you have 3 bits, you can make 8 combinations: 000, 001, 010, 011, 100, 101, 110, and 111. However you’re only getting 1 information out of 3 bits.

In superposition, you can imagine that your qubits are in all those states at the same times, so 3 qubits gets 8 pieces of information, even though you can’t measure that information yet.

Mesuring is what makes all your qubits to collapse to a state, therefore coming back to being classical bits.

The power of qubits is to use superposition so that N Qubits gives you 2^N bit of information only until you measure your results. Exponential information!

When I started reading about Qubits, I couldn’t make sense of it but again, math is the language we need to understand it better.

Representation of Qubits

Qubits can also be written as vectors with each element of the vector a probability, and so a qubit is represented as: $\left(\begin{array}{c}a\\ b\end{array}\right)$ with ||a||² + ||b||² = 1 with a, b ∈ ℂ and so it has the probability ||a||² to be 0 and ||b||² to be 1.

so it can also look like $\left(\begin{array}{c}\frac{1}{\sqrt{2}}\\ \frac{1}{\sqrt{2}}\end{array}\right)$ or even $\left(\begin{array}{c}\frac{1}{\sqrt{2}}\\ -\frac{1}{\sqrt{2}}\end{array}\right)$ which works because ${\left|\left|\frac{1}{\sqrt{2}}\right|\right|}^2+{\left||-\frac{1}{\sqrt{2}}|\right|}^2=1$

Note that in both these examples, the Qubit has 50% chance to collapse to either 0 or 1! When it’s 50/50, it’s called equal superposition.

Our classical bits vectors are just specific qubits, with:

$|0⟩=\left(\begin{array}{c}1\\ 0\end{array}\right)$ having the probability 100% of being a 0 and $|1⟩=\left(\begin{array}{c}0\\ 1\end{array}\right)$ having the probability 100% of being a 1

We now have some tools to manipulate our qubits, we can apply a CNOT to a pair of qubits or simply flip a qubit state, whatever that state is and even if we don’t know it, for example:

$\left(\begin{array}{cc}0& 1\\ 1& 0\end{array}\right)\left(\begin{array}{c}\frac{1}{\sqrt{2}}\\ -\frac{1}{\sqrt{2}}\end{array}\right)=\left(\begin{array}{c}-\frac{1}{\sqrt{2}}\\ \frac{1}{\sqrt{2}}\end{array}\right)$

Operations on qubits

Note that all operations on qubits have to be reversible. An operation is said to be reversible if knowing the output and the function, you’re able to know or reconstruct the input.

Identity and Negation are reversible, however Set-0 and Set-1 are not. Indeed, both functions are constant and don’t use the input at all, so knowing the result it’s impossible to know what the input was.

For constant operations, like Set-0 and Set-1, we can instead configure a gate using multiple Qubits. We’ll see how this works next in the article.

Bloch sphere

So far, we’ve been using matrixes but it also helps to visualize common Qubits on a sphere. It is called the Bloch sphere

To make it easy, we can consider Qubits with a, b ∈ ℝ and so in that case, we only need a circle (which simplifies the drawings).

We can use the probability to be 0 as the x coordinate and the probability to be 1 as the y coordinate. It looks like this:

We can actually navigate through the circle, for example bit flips:

Hadamard gate

Another gate we need before we dig into the problem we want to solve is the Hadamard gate

The hadamard gate takes a Qubit in equal superposition and turns it to a $|0⟩$ or a $|1⟩$. It’s matrix representation looks like: $\left(\begin{array}{cc}\frac{1}{\sqrt{2}}& \frac{1}{\sqrt{2}}\\ \frac{1}{\sqrt{2}}& -\frac{1}{\sqrt{2}}\end{array}\right)$

$\left(\begin{array}{cc}\frac{1}{\sqrt{2}}& \frac{1}{\sqrt{2}}\\ \frac{1}{\sqrt{2}}& -\frac{1}{\sqrt{2}}\end{array}\right)\left(\begin{array}{c}\frac{1}{\sqrt{2}}\\ \frac{1}{\sqrt{2}}\end{array}\right)=\left(\begin{array}{c}1\\ 0\end{array}\right)$

$\left(\begin{array}{cc}\frac{1}{\sqrt{2}}& \frac{1}{\sqrt{2}}\\ \frac{1}{\sqrt{2}}& -\frac{1}{\sqrt{2}}\end{array}\right)\left(\begin{array}{c}\frac{1}{\sqrt{2}}\\ -\frac{1}{\sqrt{2}}\end{array}\right)=\left(\begin{array}{c}0\\ 1\end{array}\right)$

$\left(\begin{array}{cc}\frac{1}{\sqrt{2}}& \frac{1}{\sqrt{2}}\\ \frac{1}{\sqrt{2}}& -\frac{1}{\sqrt{2}}\end{array}\right)\left(\begin{array}{c}-\frac{1}{\sqrt{2}}\\ \frac{1}{\sqrt{2}}\end{array}\right)=\left(\begin{array}{c}0\\ -1\end{array}\right)$

$\left(\begin{array}{cc}\frac{1}{\sqrt{2}}& \frac{1}{\sqrt{2}}\\ \frac{1}{\sqrt{2}}& -\frac{1}{\sqrt{2}}\end{array}\right)\left(\begin{array}{c}-\frac{1}{\sqrt{2}}\\ -\frac{1}{\sqrt{2}}\end{array}\right)=\left(\begin{array}{c}-1\\ 0\end{array}\right)$

and on our Bloch circle:

The Deutsch oracle problem

We’re going to write a system with multiple gates so that we can actually find a result to a question faster than on a classical computer.

The question is: Given an unknown function, is this function constant (Set-0 / Set-1) or is this function variable (Identity / Negation)?

Classical approach

On a classical computer it could look like this:

And in order to know what the function is, we can use 2 queries:

f(0)	f(1)	Result
0	0	f = Set-0
0	1	f = Identity
1	0	f = Negation
1	1	f = Set-1

Knowing if the function is constant or variable takes also 2 queries.

Quantum approach

On a quantum computer, remember that our function has to be reversible so we need a way for Set-0 and Set-1 to be reversible as well first.

The way to do it is to actually rewire our system to use multiple qubits for all the operations: Identity, Negation, Set-0, Set-1.

In the real world, note that qubits are resources that are changed, so in this case, we need 2 qubits:

• the input qubit that is left unchanged (in blue)
• the output qubit where the result is written (in red)

It’s intuitive to understand that having the input qubit left unchanged gives us an information for Set-0 and Set-1 that allows us to know what the function is.

Let’s now write all our operations using 2 qubits with the input the MSB (most significant bit) and the output the LSB (least significant bit).

It is normal to be confused by this part at first but hopefully it gets clearer afterwards.

To recap: we want to write all our operations as reversible operations (because this is how quantum computers work) and to do this, we pass an additional “output” qubit as input to our function. This qubit is initialized to $|0⟩$ and is used to write the result of the operation, while the input qubit on the other hand is left unchanged. We’ll see that using 2 qubits allows us to write reversible operations.

Set-0

In this case, we have nothing to do, the output qubit is already set to 0, and we want to leave the input qubit unchanged, so we can just leave our qubits as they are.

Step	$|00⟩$	$|10⟩$
	$f(|00⟩)=|00⟩$	$f(|10⟩)=|10⟩$
identity	$\left(\begin{array}{cccc}1& 0& 0& 0\\ 0& 1& 0& 0\\ 0& 0& 1& 0\\ 0& 0& 0& 1\end{array}\right)\left(\begin{array}{c}1\\ 0\\ 0\\ 0\end{array}\right)=\left(\begin{array}{c}1\\ 0\\ 0\\ 0\end{array}\right)$	$\left(\begin{array}{cccc}1& 0& 0& 0\\ 0& 1& 0& 0\\ 0& 0& 1& 0\\ 0& 0& 0& 1\end{array}\right)\left(\begin{array}{c}0\\ 0\\ 1\\ 0\end{array}\right)=\left(\begin{array}{c}0\\ 0\\ 1\\ 0\end{array}\right)$

Set-1

This time we have to flip our “output” qubit so it becomes 1, we just added a negation gate.

Step	$|00⟩$	$|10⟩$
	$f(|00⟩)=|01⟩$	$f(|10⟩)=|11⟩$
identity	$\left(\begin{array}{cccc}1& 0& 0& 0\\ 0& 1& 0& 0\\ 0& 0& 1& 0\\ 0& 0& 0& 1\end{array}\right)\left(\begin{array}{c}1\\ 0\\ 0\\ 0\end{array}\right)=\left(\begin{array}{c}1\\ 0\\ 0\\ 0\end{array}\right)=\left(\begin{array}{c}1\\ 0\end{array}\right)\otimes \left(\begin{array}{c}1\\ 0\end{array}\right)$	$\left(\begin{array}{cccc}1& 0& 0& 0\\ 0& 1& 0& 0\\ 0& 0& 1& 0\\ 0& 0& 0& 1\end{array}\right)\left(\begin{array}{c}0\\ 0\\ 1\\ 0\end{array}\right)=\left(\begin{array}{c}0\\ 0\\ 1\\ 0\end{array}\right)=\left(\begin{array}{c}0\\ 1\end{array}\right)\otimes \left(\begin{array}{c}1\\ 0\end{array}\right)$
X	$\left(\begin{array}{c}1\\ 0\end{array}\right)\otimes \left(\begin{array}{cc}0& 1\\ 1& 0\end{array}\right)\left(\begin{array}{c}1\\ 0\end{array}\right)=\left(\begin{array}{c}1\\ 0\end{array}\right)\otimes \left(\begin{array}{c}0\\ 1\end{array}\right)=\left(\begin{array}{c}0\\ 1\\ 0\\ 0\end{array}\right)$	$\left(\begin{array}{c}0\\ 1\end{array}\right)\otimes \left(\begin{array}{cc}0& 1\\ 1& 0\end{array}\right)\left(\begin{array}{c}1\\ 0\end{array}\right)=\left(\begin{array}{c}0\\ 1\end{array}\right)\otimes \left(\begin{array}{c}0\\ 1\end{array}\right)=\left(\begin{array}{c}0\\ 0\\ 0\\ 1\end{array}\right)$

Identity

In this case we have to use a CNOT gate, with the input as the control bit.

Step	$|00⟩$	$|10⟩$
	$f(|00⟩)=|00⟩$	$f(|10⟩)=|11⟩$
CNOT	$C(\left(\begin{array}{c}1\\ 0\end{array}\right)\otimes \left(\begin{array}{c}1\\ 0\end{array}\right))=\left(\begin{array}{cccc}1& 0& 0& 0\\ 0& 1& 0& 0\\ 0& 0& 0& 1\\ 0& 0& 1& 0\end{array}\right)\left(\begin{array}{c}1\\ 0\\ 0\\ 0\end{array}\right)=\left(\begin{array}{c}1\\ 0\\ 0\\ 0\end{array}\right)$	$C(\left(\begin{array}{c}0\\ 1\end{array}\right)\otimes \left(\begin{array}{c}1\\ 0\end{array}\right))=\left(\begin{array}{cccc}1& 0& 0& 0\\ 0& 1& 0& 0\\ 0& 0& 0& 1\\ 0& 0& 1& 0\end{array}\right)\left(\begin{array}{c}0\\ 0\\ 1\\ 0\end{array}\right)=\left(\begin{array}{c}0\\ 0\\ 0\\ 1\end{array}\right)$

Negation

And negation is pretty much same as identity with the CNOT gate, where we just flip the result by adding a negation gate.

Step	$|00⟩$	$|10⟩$
	$f(|00⟩)=|01⟩$	$f(|10⟩)=|10⟩$
CNOT	$C(\left(\begin{array}{c}1\\ 0\end{array}\right)\otimes \left(\begin{array}{c}1\\ 0\end{array}\right))=\left(\begin{array}{cccc}1& 0& 0& 0\\ 0& 1& 0& 0\\ 0& 0& 0& 1\\ 0& 0& 1& 0\end{array}\right)\left(\begin{array}{c}1\\ 0\\ 0\\ 0\end{array}\right)=\left(\begin{array}{c}1\\ 0\\ 0\\ 0\end{array}\right)=\left(\begin{array}{c}1\\ 0\end{array}\right)\otimes \left(\begin{array}{c}1\\ 0\end{array}\right)$	$C(\left(\begin{array}{c}0\\ 1\end{array}\right)\otimes \left(\begin{array}{c}1\\ 0\end{array}\right))=\left(\begin{array}{cccc}1& 0& 0& 0\\ 0& 1& 0& 0\\ 0& 0& 0& 1\\ 0& 0& 1& 0\end{array}\right)\left(\begin{array}{c}0\\ 0\\ 1\\ 0\end{array}\right)=\left(\begin{array}{c}0\\ 0\\ 0\\ 1\end{array}\right)=\left(\begin{array}{c}0\\ 1\end{array}\right)\otimes \left(\begin{array}{c}0\\ 1\end{array}\right)$
X	$\left(\begin{array}{c}1\\ 0\end{array}\right)\otimes \left(\begin{array}{cc}0& 1\\ 1& 0\end{array}\right)\left(\begin{array}{c}1\\ 0\end{array}\right)=\left(\begin{array}{c}1\\ 0\end{array}\right)\otimes \left(\begin{array}{c}0\\ 1\end{array}\right)=\left(\begin{array}{c}0\\ 1\\ 0\\ 0\end{array}\right)$	$\left(\begin{array}{c}0\\ 1\end{array}\right)\otimes \left(\begin{array}{cc}0& 1\\ 1& 0\end{array}\right)\left(\begin{array}{c}0\\ 1\end{array}\right)=\left(\begin{array}{c}0\\ 1\end{array}\right)\otimes \left(\begin{array}{c}1\\ 0\end{array}\right)=\left(\begin{array}{c}0\\ 0\\ 1\\ 0\end{array}\right)$

$f(|00⟩)=|01⟩$

$f(|10⟩)=|10⟩$

Resolution

Now that we defined all the operations using 2 qubits, how can we know if a function is constant or variable using a single query?

The solution is to:

1. initialize 2 qubits to $|0⟩$
2. apply a bit flip, so both are now $|1⟩$
3. apply the Hadamard gate, so both are now in equal superposition: $\left(\begin{array}{c}\frac{1}{\sqrt{2}}\\ -\frac{1}{\sqrt{2}}\end{array}\right)$
4. apply the function f
5. apply the Hadamard gate again
6. measure the result:

• if the function is constant, it should be $|11⟩$
• if the function is variable, it should be $|01⟩$

After the first 3 steps, both qubits are always in state: $\left(\begin{array}{c}\frac{1}{\sqrt{2}}\\ -\frac{1}{\sqrt{2}}\end{array}\right)$

Let see what happens from each function:

Set-0

Step		Notes
4. Apply Set-0 gate	$f(\left(\begin{array}{c}\frac{1}{\sqrt{2}}\\ -\frac{1}{\sqrt{2}}\end{array}\right)\otimes \left(\begin{array}{c}\frac{1}{\sqrt{2}}\\ -\frac{1}{\sqrt{2}}\end{array}\right))=\left(\begin{array}{c}\frac{1}{\sqrt{2}}\\ -\frac{1}{\sqrt{2}}\end{array}\right)\otimes \left(\begin{array}{c}\frac{1}{\sqrt{2}}\\ -\frac{1}{\sqrt{2}}\end{array}\right)$	Input and Output are left unchanged
5. Apply H gate to each qubits	$H(\left(\begin{array}{c}\frac{1}{\sqrt{2}}\\ -\frac{1}{\sqrt{2}}\end{array}\right))=\left(\begin{array}{cc}\frac{1}{\sqrt{2}}& \frac{1}{\sqrt{2}}\\ \frac{1}{\sqrt{2}}& -\frac{1}{\sqrt{2}}\end{array}\right)\left(\begin{array}{c}\frac{1}{\sqrt{2}}\\ -\frac{1}{\sqrt{2}}\end{array}\right)=\left(\begin{array}{c}0\\ 1\end{array}\right)$ $H(\left(\begin{array}{c}\frac{1}{\sqrt{2}}\\ -\frac{1}{\sqrt{2}}\end{array}\right))=\left(\begin{array}{cc}\frac{1}{\sqrt{2}}& \frac{1}{\sqrt{2}}\\ \frac{1}{\sqrt{2}}& -\frac{1}{\sqrt{2}}\end{array}\right)\left(\begin{array}{c}\frac{1}{\sqrt{2}}\\ -\frac{1}{\sqrt{2}}\end{array}\right)=\left(\begin{array}{c}0\\ 1\end{array}\right)$

which gives us: $|11⟩$

Input Qubit

Output Qubit

$\left(\begin{array}{c}-1\\ 0\end{array}\right)$ $\left(\begin{array}{c}0\\ 1\end{array}\right)$ $\left(\begin{array}{c}1\\ 0\end{array}\right)$ $\left(\begin{array}{c}0\\ -1\end{array}\right)$ $\left(\begin{array}{c}-\frac{1}{\sqrt{2}}\\ \frac{1}{\sqrt{2}}\end{array}\right)$ $\left(\begin{array}{c}\frac{1}{\sqrt{2}}\\ \frac{1}{\sqrt{2}}\end{array}\right)$ $\left(\begin{array}{c}-\frac{1}{\sqrt{2}}\\ -\frac{1}{\sqrt{2}}\end{array}\right)$ $\left(\begin{array}{c}\frac{1}{\sqrt{2}}\\ -\frac{1}{\sqrt{2}}\end{array}\right)$

$\left(\begin{array}{c}-1\\ 0\end{array}\right)$ $\left(\begin{array}{c}0\\ 1\end{array}\right)$ $\left(\begin{array}{c}1\\ 0\end{array}\right)$ $\left(\begin{array}{c}0\\ -1\end{array}\right)$ $\left(\begin{array}{c}-\frac{1}{\sqrt{2}}\\ \frac{1}{\sqrt{2}}\end{array}\right)$ $\left(\begin{array}{c}\frac{1}{\sqrt{2}}\\ \frac{1}{\sqrt{2}}\end{array}\right)$ $\left(\begin{array}{c}-\frac{1}{\sqrt{2}}\\ -\frac{1}{\sqrt{2}}\end{array}\right)$ $\left(\begin{array}{c}\frac{1}{\sqrt{2}}\\ -\frac{1}{\sqrt{2}}\end{array}\right)$

Set-1

Step		Notes
4. Apply Set-1 gate	$f(\left(\begin{array}{c}\frac{1}{\sqrt{2}}\\ -\frac{1}{\sqrt{2}}\end{array}\right)\otimes \left(\begin{array}{c}\frac{1}{\sqrt{2}}\\ -\frac{1}{\sqrt{2}}\end{array}\right))=\left(\begin{array}{c}\frac{1}{\sqrt{2}}\\ -\frac{1}{\sqrt{2}}\end{array}\right)\otimes \left(\begin{array}{c}-\frac{1}{\sqrt{2}}\\ \frac{1}{\sqrt{2}}\end{array}\right)$	Input is left unchanged Output is flipped
5. Apply H to each qubits	$H(\left(\begin{array}{c}\frac{1}{\sqrt{2}}\\ -\frac{1}{\sqrt{2}}\end{array}\right))=\left(\begin{array}{cc}\frac{1}{\sqrt{2}}& \frac{1}{\sqrt{2}}\\ \frac{1}{\sqrt{2}}& -\frac{1}{\sqrt{2}}\end{array}\right)\left(\begin{array}{c}\frac{1}{\sqrt{2}}\\ -\frac{1}{\sqrt{2}}\end{array}\right)=\left(\begin{array}{c}0\\ 1\end{array}\right)$ $H(\left(\begin{array}{c}-\frac{1}{\sqrt{2}}\\ \frac{1}{\sqrt{2}}\end{array}\right))=\left(\begin{array}{cc}\frac{1}{\sqrt{2}}& \frac{1}{\sqrt{2}}\\ \frac{1}{\sqrt{2}}& -\frac{1}{\sqrt{2}}\end{array}\right)\left(\begin{array}{c}-\frac{1}{\sqrt{2}}\\ \frac{1}{\sqrt{2}}\end{array}\right)=\left(\begin{array}{c}0\\ -1\end{array}\right)$

which gives us: $|11⟩$

Note that $\left(\begin{array}{c}0\\ -1\end{array}\right)=|1⟩$ simply because there is a probability || − 1||² to be 1.

Input Qubit

Output Qubit

$\left(\begin{array}{c}-1\\ 0\end{array}\right)$ $\left(\begin{array}{c}0\\ 1\end{array}\right)$ $\left(\begin{array}{c}1\\ 0\end{array}\right)$ $\left(\begin{array}{c}0\\ -1\end{array}\right)$ $\left(\begin{array}{c}-\frac{1}{\sqrt{2}}\\ \frac{1}{\sqrt{2}}\end{array}\right)$ $\left(\begin{array}{c}\frac{1}{\sqrt{2}}\\ \frac{1}{\sqrt{2}}\end{array}\right)$ $\left(\begin{array}{c}-\frac{1}{\sqrt{2}}\\ -\frac{1}{\sqrt{2}}\end{array}\right)$ $\left(\begin{array}{c}\frac{1}{\sqrt{2}}\\ -\frac{1}{\sqrt{2}}\end{array}\right)$

$\left(\begin{array}{c}-1\\ 0\end{array}\right)$ $\left(\begin{array}{c}0\\ 1\end{array}\right)$ $\left(\begin{array}{c}1\\ 0\end{array}\right)$ $\left(\begin{array}{c}0\\ -1\end{array}\right)$ $\left(\begin{array}{c}-\frac{1}{\sqrt{2}}\\ \frac{1}{\sqrt{2}}\end{array}\right)$ $\left(\begin{array}{c}\frac{1}{\sqrt{2}}\\ \frac{1}{\sqrt{2}}\end{array}\right)$ $\left(\begin{array}{c}-\frac{1}{\sqrt{2}}\\ -\frac{1}{\sqrt{2}}\end{array}\right)$ $\left(\begin{array}{c}\frac{1}{\sqrt{2}}\\ -\frac{1}{\sqrt{2}}\end{array}\right)$

Identity

Step		Notes
4. Apply Identity gate	$f(\left(\begin{array}{c}\frac{1}{\sqrt{2}}\\ -\frac{1}{\sqrt{2}}\end{array}\right)\otimes \left(\begin{array}{c}\frac{1}{\sqrt{2}}\\ -\frac{1}{\sqrt{2}}\end{array}\right))=\left(\begin{array}{c}\frac{1}{\sqrt{2}}\\ \frac{1}{\sqrt{2}}\end{array}\right)\otimes \left(\begin{array}{c}\frac{1}{\sqrt{2}}\\ -\frac{1}{\sqrt{2}}\end{array}\right)$	$C(\left(\begin{array}{c}\frac{1}{\sqrt{2}}\\ -\frac{1}{\sqrt{2}}\end{array}\right)\otimes \left(\begin{array}{c}\frac{1}{\sqrt{2}}\\ -\frac{1}{\sqrt{2}}\end{array}\right))=\left(\begin{array}{cccc}1& 0& 0& 0\\ 0& 1& 0& 0\\ 0& 0& 0& 1\\ 0& 0& 1& 0\end{array}\right)\left(\begin{array}{c}\frac{1}{2}\\ -\frac{1}{2}\\ -\frac{1}{2}\\ \frac{1}{2}\end{array}\right)=\frac{1}{2}\left(\begin{array}{cccc}1& 0& 0& 0\\ 0& 1& 0& 0\\ 0& 0& 0& 1\\ 0& 0& 1& 0\end{array}\right)\left(\begin{array}{c}1\\ -1\\ -1\\ 1\end{array}\right)$ $=\frac{1}{2}\left(\begin{array}{c}1\\ -1\\ 1\\ -1\end{array}\right)=\left(\begin{array}{c}\frac{1}{2}\\ -\frac{1}{2}\\ \frac{1}{2}\\ -\frac{1}{2}\end{array}\right)=\left(\begin{array}{c}\frac{1}{\sqrt{2}}\\ \frac{1}{\sqrt{2}}\end{array}\right)\otimes \left(\begin{array}{c}\frac{1}{\sqrt{2}}\\ -\frac{1}{\sqrt{2}}\end{array}\right)$
5. Apply H to each qubits	$H(\left(\begin{array}{c}\frac{1}{\sqrt{2}}\\ \frac{1}{\sqrt{2}}\end{array}\right))=\left(\begin{array}{cc}\frac{1}{\sqrt{2}}& \frac{1}{\sqrt{2}}\\ \frac{1}{\sqrt{2}}& -\frac{1}{\sqrt{2}}\end{array}\right)\left(\begin{array}{c}\frac{1}{\sqrt{2}}\\ \frac{1}{\sqrt{2}}\end{array}\right)=\left(\begin{array}{c}1\\ 0\end{array}\right)$ $H(\left(\begin{array}{c}\frac{1}{\sqrt{2}}\\ -\frac{1}{\sqrt{2}}\end{array}\right))=\left(\begin{array}{cc}\frac{1}{\sqrt{2}}& \frac{1}{\sqrt{2}}\\ \frac{1}{\sqrt{2}}& -\frac{1}{\sqrt{2}}\end{array}\right)\left(\begin{array}{c}\frac{1}{\sqrt{2}}\\ -\frac{1}{\sqrt{2}}\end{array}\right)=\left(\begin{array}{c}0\\ 1\end{array}\right)$

which gives us: $|01⟩$

Input Qubit

Output Qubit

$\left(\begin{array}{c}-1\\ 0\end{array}\right)$ $\left(\begin{array}{c}0\\ 1\end{array}\right)$ $\left(\begin{array}{c}1\\ 0\end{array}\right)$ $\left(\begin{array}{c}0\\ -1\end{array}\right)$ $\left(\begin{array}{c}-\frac{1}{\sqrt{2}}\\ \frac{1}{\sqrt{2}}\end{array}\right)$ $\left(\begin{array}{c}\frac{1}{\sqrt{2}}\\ \frac{1}{\sqrt{2}}\end{array}\right)$ $\left(\begin{array}{c}-\frac{1}{\sqrt{2}}\\ -\frac{1}{\sqrt{2}}\end{array}\right)$ $\left(\begin{array}{c}\frac{1}{\sqrt{2}}\\ -\frac{1}{\sqrt{2}}\end{array}\right)$

$\left(\begin{array}{c}-1\\ 0\end{array}\right)$ $\left(\begin{array}{c}0\\ 1\end{array}\right)$ $\left(\begin{array}{c}1\\ 0\end{array}\right)$ $\left(\begin{array}{c}0\\ -1\end{array}\right)$ $\left(\begin{array}{c}-\frac{1}{\sqrt{2}}\\ \frac{1}{\sqrt{2}}\end{array}\right)$ $\left(\begin{array}{c}\frac{1}{\sqrt{2}}\\ \frac{1}{\sqrt{2}}\end{array}\right)$ $\left(\begin{array}{c}-\frac{1}{\sqrt{2}}\\ -\frac{1}{\sqrt{2}}\end{array}\right)$ $\left(\begin{array}{c}\frac{1}{\sqrt{2}}\\ -\frac{1}{\sqrt{2}}\end{array}\right)$

Negation

Step		Notes
4. Apply Identity gate	$f(\left(\begin{array}{c}\frac{1}{\sqrt{2}}\\ -\frac{1}{\sqrt{2}}\end{array}\right)\otimes \left(\begin{array}{c}\frac{1}{\sqrt{2}}\\ -\frac{1}{\sqrt{2}}\end{array}\right))=\left(\begin{array}{c}\frac{1}{\sqrt{2}}\\ \frac{1}{\sqrt{2}}\end{array}\right)\otimes \left(\begin{array}{c}-\frac{1}{\sqrt{2}}\\ \frac{1}{\sqrt{2}}\end{array}\right)$	Same as previously but with an additional bit flip on the output
5. Apply H to each qubits	$H(\left(\begin{array}{c}\frac{1}{\sqrt{2}}\\ \frac{1}{\sqrt{2}}\end{array}\right))=\left(\begin{array}{cc}\frac{1}{\sqrt{2}}& \frac{1}{\sqrt{2}}\\ \frac{1}{\sqrt{2}}& -\frac{1}{\sqrt{2}}\end{array}\right)\left(\begin{array}{c}\frac{1}{\sqrt{2}}\\ \frac{1}{\sqrt{2}}\end{array}\right)=\left(\begin{array}{c}1\\ 0\end{array}\right)$ $H(\left(\begin{array}{c}-\frac{1}{\sqrt{2}}\\ \frac{1}{\sqrt{2}}\end{array}\right))=\left(\begin{array}{cc}\frac{1}{\sqrt{2}}& \frac{1}{\sqrt{2}}\\ \frac{1}{\sqrt{2}}& -\frac{1}{\sqrt{2}}\end{array}\right)\left(\begin{array}{c}-\frac{1}{\sqrt{2}}\\ \frac{1}{\sqrt{2}}\end{array}\right)=\left(\begin{array}{c}0\\ -1\end{array}\right)$

which gives us: $|01⟩$

Input Qubit

Output Qubit

$\left(\begin{array}{c}-1\\ 0\end{array}\right)$ $\left(\begin{array}{c}0\\ 1\end{array}\right)$ $\left(\begin{array}{c}1\\ 0\end{array}\right)$ $\left(\begin{array}{c}0\\ -1\end{array}\right)$ $\left(\begin{array}{c}-\frac{1}{\sqrt{2}}\\ \frac{1}{\sqrt{2}}\end{array}\right)$ $\left(\begin{array}{c}\frac{1}{\sqrt{2}}\\ \frac{1}{\sqrt{2}}\end{array}\right)$ $\left(\begin{array}{c}-\frac{1}{\sqrt{2}}\\ -\frac{1}{\sqrt{2}}\end{array}\right)$ $\left(\begin{array}{c}\frac{1}{\sqrt{2}}\\ -\frac{1}{\sqrt{2}}\end{array}\right)$

$\left(\begin{array}{c}-1\\ 0\end{array}\right)$ $\left(\begin{array}{c}0\\ 1\end{array}\right)$ $\left(\begin{array}{c}1\\ 0\end{array}\right)$ $\left(\begin{array}{c}0\\ -1\end{array}\right)$ $\left(\begin{array}{c}-\frac{1}{\sqrt{2}}\\ \frac{1}{\sqrt{2}}\end{array}\right)$ $\left(\begin{array}{c}\frac{1}{\sqrt{2}}\\ \frac{1}{\sqrt{2}}\end{array}\right)$ $\left(\begin{array}{c}-\frac{1}{\sqrt{2}}\\ -\frac{1}{\sqrt{2}}\end{array}\right)$ $\left(\begin{array}{c}\frac{1}{\sqrt{2}}\\ -\frac{1}{\sqrt{2}}\end{array}\right)$

Recap

• Using our system with Set-0 and Set-1 operations, we end up with $|11⟩$ as the output
• Using our system with Identity and Negation operations, we end up with $|01⟩$ as the output

For each those cases, it took us 1 single query to the operation as opposed to 2 queries on a classic computer.

The Deutsch–Jozsa algorithm generalizes the idea using functions that take N-bit input and generate single 0 or 1 bit, i.e. f{0, 1}ⁿ → {0, 1}