USING QISKIT TO IMPLEMENT DEUTSCH-JOSZA’S ALGORITHM FOR CALIFORNIA HOUSING PRICE PREDICTION

Understanding quantum algorithm presupposes that one should have a clear dichotomy of what entails and what constitutes it in the simplest form. There’s no simple illustration or description one can give to quantum algorithm without getting out of bound for those with little physics and/or mathematics (linear algebra) background or experience.

While this article mainly focuses on implementation of Deutsch-Jozsa’s algorithm to predict California housing prices for some years, it will also give a thorough explanation on how Deutsch-Jozsa algorithm works. Understanding Deustch-Jozsa’s algorithm is the basis for understanding most of the quantum algorithm. The better you understand this algorithm, the easier it becomes when you face the harder ones like Grover’s, Simon’s, Shor’s algorithm etc.

I won’t be explaining how quantum gates work in this article, a better explanation is given by IBM Q Researchers and Educators. https://community.qiskit.org/education/

Enough of introduction, let’s dive into business.

Why is quantum computation such a big deal? Quantum computation exploits the inherent parallelism due to the principle of superposition of quantum states and hence has the potential to give many computational problems an exponential speedup. Most of the quantum algorithm mentioned above have been proven to some problems exponentially faster than their classical counterparts.

Deutsch-Jozsa’s algorithm is designed to solve the problem of identifying whether a binary function is constant or balanced. Its running time is 0(n) while classical method requires o(2^n).

The basic rules used in this article to implement Deutsch-Jozsa’s algorithm are as follows:

  • Initialized the quantum register/circuit
  • Put the registers in superposition of states
  • Include unitary operators to execute the quantum algorithm
  • Measure the states to get the result

There’s a quantum oracle which is mostly use to embodies step 3. Quantum oracle is similar to that of classical black box function. This oracle evaluate an unknown function

Image for post
Image for post

.

Given a value

Image for post
Image for post

the output after being executed by the oracle will be

Image for post
Image for post
Fig 1: Deutsch-Jozsa’s algorithm oracle
Image for post
Image for post

can either be a 1 or a 0, just like a classical bit. You might be thinking that what’s y doing in the algorithm. Well, according to quantum mechanics, a quantum oracle can only exist if it is reversible. Since quantum computers are reversible, therefore their inputs and outputs must also be reversible. Which is impossible in classical computer. So the additional input is added to create this reversible system and the output of the result is

Image for post
Image for post

where

Image for post
Image for post

denotes addition modulo 2 operator. That is, if y = 0 then the output is simply

Image for post
Image for post

A function

Image for post
Image for post

is said to be balanced if

Image for post
Image for post

and constant if

Image for post
Image for post

This might still be a little ambiguous, let’s use a table to illustrate what is being said above.

Given a function

Image for post
Image for post

we concluded from the function above that Deutsch-Jozsa’s algorithm will output

Image for post
Image for post

and make us understand if the function is balance i.e

Image for post
Image for post

or if it’s constant

Image for post
Image for post

The word balance in this sense means the output won’t be the same for every input you give the algorithm, and the word constant means it will return the same output as your input. Simple as that

Here is a table that illustrates Deutsch-Jozsa’s algorithm for a register of 3 qubits which is 8 classical bits. Input can either be one of the 8 bits below

Input = |000> |001> |010> |011> |100> |101> |110> |111>

Constant = 0 or 1 for all the inputs

If the function is balanced, the output of the eight input can either be

Balanced = |0 > |1 > |0> |1 > |0> |1 > |0> |1>

or

Balanced = |1> |0 > |1> |0 > |1> |0 > |1> |0>

For a given input, the table above give the possible output you should expect.

Let’s consider a function

Image for post
Image for post

that can predict whether the California housing price will increase or decrease for a given year.

x is a binary variable of 1 or 0 and years is the number of years we want to predict its value. So we want an algorithm that works this way f(x, years) = f(x). That is:

If

Image for post
Image for post

then California housing price will increase for that year.

If

Image for post
Image for post

then the California housing price will decrease for that year

If we try to do this in classical computer, we will have to try this in

Image for post
Image for post

queries, because we need to check every input up to

Image for post
Image for post

before we can make a reasonable conclusion, but a quantum computer will solve this just in 1 query.

Let’s start looking at the implementations.

Read a California housing data frame from google website, what we actually needed is the median price for each house, and for simplicity, the index of each price is the age of the house. Secondly, all necessary libraries to run the Qiskit were imported.

Image for post
Image for post
Fig 2: Importing Qiskit and Python libraries

As discussed above, we want to use the principle of superposition of quantum states to create a quantum parallelism. Applying hadamard gate as denoted as h in the code below put the system into a superposition.

Image for post
Image for post
Fig 3: Putting the quantum state into superposition by applying Hadamard gate

Now, let’s solve the problem. Now this code is implementing Deutsch-Jozsa’s algorithm to make a prediction. As explained earlier, if

Image for post
Image for post

, the housing price will increase. This is how the the quantum oracle goes. Let’s say today is 100 years as shown in the code below, if the housing price of the year we are predicting is greater than that of today, the circuit apply a NOT gate on the fourth gate. This gives us a constant value every time making sure

Image for post
Image for post

The second condition is that if

Image for post
Image for post

then apply a CNOT gate. The control of the CNOT can be on any of the three qubits, and the target on the fourth qubit.

Image for post
Image for post
Fig 4: Implementing Deutsch-Jozsa’s algorithm on a given California of data

Then give this quantum program to qasm simulator to visualize what our code is doing.

Image for post
Image for post
Fig 5: Giving the quantum program to qasm simulator

After running the code on the simulator, it requested for 4 inputs, 3 which is binary to initialize the state of the quantum systems and the fourth input which is 21 is this case. The output shows that the Predicted value will be less than the current value. That is,

Image for post
Image for post
Image for post
Image for post
Fig 6: Circuit of the quantum system

Lastly, let’s make a plot and see the output of our prediction. We input 110, we get the output of 101 in 1 shot. This shows that

Image for post
Image for post

is balanced, and our predicted housing price will decrease.

Image for post
Image for post
Fig 7: Output plot

This article has given a simple explanation of Deutsch-Jozsa’s algorithm implementation. For further understanding of quantum computing and quantum algorithm implementation, good resources are available on QISKIT website. https://qiskit.org

Some people call me unstable force, while some say I'm quantum dot.

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store