Demonstrating exponential speedup with the Deutsch-Jozsa algorithm
Whenever a new technology is being hyped, people get curious about what it has to offer. With the attention that Quantum Computing is getting, you may wonder whether it actually has benefits over the computers we have today. In this post, I will introduce the Deutsch-Jozsa algorithm [1], the first proposed quantum algorithm proven to be faster than the best classical solution.
Imagine you have a “black box”, and it acts as a function f:{0,1}ⁿ→{0,1}, that is, it takes n bits as input and outputs 1 bit, but you don’t know how this function is implemented or how it behaves. The only thing you know is that the function can only have one of the two behaviors: the function is either constant, meaning it always outputs 0 or always outputs 1, or it is balanced, so it outputs 0 for exactly half the inputs, and outputs 1 for the other half inputs. To give an example, say we have n=2, so the possible inputs are 00, 01, 10, 11. If the function is constant, we have:
- f(00)=f(01)=f(10)=f(11)=0 or
- f(00)=f(01)=f(10)=f(11)=1
If the function is balanced, we have many possibilities, and you can see some examples below.
- f(00)=f(01)=0 and f(10)=f(11)=1 or
- f(00)=f(11)=0 and f(01)=f(10)=1
The goal of the Deutsch-Jozsa algorithm is to find if the function is constant or balanced using the least possible calls to the function. To see how the quantum algorithm is superior, we must look at the classical solution first.
Classical solution:
The best case for the classical solution requires two calls to the function. In this case, the first call returns 0 and the second returns 1, or vice-versa. This is true because if there are two different outputs, then the function must be balanced.
However, in the worst case, we need ((2ⁿ÷2) +1) calls to the function. This is because it is possible that the first half calls will return the same value, so if the next call returns the same as the previous ones, then f is constant, and if the output is different, then f is balanced.
Quantum solution:
Using a quantum computer for this problem, we can solve it using a single call. So it is clear that, even for n=1, the quantum solution is faster, and the advantage gets even bigger when we increase the size of the input. So, how is this possible?
The first step is to implement the function f as a quantum oracle, that is like a black box, and this oracle will map the input |x⟩|y⟩ to |x⟩|y ⊕ f(x)⟩. The ⊕ sign means an addition mod 2, also known as XOR. We will call this oracle Uf.
The full circuit for the algorithm is the following:
Just in case you are confused, this “⊗n” you see means the action is happening in n qubits. This means there are n qubits initialized as |0⟩, and then n Hadamard gates are applied to them.
To explain what is happening, it will be interesting to look at the state of the system during each step.
- Step 0 :
- Step 1(After the Hadamards):
Here, it is nice to see the effect of the Hadamards on both registers alone, and then the effect on the whole system.
- Step 2 (After Uf):
Notice that in the current state, y = (|0⟩ -|1⟩). When U_f is applied, the result is the following.
To simplify this state, notice these properties about the XOR:
With this, we can write that:
Making it possible to rewrite this term as
Resulting in the state
- Step 3 (After the last Hadamards):
Here, we can ignore the second register (the ancilla qubit), since it won’t be measured. This leaves us with the following state.
To understand this next step, know that we can write the effect of Hadamard gates on some state|x⟩ as
with x.y being the bitwise product, so x.y=x₀y₀ ⊕ x₁y₁ ⊕ … ⊕xₙyₙ. With that said, when the Hadamards are applied to|ψ2⟩, we get our final state.
Notice that, if you want to be rigorous, then the intermediate steps of this last operation are wrong, since the sum is a part of the definition of the state |x⟩, and the Hadamard is actually being applied to it as well. But since this won’t affect the results, and I believe it makes it easier to understand what was done, I decided to leave it like that.
- Measurement:
Now it is time to measure, and this is where the magic happens. Notice that, if we want to measure the state |00…0⟩, that is, |y⟩ = |00…0⟩, then the probability of this measurement is given by
So, as you can see, if we measure the result once and it is equal to |00…0⟩, then we know for sure that the function is constant, and if we get any other result, then the function is balanced. So, as previously said, instead of ((2ⁿ÷2) +1), we used a single call to the function, meaning this algorithm is exponentially faster than the classical one.
Now that you know the theory behind the algorithm, we can use a platform like qiskit to implement it and try it out on a real quantum computer. I should say that most of the code below is based on the qiskit documentation [2], so if you want further information, go check it out.
Qiskit Implementation:
Setting up the environment:
import numpy as np
from qiskit import QuantumCircuit
from qiskit.visualization import plot_histogram
n=3 #size of the inputfrom qiskit import IBMQ
IBMQ.save_account("*token*")
IBMQ.load_account()
provider = IBMQ.get_provider("ibm-q")
Creating the Oracle:
We can create a constant oracle or a balanced one. I’ll create both just so you know what they look like.
- Constant Oracle:
const_oracle = QuantumCircuit(n+1)output = np.random.randint(2) #Randomly decides if f(x)=0 or f(x)=1
if output == 1:
const_oracle.x(n)
const_oracle.draw()
- Balanced Oracle:
The balanced oracle is implemented through some CNOT gates. Also, we add some NOT gates in order to change the control qubits so the CNOT has some effect. However, the NOT is applied twice, so the control qubit goes to the original state after Uf.
balanced_oracle = QuantumCircuit(n+1)
b_str = "101" # This string simply determines the balance# Place X-gates
for qubit in range(len(b_str)):
if b_str[qubit] == '1':
balanced_oracle.x(qubit)# Use barrier as divider
balanced_oracle.barrier()# Controlled-NOT gates
for qubit in range(n):
balanced_oracle.cx(qubit, n)balanced_oracle.barrier()# Place X-gates to return qubits to original state
for qubit in range(len(b_str)):
if b_str[qubit] == '1':
balanced_oracle.x(qubit)# Show oracle
balanced_oracle.draw()
The rest of the algorithm:
dj_circuit = QuantumCircuit(n+1, n) # Apply H-gates
for qubit in range(n):
dj_circuit.h(qubit)# Put ancilla qubit in state |->
dj_circuit.x(n)
dj_circuit.h(n)# Add oracle
dj_circuit += balanced_oracle #You can change for constant oracle# Repeat H-gates
for qubit in range(n):
dj_circuit.h(qubit)
dj_circuit.barrier()# Measure
for i in range(n):
dj_circuit.measure(i, i)# Display circuit
dj_circuit.draw()
Notes: The circuit is created using n+1 qubits, because we have an ancilla qubit, initialized as |1⟩. Also, notice you can append the oracle to this circuit using the += operation, so the NOTs you see in the full circuit are part of the Oracle, not part of the external circuit.
Results:
from qiskit import execute
backend = provider.get_backend("ibmq_quito")
job = execute(dj_circuit, backend=backend, shots=500)
result = job.result()
answer = result.get_counts()
plot_histogram(answer)
As you can see, there was still a small probability of getting the 000 result, but that is due to some noise that occurs on real quantum computers, like the one in which the algorithms were executed. This means that the intended result was not 000, meaning the function is balanced, which is right. If you want, you can switch the oracles and check if the results are still right.
Despite this being the first algorithm to top a classical one, its benefits are not really useful, since the problem it is solving is not something we need to solve frequently. So, despite this proving that quantum computers can outperform classical ones, there are other algorithms that can do the same, but also solve useful and interesting problems, such as Grover’s algorithm and Shor’s algorithm. Besides the algorithms, other areas can make use of this technology, like Machine Learning and Chemistry.
With all that said, I believe it is safe to say Quantum Computers are not only hype, but will be able to offer us real benefits in the near future.
References:
[1] David Deutsch and Richard Jozsa (1992). “Rapid solutions of problems by quantum computation”. Proceedings of the Royal Society of London A. 439: 553–558. doi:10.1098/rspa.1992.0167
