Deutsch-Jozsa Algorithm, The Algorithm That Showed The Promise Of Quantum Advantage By Co-Discoverer David Deutsch

Perhaps one of the best ways to illustrate the power of quantum computing is with an illustrative calculation algorithm that shows the power of quantum parallelism. We look at the basics of Quantum Computing and then the Deutsch Algorithm.

Deutsch-Jozsa Algorithm

Quantum Calculations

One of the significant benefits of using a Quantum Computer over a classical computer is the computational efficiency of performing calculations. For those familiar with creating or building algorithms, you’ll know there is every advantage in usually making these run as quickly as possible, given fixed resources. Whether that is a search over microseconds or a simulation to find valuable drugs, performing calculations as effectively as possible is fundamental to our lives. Quantum Computing is a way of getting the most “bang for the buck” with specific problems.

Of course, as you might expect, it is not that easy, and not every problem can be formulated in a Quantum way and thus be more efficient. The challenge of computing is finding appropriate ways to apply quantum techniques to solve some of the world’s challenges. If one can perform calculations faster, then one could argue that humanity improves, as many problems can be related to the ability to perform calculations quickly. Machine Intelligence tasks, Drug Discovery. Imagine examples such as self-driving, which many might argue is related to the ability to compute vast amounts of data in a real-world setting.

Who is David Deutsch?

David Deutsch is one of the most eminent scientists in the Quantum Computing Space. Some might even call him the forefather of Quantum Computing. Deutsch is a British physicist at the University of Oxford—a professor and Fellow of the Royal Society (FRS). If you want to read more about David Deutsch and his scientific innovations, stop by our article on the forefather of Quantum Computing, or you can even go to his website here.

Deutsch Is A British Physicist At The University Of Oxford—A Professor And Fellow Of The Royal Society (Frs) — Deutsch is a British physicist at the University of Oxford—a professor and Fellow of the Royal Society (FRS)

Quantum Parallelism Explained

In a nutshell, this allows us to evaluate many functions simultaneously. In more detail, given a function f(x), the quantum version somehow (magically) allows us to compute the function for multiple values of x – so-called more bang for the buck. I want to spell out how crazy this is. Imagine you could have a function, and for the price of evaluating it once, you could effectively evaluate it twice. Yes, it seems odd, but as we all know, quantum mechanics is odd, so let’s explore the mechanisms behind this strange claim further.

How the Magic Happens in the Deutsch Jozsa Algorithm

Introduction

First, you should know that the Deutsch Jozsa Algorithm is an extension of the Deutsch Algorithm, and being simple creatures, we should master this first, hence part I. For some basics on Qubits, go here.

The setup and terminology

As this tries to assume little to no previous knowledge, that means we have to cover some of the basic machinery that Quantum Mechanics often use. So here are some of the basics (not complete beginner basics) you need.

Hadamard Function / Operator

This is one of the coolest operators in Quantum Physics. It turns a single qubit state into a superposition of states. Amazing. It has some cool properties in that it can operate on qubits in states 0 and 1. For details on qubits, follow the article here, which gives an easy guide to the world of qubits. Perhaps the essence is as follows:

If the Qubit is in state 0, the Hadamard Operator turns this into the following super-positional state:

$\Frac{1}{\Sqrt{2}}|0\Rangle + \Frac{1}{\Sqrt{2}}|1\Rangle$

And if the Qubit is in state 1, the operator turns this into the following Super-positional state:

$\Frac{1}{\Sqrt{2}}|0\Rangle - \Frac{1}{\Sqrt{2}}|1\Rangle$

Voila, that’s it. I’ll skip over the matrix form, but you can look this up here if you want. But the primary way of thinking about it is fundamental to Quantum Computing and provides many of the “tricks” that can be performed, so it is worth understanding with some depth.

XOR (adding bits)

Have we ever seen the truth table for the XOR function? Well, I’ll put it below, but the easy “way” to think about it is as follows: If the input bits (a and b) sum to 2, then make that sum rollover to 0 again. The XOR function, therefore, outputs a 0 half the time and a 1 the other half of the time. It has a whole load of really useful features, such as if the input bits are the same, we always output a 0, and if they are different, we get a 1. What an excellent function, and it is – not just in the classical space but quantum.

Sometimes, this function is best thought of as addition “modulo 2”. Often because of its utility a simple symbol can be used: $X \Oplus Y = Z$

Input (x)	Input (y)	XOR (z)
0	0	0
0	1	1
1	0	1
1	1	0

Unitary Functions

We now can construct a function named $U_F$ that is the same as working on our function $F(X)$ , which takes values and transforms the input into an output. Let us now explore what happens when we take this arbitrary function (it doesn’t matter what it is doing) and employ this in a simple quantum circuit. What is special about unitary functions is that if we perform the same operation or function again, we can reach the original state – a compelling and essential concept in Quantum Computing.

A Simple Quantum Circuit

We will have 2 inputs (much like our XOR function) and we will inspect the output. However instead of using regular classical bits, we will use Quantum bits or Qubits as our inputs and our function $U_F$ will operate on the quantum states.

We input $X$ , $Y$ and obtain new outputs $X$ and $Y \Oplus F(X)$ . In more Quantum parlance, we can say

$|X, Y\Rangle &Nbsp;\Rightarrow | X, Y \Oplus F(X) \Rangle$

Creating some Quantum Inputs to our circuit

For our input $X$ and $Y$ , lets use respectively turn $X$ into the superposition of $Deutsch-Jozsa Algorithm, The Algorithm That Showed The Promise Of Quantum Advantage By Co-Discoverer David Deutsch$ and $1$ states using the Hadamard gate $H(0)$ which gives:

$X = \Frac{1}{\Sqrt{2}}(|0\Rangle + |1\Rangle)$

Let’s have $Y$ as the “0” quantum state, giving us the following inputs

$Y = |0\Rangle$

Now let’s look at the output from our circuit after applying the unitary function:

$\Frac{1}{\Sqrt{2}}( |0, F(0)\Rangle + |1, F(1)\Rangle )$

This means our output state after applying the function we have a superposition state of two function evaluations. In a nut shell, we have performed two function evaluations for one function evaluation. Crazy, huh? Think about it: by inputting a superposition state, the quantum circuit can effectively evaluate our function two times! $F(0)$ and $F(1)$ , giving us the bang for our buck that we spoke about.

Multiverse – already this stuff is wacky

For those inquiring, please ask yourself where the calculation is being done. Could it be the Multiverse? For those who want to look more into the philosophy behind Quantum Computing, please do look into David Deutsch in more detail.

Tags: