Deutsch-Jozsa, or How to Evaluate a Balanced Function
The Hello World! of quantum advantage
Introduction
Each technology or programming language has its version of a “Hello World!” program. With this “simple” program, you can start coding or using the technology. For example, in Python, the language we use in this book, the Hello World concept is to print a string like this: print(‘Hello World!’). This chapter uses the “Hello World!” approach to implement Deutsch-Jozsa’s (DJ) algorithm within a quantum computing language. The DJ algorithm is a mapping algorithm where we will know if a function is balanced (half 0s half 1s) or constant in one algorithm query. Our “Hello World!” is a little more complicated than just printing a string. Still, the DJ algorithm is an excellent start to understanding how quantum algorithms can be better than classical equivalents.
The ‘black-box’ of the Boolean function
Imagine you want to study a specific function’s behaviour. A function which can be constant or balanced. Constant means that the function only outputs the values of 0 or 1. Balanced refers to a behaviour where the output will be half 0 and a half 1.
Mathematically, you can formulate the problem as:
Sounds weird, doesn’t it? You will pass n bits with a value of 0 or 1 to the function to see if an output of 0 or 1 is obtained. The process of passing n bits to the function is called a query. The goal is to give information to understand the behaviour of the output, like a bandit slot machine where you put in money and hope to win. The device’s output is usually 0 (no cash) if you don’t execute enough queries. The probability dictates that the output will be zero for a finite number of inputs.
How many times do we query the function to obtain the result? By result, I mean a long chain of 0 and 1, but the probability of receiving 0 and 1 leads to the conclusion of “constant” or “balanced” behaviour. Start with the classical approach and the best case. You need only two queries. Why?
- In the first call, you pass the value 0 to the function and receive the value 0; it’s written like this: f(0) = 0
- In the second call, you pass the value 1 to the function and receive the value 1; the corresponding mathematical equation is f(1) = 1
Remember that the number of inputs is finite, so we will not query the function to infinity. Also, the results are statistical, meaning that you have an output probability of obtaining 0 or 1. Getting 1 once doesn’t mean that the function has an equal distribution.
The function is balanced; it’s the best case (f(1) = 0 and f(0) = 1). In the worst case? You will need to test half of the possibilities plus one. Remember, balanced means half of the function has the values 0s and the other 1s. So, you will need to test half of the input plus one. 2^n represents all the possibilities, so half of them are written 2^(n-1)and you need one more test so: 2^(n-1)+1tests.
Imagine you have a 4-bit string in input; this corresponds to 2⁴ possibilities (16). You will test 8 combinations plus one, so 9evaluations. In the same way, we can compute the probability that the function is balanced.
with 1 < x < 2^(n-1).
The probability is a way to have a good idea of the behaviour; the more queries you do, the higher the probability that the function is constant.
The worst or best case has the same value with a quantum algorithm, like the Deutsch-Jozsa algorithm. You always need a unique query to find if the function is balanced or constant.
How is this possible? In a previous post, I mentioned that a quantum computer accesses some form of parallelism when using qubits. The quantum layer estimates all the possibilities at once. Deutsch Jozsa’s algorithm uses this property with a specific component called an oracle. An oracle is a black-box operation. The oracle will evaluate all possible input variations in one query to output an aggregate result.
Do you remember the Big O notation explained concisely in the Classical vs quantum post? Here, you have an exponential gain (quantum advantage). The classical approach needs 2^(n-1)+1calls against 1 for the quantum algorithm. The difference in time complexity is 2^nand it’s called exponential optimization.
Did you say Oracle?
Yes, like the sibyls of Rome, oracles were women who spoke in the name of Gods. They were considered to have been empowered by the Gods to provide their advice to mortal people.
Bra-Ket notation
In quantum mechanics, the matrices transformation and vectors manipulation is done with the bra-ket notation (or Dirac notation) to represent quantum states.
A bra is a row in a matrix, and the symbol represents <psi|.
Example:<psi| = [2+3i , 5-4i , 2i]
A ket is a column in the matrix represented by |psi>.
Example:
You can transform a bra into a ket and vice versa with the conjugate transpose.
In the case of quantum algorithms, oracles are black-box operations. They provide not the voice of gods but an algorithm (like a classical function) as an input to another algorithm. Oracles are like masks with different properties that will help you simulate the physical effect you want to solve. An oracle will act on qubits to output a transformation. Most of the time, the formulation is written like this: O|x> = |f(x)> where O is the oracle and x a state vector of the qubits x = {x_0, x_1, ..., x_n} with n the number of inputs).
An oracle’s main advantage is allowing the user to focus on the quantum techniques to analyze the function rather than the function itself. But there is a significant drawback to the black-box. The output size can be different from the input size, which would break the reversibility rule. It’s essential to ensure that your oracle can be reversible.
What is an oracle in the context of Deutsch-Jozsa’s algorithm? In the constant case, the input is equal to the output. The transformation corresponds to a multiplication of the identity matrix and the input: input x I = output = input
On the other hand, in the balanced case, the oracle’s output will be half 0s and half 1s.
Implementations of the Deutsch-Jozsa’s algorithm
The code snippets will be provided for Qiskit. Qiskit isn’t the only open-source quantum library, but it’s one of the most used, and its community is huge.
For an introduction to Qiskit and how to install the different modules, please look at my post on Qiskit.
Corresponding classical pseudocode
You probably have an idea of how to do the function’s evaluation in a classical code to determine if the function is constant or balanced. You can use simple if...else statements to assess the behaviour. The following simple pseudocode tested the function of the oracle and compared it with the output and so iteratively.
if f(0) = 0:
if f(1) == ):
print(“The function is constant”)
else:
print(“The function is balanced”)
else:
if f(1) == 0:
print(“The function is balanced”)
else:
print(“The function is constant”)Quantum circuit for Deutsch-Jozsa
It’s time to go deeper! We will jump into the rabbit hole! What does the quantum circuit of Deutsch-Jozsa look like? Look at this picture:
Lot of things to look at it, right? So, let’s go.
When you start a quantum circuit, you initialize the circuit at the state 0. This is the |psi_0> step. Each qubit will have the state 0 or the column vector (1, 0). This quantum circuit is a generalized model because you can create a quantum circuit with n qubits. You also need one qubit with the initialization at state 1; the X quantum gate does this. The X-gate performs a bit flip operation; it inverts the state, passing from 0 to 1.
Hadamard Gate
It’s a single-qubit operation mapping the state |0> and |1> of the qubits into a superposition state. Hadamard has the letter H to represent the gate, and the corresponding mathematical representation is:
When applied on |0> and |1> we have the corresponding states:
Every qubit is put in a superposition 0 and 1 states. These states are then passed to the oracle.
We query the oracle with a superposition state!
Code for Deutsch-Jozsa’s algorithm
It’s time to see how to code it. First, we need to import some packages to create the corresponding objects.
import numpy as np
from qiskit import QuantumCircuit, transpile, assemble, Aer, IBMQ, execute
from qiskit.quantum_info import Statevector
from qiskit.visualization import plot_bloch_multivector, plot_histogramHere we have all the packages we need to create the oracle and implement the Deutsch-Jozsa algorithm. We will use oriented-object programming to generate the quantum algorithm.
The class will contain three methods. The first is the init() , the second is the oracle() and the last is the algorithm dj().
The __init__() function will create an instance of the class. The parameters are the case (balanced or constant) to be passed to the oracle and the string of states that you will test an input (as ‘1001’, ‘0010’ for four qubits input). The init() function will generate the correct number of qubits required for the algorithm.
The oracle() function will create a proper QuantumCircuit(). The objective is to create a custom gate to insert it into the final algorithm. The oracle will consider two cases. Constant: the function will transform the state to return the state 0s state as output. In the balanced case, the function will flip all the 1s in input to 0s. Then apply CNOT gates and flip the 1s again. You have your oracle for Deutsch-Jozsa.
Now, the dj() function, is where we create the |psi_x> where x = 0, 1, 2. At first, we make the output qubit (n+1 qubit), applying X-gate and then Hadamard-gate. The rest is to initialize all the rest of the qubits with Hadamard-gate, add the oracle on all qubits, then use Hadamard-gate again and create the measurement of all qubits without the output one.
Let’s get it run!
dj_object = DeutschJozsa('constant', '0110') # Call the class and generate the instance with the constant case and the input state string ‘0110’dj_circuit = dj_object.dj() # Create the quantum algorithm by calling the dj()dj_circuit.draw('mpl') # Make the visualization of the circuit
The result is this circuit:
Now we need to run it both in a simulator and on a real device (oh yeah!).
Running a quantum algorithm.
First, we will try the quantum algorithm with a perfect simulator. This will be our baseline. We will use all of the functions described in the part of the main components of Qiskit. Let’s do it:
qasm_sim = Aer.get_backend('qasm_simulator') # Create a backend simulatortranspiled_dj_circuit = transpile(dj_circuit, qasm_sim) # Transpile the code into fundamental gates, this will break the oracle into its componentsqobj = assemble(transpiled_dj_circuit) # Then assemble each gate into a new quantum circuitresults = qasm_sim.run(qobj).result() # Time to run it on the backend and get the results, the simulator is perfect, so it requires only one shotanswer = results.get_counts()# Extract the output stateplot_histogram(answer) # Plot it to visualize the corresponding histogram
All right, the result is a corresponding 100% probability that the function is constant. But it was easy and perfect because the qasm_simulator reproduces the behaviour of an ideal quantum computer without any decoherence. You made it, created a quantum algorithm for the Deutsch-Jozsa’s problem, and tried it with a simulator.
Now, let’s run the quantum algorithm on a real device. To do it, you will need an account on the IBM quantum experience (it’s free, and you have access to quantum computer for free). When your account is created, you need to generate a token; it is your credential to use the IBM Quantum Cloud. On the main page, you have an ‘API token’; create one and copy the token. You will link your machine and the Qiskit library like this:
from qiskit import IBMQ # Call IBMQ – API for the quantum cloudTOKEN = 'paste your token here' # Save your token hereIBMQ.save_account(TOKEN) # Connect your machine with the cloudIBMQ.load_account() # Load account from diskIBMQ.providers() # Print the group you belong to
The code will print this:
[<AccountProvider for IBMQ(hub='ibm-q', group='open', project='main')>]This means that you have a free account and access to the group ‘open’ for open-source and project ‘main’ because you are not part of a category for IBM. Let’s see what device we could use. To know that, we need to call the available backends:
provider = IBMQ.get_provider(hub='ibm-q')
provider.backends()And the code (or API call) will generate this list:
[<IBMQSimulator('ibmq_qasm_simulator') from IBMQ(hub='ibm-q', group='open', project='main')>,
<IBMQBackend('ibmq_armonk') from IBMQ(hub='ibm-q', group='open', project='main')>,
<IBMQBackend('ibmq_santiago') from IBMQ(hub='ibm-q', group='open', project='main')>,
<IBMQBackend('ibmq_bogota') from IBMQ(hub='ibm-q', group='open', project='main')>,
<IBMQBackend('ibmq_lima') from IBMQ(hub='ibm-q', group='open', project='main')>,
<IBMQBackend('ibmq_belem') from IBMQ(hub='ibm-q', group='open', project='main')>,
<IBMQBackend('ibmq_quito') from IBMQ(hub='ibm-q', group='open', project='main')>,
<IBMQSimulator('simulator_statevector') from IBMQ(hub='ibm-q', group='open', project='main')>,
<IBMQSimulator('simulator_mps') from IBMQ(hub='ibm-q', group='open', project='main')>,
<IBMQSimulator('simulator_extended_stabilizer') from IBMQ(hub='ibm-q', group='open', project='main')>,
<IBMQSimulator('simulator_stabilizer') from IBMQ(hub='ibm-q', group='open', project='main')>,
<IBMQBackend('ibmq_manila') from IBMQ(hub='ibm-q', group='open', project='main')>]Here we are; we can see many devices, backend (real device) and simulators. IBM has devices with more than one hundred qubits, but in open access, we have only access to 5 qubits devices. We put a string of four values (4 qubits for the string — x, and one for the output — y, 4+1=5).
Let’s try ibmq_manila:
backend = provider.get_backend('ibmq_manila')Now our backend to do the calculation is the real device. Let’s rerun some previous lines:
mapped_circuit = transpile(dj_circuit, backend=backend)# Transpile the circuit with the backend architectureqobj = assemble(mapped_circuit, backend=backend, shots=1024)# Assemble into a new quantum circuit with Manila in the backend and a number of shots of 1024job = backend.run(qobj) # Run it
This step can be very long, depending on the use of the device. The first time it took me 30 minutes to get the results back. You can get the results and print them when your job is validated, in queued and run.
result = job.result()# Get the result objectcounts = result.get_counts() # Extract the dictionary containing the states with their corresponding number of appearances when measuredprint(counts)>>> {'0000': 974, '0001': 8, '0010': 8, '0100': 25, '1000': 8, '1001': 1}
Well, as you see, the result isn’t perfect due to the noise of the real device. We can visualize the corresponding histogram:
plot_histogram(counts)
Look, take a breath; you did it!! You built a quantum algorithm and tested it on a simulator and a real device. Congratulation! You know now how to code and use Deutsch-Jozsa’algorithm with Qiskit and IBM quantum.
Take away
- Deutsch-Jozsa is a quantum algorithm used to determine the behaviour of a function, constant or balanced. The algorithm has an oracle that we need to query to obtain an answer once.
- DJ is the quantum algorithm which reaches a quantum advantage. The time complexity is exponentially faster than the classical approach.
- The quantum algorithm is equipped with an oracle, a black-box operation. This black-box is a function where we don’t know the properties and need to query the function to obtain them.
- An oracle is necessary a unitary matrix because it needs to be reversible to follow unitary operators’ rules and doesn’t lose information from input to output.
- Qiskit possesses six modules. Two contain fundamental functions to create and use a quantum algorithm (Aer and Terra). Four are domain specifics and have algorithms for real-world applications (Optimization, Machine Learning, Finance and Nature).
- We create a class containing the components of the Deutsch-Jozsa quantum algorithm. Easily usable with only the case scenario and the bit string as input. The code is agnostic of the bit string length, but you must be careful of the number of qubits needed to run the quantum algorithm.
- A quantum algorithm can be run locally with simulators. The results are usually perfect because a simulator is a quantum computer without noise. This noise provides a different circuit output due to destructive decoherence.
- The quantum algorithm needs to be run multiple times to generate a probability distribution of the output. The output with the highest probability is the one we keep as a “result.”
- We used a lot of concepts different from the classical world, be sure to fully understand the different steps and how they affect the quantum circuit to understand the quantum computation of the algorithm.
