How to Implement the Deutsch-Jozsa Algorithm in Haskell

We have already mentioned this algorithm when solving the simplest tasks in quantum computations. Let’s go on developing the framework and review the initial algorithm enhancement, named the Deutsch-Jozsa algorithm. It is another article in the series about the model of quantum computations. That’s why you’d better read the previous articles, as they will help you to understand all the things here. You should refer to the first three articles:

1. A Few Words About Reversible Computing
   
2. How to Implement Deutsch’s Algorithm in Haskell
   
3. Quantum Circuit Design: Methods and Techniques
   

Today you will find out about the way to build an oracle on the basis of the given definition of a binary function. We will build it not manually, like we used to before, but automatically. You will also learn how to understand the function type with the help of the only one oracle call. We will also carry out an experiment, the results of which were quite a surprise for me. If all of this sounds interesting, you’re most welcome to join the journey.

Brief Historical Background and Some Mathematical Descriptions

In 1985, David Deutsch developed the first algorithm within the limits of the model of quantum computations. To tell the truth, it was quite a breakthrough, as this algorithm was the first to show the superiority of the model of quantum computations over the classical one. It became a case study for researchers. As a result, there appeared such breakthrough algorithms as Shor’s algorithm, and also his discrete logarithm. Both of them give no peace to cryptographers and cryptanalysts.

The Deutsch task itself is not really demonstrative. But he was the one to notice that with the help of the model of quantum computations, we can concurrently calculate values of some binary function on the entire set of input values. Since we can convert the input qubits to the equally probable superposition of all basis states, and then apply the defined function, that is when quantum parallelism will show itself. But what’s next? It is impossible to get all the acquired values of the function. As a result of the measurement, with some or other probability, we will get one value from the entire set. There’s one thing spotted by David Deutsch. Before the measurement, the resulting state of the quantum register hides all the set of function values. Applying the necessary manipulations to the quantum register, we can get the information about some basic properties of the function. Thus, we will get not some specific values of the function, but the information about its basic properties.

Finally, there appears the Deutsch task, in which we should realize, whether the binary function on one binary element is constant or balanced (again — read the post about this algorithm). The function property as balanced or constant is the example of the basic property of the function. This means that we can apply the principle of quantum parallelism to the analysis of a basic property. That's exactly what David Deutsch did.

In 1992 Richard Jozsa suggested to deepen David Deutsch’s task and consider f: {0, 1}n → {0, 1} function. So, we will not restrict ourselves to the four functions mentioned before. But the problem is that the number of such various functions is equal to 2²ⁿ. The bigger part of this number is formed by the functions that are neither constant, nor balanced. Therefore, the task was stated quite artificially. Namely, they limited the number of possible types of the function. It can be either constant, or balanced.

The Algorithm Description

However, the task deepening did not affect the algorithm complexity. In case of the Jozsa task, the algorithm remains the same. Here is the description of all the steps:

1. Initialize the initial states from n qubits. It should be equal to |0ⁿ>.
   
2. Apply the H⊗n Hadamard gate to the initial state for n qubits. As a result, there appears an equally probable superposition of all possible values of n qubits.
   
3. Apply the O_f oracle, which is built in a bit different way, than that reviewed in the Deutsch algorithm description.
   
4. Apply H⊗n Hadamard gate one more time.
   
5. Carry out the measurement. If we get |0ⁿ> value, the function is constant. If otherwise, it is balanced. (At that, we can use the value, acquired as a result of measurement, to get the general idea about the values, at which the function returns value of 1).
   

Here’s the chart of the quantum circuit of the described algorithm:

O_f oracle changes the phase to -1 in those quantum states, for which function f returns value of 1. There’s not much point in using the service qubit. The matrix with 1 and -1 at the main diagonal, and 0 at other positions, is unitary.

From a mathematical standpoint, the following things happen. The initial quantum state transforms to the equally probable superposition. Then, each quantum state of the superposition changes the phase sign, provided that the function accepts the value of 1 at this quantum state. After the second application of the Hadamard gate, all quantum states “collapse”. If the function is constant, then the destructive interference of phases of all quantum states, except for |0ⁿ>, takes place. As for |0ⁿ>, constructive interference takes place in it. The state amplitude becomes equal to 1.

It’s much simpler to understand all of this via examples. That’s why we will implement this algorithm with the help of the same functions and other programming entities we have already used when implementing the Deutsch's algorithm. The Deutsch-Jozsa algorithm is very interesting for carrying out various experiments and measurements of frequency probabilities. Therefore, we will provide some enhancement of the developed functions and describe an interesting experiment.

The Algorithm Implementation

First of all, let’s define the function to create oracles. It’s good that we used to define oracles in the form of a matrix, as this will allow us to perfect our skills in quantum circuit design. Anyway, it’s time to create a normal function for building an oracle for the Deutsch-Jozsa algorithm, using an arbitrary f: {0, 1}n → {0, 1} function. Here’s the definition:

makeOracle :: ([Bool] -> Bool) -> Int
 -> Matrix (Complex Double)
