Quantum Tutorial

Deutsch-Jozsa Algorithm, the easy way

February 11, 2019

Perhaps one of the best ways of illustrating the power of Quantum Computing is will an illustrative calculation algorithm that shows the power of Quantum Parallelism. Here is part I we we look at the basics and then the Deutsch Algorithm.

Quantum Parallelism

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

Of course as you might expect it is not that easy – and not every problem can be formulated in a Quantum way and thus more efficient. The challenge of computing is to be able to find appropriate ways to apply Quantum Techniques to solve some of the challenges that the world faces. 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 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 innovations in science then do stop by the Wikipedia article or you can even go to his website here.

David Deutsch. Professor of Physics at Oxford University. He is one of the most influential scientists working at the fundamentals of Quantum Mechanics and Physics. One of the most profound thinkers of our time – famous for the Deutsch Algorithm and the Deutsch-Jozsa Algorithm which have paved the way for Quantum Computing.

Quantum Parallelism Explained

In a nutshell this allows us to evaluate many functions apparently simultaneously. In more details, given a function f(x), then the quantum version somehow (magically) allows us to compute the function for multiple values of x – so called more bang for the buck. Just to spell out how mad 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 rather odd, so lets explore further the mechanisms behind this strange claim.

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 set-up and terminology

As this tries to assume little to know 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. Basically it turns a single qubit state into a super position of states. Amazing. It has some cool properties in that it can operate on qubits in state 0 and 1. For details on qubits, follow the article here, which gives an easy guide to the world of the qubit. 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. The matrix form, I’ll skip over, but if you really want, you can look this up here. But the basic way of thinking about it is fundamental to the concept of Quantum Computing and provides many of the “tricks” that can be performed, so it is worth understanding with some depth.

XOR (adding bits)

Ever seen the truth table for the XOR function? Well its simple, 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 the fact that if the input bits are the same we always output a 0 and if they are different we get a 1. What a cool function, and it is – not just in the classical space but quantum too.

Sometimes this function is best thought of addition “modulo 2”. Often because of its utility a simple symbol can be used: x \oplus y = z

Input (x)Input (y)XOR (z)
000
011
101
110

Unitary Functions

We now can construct a function named U_f that is the same as working on out 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 really 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 get to the original state – a very powerful and important 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  \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 0 and 1 states using the Hadamard gate H(0) which gives:

x = \frac{1}{\sqrt{2}}(|0\rangle + |1\rangle)

Lets have y as the “0” quantum state, giving us the following inputs

y = |0\rangle

Now lets 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 of you with an inquiring mind, please ask yourself where the calculation is being done. For those who want to look more into the philosophy behind Quantum Computing, please do look into David Deutsch in more detail.

Leave a Reply

Your email address will not be published.