makeOracle f n = matrixToComplex $
 zipWith makeLine domain [1..2^n]
 where
 zeroes = replicate (2^n) 0
 domain = replicateM n [False, True]
 makeLine :: [Bool] -> Int -> [Int]
 makeLine x i = changeElement zeroes i
((-1)^(if f x then 1 else 0)) 

makeOracle function accepts function f of [Bool] -> Bool type. It also accepts n  — the number of qubits. Then, it will build the entire domain of definition of the function (domain), representing a list of all possible combinations of False and True values n long. The domain of definition (the list length is 2ⁿ) joins in pairs with the list of indices from 1 to 2ⁿ. It is necessary for building a matrix.

We will build the oracle matrix with the help of the locally defined makeLine function, which builds one matrix line. Then, it changes the element in the list of zeros of the length of 2ⁿ to 1 or -1, depending on the function value. The element stands at the position that is equal to the matrix line number.

After that, the matrix transforms into a complex-valued one, by using the already known matrixToComplex function, and returns as a result.

There’s also a call for changeElement function that changes the element in the list at the defined position. Its definition is really simple:

changeElement :: [a] -> Int -> a -> [a]
changeElement xs i x = take (i - 1) xs ++
 [x] ++
 drop i xs

The dimension of the list and the element number are not checked for adequacy. Therefore, the developer should control these things himself.

Now we can apply makeOracle to build the oracle. For the purposes of our experiment, let’s create nine oracles:

oracle :: Int -> [Bool] -> Bool
oracle 1 [_, _, _] = False
oracle 2 [x, y, z] = x && y && z
oracle 3 [x, y, _] = x && y
oracle 4 [x, y, z] = x && (z || y && not z)
oracle 5 [x, _, _] = x
oracle 6 [x, y, z] = y && z || x && (not y || y && not z)
oracle 7 [x, y, z] = y || oracle 6 [x, y, z]
oracle 8 [x, y, z] = x || y || z
oracle 9 [_, _, _] = True

The first argument of oracle function accepts the oracle number. The partial application of this function with the number gives a function that is expected by makeOracle function. This approach allows using lists of numbers for the mass call of the function, which is going to be used further.

The following table shows the way all the nine oracles are defined:

X1	X2	X3	f
			1	2	3	4	5	6	7	8	9
0	0	0	0	0	0	0	0	0	0	0	1
0	0	1	0	0	0	0	0	0	0	1	1
0	1	0	0	0	0	0	0	0	1	1	1
0	1	1	0	0	0	0	0	1	1	1	1
1	0	0	0	0	0	0	1	1	1	1	1
1	0	1	0	0	0	1	1	1	1	1	1
1	1	0	0	0	1	1	1	1	1	1	1
1	1	1	0	1	1	1	1	1	1	1	1

It’s obvious that the algorithm should return |000> for 1 and 9 numbers of the oracle. But what will it return for other functions? Let’s see…

Here’s the definition of the function that implements the Deutsch-Jozsa algorithm itself. It’s simple:

jozsa :: Matrix (Complex Double) -> Int -> IO String
jozsa f n = initial |> gateHn n
 |> f
 |> gateHn n
 >>> (measure . fromVector n)
 where
 initial = toVector $
 foldl1 entangle $
 replicate n qubitZero

As per description: prepare the initial state with the help of folding the list of n qubits to a |0> state and one (service) qubit to a |1> state. Then apply the Hadamard gate, then the oracle, and the Hadamard gate again. After that, carry out the measurement. As you can see, the function definition is general. It accepts an oracle for function f: {0, 1}n → {0, 1} at the input, but we should also specify the value of n.

We will build histograms for the experiment. There will be nine variants of functions. That's why we will write a special function for these purposes. Here it is:

histogram :: (Monad m, Ord a)
 => m a -> Int -> m [(Int, a)]
histogram qs n = do l 

The quantum algorithm is executed (n) times utilizing the replicateM function. The algorithm is passed in the form of qs argument. Its execution results are stored in the list l. Then, the list of results of the quantum circuit is sorted and grouped (and we get a list of lists). After that, we apply (length &&& head) function to each list in the list. The function transforms to a (list’s length, list’s head) pair. We keep the heads, as all elements of these lists are the same after grouping. As a result, we get a list of pairs, and that’s the required histogram.

Let’s move on and implement the function main:

main :: Int -> IO [[(Int, String)]]
main n = mapM (\i -> histogram
 (jozsa
 (makeOracle
 (oracle i) 3) 3) n)
 [1..9]

That’s where we are going to apply the method that has been used in the definition of oracle function. With the help of a map, we will apply the process of building an oracle, its running in the Deutsch-Jozsa algorithm, and building a histogram to each element of [1..9] list. As a result of running this function (suppose we run the algorithm a million times for each oracle), we will get the following table:

The results are really significant. They prove that the result should be |000> for constant functions. But why do we get |100> result, and not, say, |001>, for the function number 5? One in the first qubit shows that the function is balanced with the regard to the first qubit exactly. If we used

oracle 5 [_, _, z] = z 

definition, 100% measurements would give |001> result. But if the function would not be balanced with regard to some variable, its result would be probabilistic.

Now, take a look at the functions number 2 and number 8. They are almost constant. That’s exactly why we will get |000> result at the output with 55% of probability. We can say the same about the functions number 4 and number 6. They are almost balanced. With more than 55% of probability, we will get |100> value.

As for the functions number 3 and number 5, they are equally far from constant and balanced ones. Therefore, their results are distributed between the four possible values with equal probability. These values hint us on which input arguments the function takes accepts the value 1.

Summary

In case you’re interested, I’d suggest you keep experimenting with the developed algorithm, just to make sure you really understand the way it operates. As for me, I will be preparing a new article to review the next algorithm.

Source code:

{-# OPTIONS_HADDOCK prune, ignore-exports #-}
{------------------------------------------------------------------------------}
{- | The module with a description of functions to implement the Deutsch-Jozsa algorithm. 
   Developer:  R. Dushkin  
   Project:    Quantum Computations and Functional Programming 
                                                                              -}
{------------------------------------------------------------------------------}
module Jozsa
(
  jozsa,
  main
)
where
{-[ THE IMPORT SECTION ]-----------------------------------------------------------}
import Control.Arrow ((&&&))
import Control.Monad (replicateM)
import Data.Complex (Complex(..))
import Data.List (group, sort)
import Circuit
import Gate
import Qubit
{-[ FUNCTIONS ]------------------------------------------------------------------}
The service function for building an oracle from a function of \[Bool] -> Bool\ type.
makeOracle :: ([Bool] -> Bool) -> Int -> Matrix (Complex Double)
makeOracle f n = matrixToComplex $ zipWith makeLine domain [1..2^n]
  where
    zeroes = replicate (2^n) 0
    domain = replicateM n [False, True]
    makeLine :: [Bool] -> Int -> [Int]
    makeLine x i = changeElement zeroes i ((-1)^(if f x then 1 else 0))
-- | The service function for changing the element if the defined list, at the specified position 
--   (the count starts with 1) to the defined value. 
changeElement :: [a] -> Int -> a -> [a]
changeElement xs i x = take (i - 1) xs ++
                       [x] ++
                       drop i xs
-- | The basic module function that demonstrates the Deutsch-Jozsa algorithm. 
jozsa :: Matrix (Complex Double) -> Int -> IO String
jozsa f n = initial |> gateHn n
                    |> f
                    |> gateHn n
                    >>> (measure . fromVector n)
  where
    initial = toVector $ foldl1 entangle $ replicate n qubitZero
-- | The function for building a histogram with the results of the defined quantum circuit.  
--   Triggers the quantum circuit a required number of times, gathers results, and 
--   builds an associative list of pairs (frequency, result).
histogram :: (Monad m, Ord a) => m a -> Int -> m [(Int, a)]
histogram qs n = do l  IO [[(Int, String)]]
main n = mapM (\i -> histogram (jozsa (makeOracle (oracle i) 3) 3) n) [1..9]
-- | The oracle simulator. The first argument is used as the index of the oracle that is to be returned for the research. 
oracle :: Int -> [Bool] -> Bool
oracle 1 [_, _, _] = False
oracle 2 [x, y, z] = x && y && z
oracle 3 [x, y, _] = x && y
oracle 4 [x, y, z] = x && (z || y && not z)
oracle 5 [x, _, _] = x
oracle 6 [x, y, z] = y && z || x && (not y || y && not z)
oracle 7 [x, y, z] = y || oracle 6 [x, y, z]
oracle 8 [x, y, z] = x || y || z
oracle 9 [_, _, _] = True
{-------------------------------------------------------------------------------
The Output:
8/0: [[(1000000, "000")],
7/1:  [(561592,  "000"), (62964,   "001"), (62666,  "010"), (62108, "011"), (63144,  "100"), (62304, "101"), (62799,  "110"), (62423, "111")],
6/2:  [(249916,  "000"),                   (249794, "010"),                 (250264, "100"),                 (250026, "110")],
5/3:  [(62405,   "000"), (62373,   "001"), (62694,  "010"), (62098, "011"), (562886, "100"), (62517, "101"), (62505,  "110"), (62522, "111")],
4/4:                    [(1000000, "001")],
3/5:  [(62504,   "000"), (62706,   "001"), (62515,  "010"), (62525, "011"), (562153, "100"), (62357, "101"), (62386,  "110"), (62854, "111")],
2/6:  [(250329,  "000"),                   (249748, "010"),                 (250030, "100"),                 (249893, "110")],
1/7:  [(562946,  "000"), (62096,   "001"), (62240,  "010"), (62560, "011"), (62595,  "100"), (62763, "101"), (62628,  "110"), (62172, "111")],
0/8:  [(1000000, "000")]]
-------------------------------------------------------------------------------}
{-[ THE END OF THE MODULE ]-------------------------------------------------------------}