Improving The Deutsch And Jozsa Quantum Algorithm
A practical guide about a famous quantum algorithm
There’s good news! The printed version of Hands-On Quantum Machine Learning with Python is now available on Amazon! If you prefer an ebook, you can order it from LeanPub.
If you backed my Kickstarter project then there is even better news! The printed version is now on its way to you! Depending on your location, shipping will take a little time, though.
In a previous post, we got to know the algorithm developed by David Deutsch and Richard Jozsa. One of the first algorithms to prove how a quantum algorithm can be exponentially faster than a classical algorithm.
This algorithm evaluates in a single run whether the input we provide is constant or balanced. As an example, we looked at a coin. To say whether a coin is fair, you have to toss and evaluate it multiple times. On the other hand, the Deutsch-Jozsa quantum algorithm evaluates it only once.
The algorithm, however, has a few shortcomings.
First, we use entirely different oracles for fair and for tricked coins. So, we have to decide whether the coin is fair or tricked when creating the quantum circuit.
Second, we do not have a single qubit telling us whether the coin is fair or not. Instead, we have to measure three qubits.
And third, while the oracle puts the qubits into a state representing their input value, this input value is not used to decide whether the coin is fair or tricked. We could even skip putting the qubits into the correct state. The algorithm would still work as long as we select the correct oracle.
To summarize, we need to decide on oracle (the constant/tricky or the balanced/fair) before running the quantum circuit that should tell us which kind of coin we have.
So, let’s address these shortcomings.
We start with the setup. Here, we import all the required libraries from Qiskit.
from qiskit import QuantumCircuit, QuantumRegister, ClassicalRegister, Aer, execute
from qiskit.visualization import plot_histogram
TOSSES = 3
Next, we create our generalized oracle. It takes two quantum registers and the configuration (config
) as parameters. The quantum registers contain the qubits and allow us to work with them. The config
contains a string consisting of 0
s and 1
s. Each digit represents an output of the function we aim to classify--or the result of tossing the coin if you will.
If the string contains three 0
s or three 1
s, it is a constant function (or tricked coin). If the string contains at least one 0
and one 1
, it is a balanced function (or fair coin).
def oracle(qr, aux, config):
# Create a sub-circuit
oc = QuantumCircuit(qr, aux)
for pos in range(len(config)):
if config[pos] == '1':
oc.cx(qr[pos], aux)
# We return the oracle as a gate
oracle = oc.to_gate()
oracle.name = "oracle"
return oracle
Inside the oracle
function, we evaluate each position of the config
string (line 6). This is important to note because it addresses the first shortcoming we mentioned. We don't use the whole config string at any point in the preparation of the quantum circuit. Instead, we leave it up to the quantum algorithm to evaluate whether the overall string is constant or balanced.
For each position in the config
string that is 1
, we apply a controlled-NOT gate with the qubit representing the toss as the control qubit and the auxiliary as the target qubit.
The obvious question is: “Why do we do that?”
Before we can answer this question, we should look at the whole quantum circuit. But only concentrate on the initialization of the qubits (lines 8–13) before we apply the oracle.
def create_circuit(config):
# prepare the registers and the circuit
qr = QuantumRegister(TOSSES, "toss")
aux = QuantumRegister(1, "aux")
cr = ClassicalRegister(1, "cr")
qc = QuantumCircuit(qr, aux)
# set auxiliary to |->
qc.x(aux)
qc.h(aux)
# set toss-qubits to |+>
qc.h(qr)
# apply oracle
qc.append(oracle(qr, aux, config), [*qr, *aux])
# bring qubits out of superposition
qc.h(qr)
qc.h(aux)
qc.barrier()
# flip auxiliary to |0>
qc.x(aux)
# flip auxiliary to |1> if all tosses are |1>
qc.mcx(qr, aux)
qc.x(qr)
qc.mcx(qr, aux)
qc.x(qr)
return qc
The following figure depicts the initialization and the oracle for a two-qubit system (one toss only).
“So, what does such a circuit do?” First, we put the top qubit into state |+⟩ and the bottom qubit (the auxiliary) into state |−⟩. In these states, we measure each qubit as either 0
or 1
with a 50% chance. The only difference is the qubit phase.
This difference matters when we apply the controlled-NOT gate. It flips the amplitudes of the states |01⟩ and |11⟩ (the top qubit is on the right-hand side). But the amplitude absolutes of these two states are equal. So, this gate doesn’t affect the resulting measurement probabilities.
The following figure depicts the change of measurement probabilities.
We see the top qubit starts in position “off” (meaning 0% chance of being measured as 1
). So does the bottom qubit. But the 𝑋 gate flips it to "on" (100% chance of being measured as 1
). The Hadamard gates put both qubits into an equal superposition with a 50% chance of being measured as a 1
. The controlled-NOT gate doesn't change these probabilities.
Then, why do we apply this gate? As in the original Deutsch-Jozsa algorithm, the answer is phase kickback. The bottom qubit is in state |−⟩. While it has the same amplitude absolute and thus, the same measurement probability as state |+⟩, its phase is shifted. A look at the Bloch Sphere discloses this.
By the way, the Bloch Sphere vividly illustrates why the X-gate doesn’t change the states |+⟩ and |−⟩. The X-gate mirrors the qubit state vector by the X-axis. But these two states reside on that axis. Therefore, reflecting on the X-axis does not change anything.
But the controlled-NOT gate affects the phase of the control qubit. The following figure shows the states of the qubits after we applied the controlled-NOT gate.
Since the oracle applies a controlled-NOT for each 1
in the config
string, it effectively flips the phase of these qubits and puts them into state |1⟩. But the oracle does nothing when we have a 0
in the config
string, leaving those qubits in state |+⟩.
Now, let’s continue with the remainder of the circuit. The following figure depicts that part of the circuit.
First, the series of Hadamard gates brings the qubits back into a basis state. If the qubit is in state |+⟩, the Hadamard gate turns it into |0⟩. This is the case if we did not apply a controlled-NOT gate on this qubit in the oracle. It represents a 0
in the config
string. If the qubit is in state |−⟩, the Hadamard gate turns it into |1⟩. When we applied the controlled-NOT gate, this is the case, and it represents a 1
in our string.
The auxiliary qubit does not change. So, it is still in state |−⟩ and the Hadamard gate turns it into |1⟩. The following NOT-gate flips this qubit back into state |0⟩.
Next, we apply an MCX-gate. This is a multi-controlled-NOT gate. It takes an arbitrary number of control qubits and a single target qubit. It applies a NOT-gate on the target qubit only for all control qubits are in state |1⟩. This means we flip the auxiliary qubit to |1⟩ if our config
string implies a constant function that always returns 1
.
Next, we flip the three input qubits by NOT-gates followed by another MCX-gate. Now, we flip the auxiliary qubit to |1⟩ if our config
string implies a constant function that always returns 0
.
And that’s it. If neither of the MCX-gates flips our auxiliary qubit into state |1⟩, our input must have been a balanced function.
Therefore, we fix the second shortcoming of the original Deutsch-Jozsa algorithm. That is, we do not see the result in a single qubit. In our improved circuit, we only need to measure the auxiliary qubit.
Let’s have a look. The following figure shows the output of the constant 000
configuration. We also include the measures of all qubits to illustrate that the input qubits have the correct values, too.
qc = create_circuit('000')
results = execute(qc,Aer.get_backend('statevector_simulator'),shots=1000).result().get_counts()
plot_histogram(results, figsize=(3,2), color=['white'])
We see that only the auxiliary qubit results in 1
. But all input qubits are 0
and thus, constant. Next, we look at the constant 1
function.
qc = create_circuit('111')
results = execute(qc,Aer.get_backend('statevector_simulator'),shots=1000).result().get_counts()
plot_histogram(results, figsize=(3,2), color=['white'])
We see that all qubits result in 1
, including the auxiliary qubit. Next, we look at a balanced function.
qc = create_circuit('101')
results = execute(qc,Aer.get_backend('statevector_simulator'),shots=1000).result().get_counts()
plot_histogram(results, figsize=(3,2), color=['white'])
In this case, a balanced function, we measure the auxiliary qubits as 0
. The following figure shows the complete circuit.
The Deutsch-Jozsa algorithm is one of the first and well-known quantum algorithms. It vividly illustrates how we can use quantum phase kickback to create a quantum algorithm that is exponentially faster than its classical counterpart.
In this post, we addressed three shortcomings of the original algorithm. First, we use the same oracle function for all possible inputs. Second, we can use a single (the auxiliary qubit) to measure whether the input function is constant or balanced. And third, the quantum gates we use to mark the input as 0
or 1
are decisive for their output value and whether we classify the overall function as constant or balanced.
This extension of the Deutsch-Jozsa algorithm is not intended to diminish the original performance by any means. Deutsch and Jozsa developed their algorithm in 1992. They did not have textbooks to learn quantum computing. They did not have simulators, and they did not have real devices. Most importantly, they came up with phase kickback in the first place! This extension simply uses it and straightens the rest of the algorithm.
We could have simplified the whole algorithm even further. Instead of a series of Hadamard gates and controlled-NOT gates, we could have simply put the input qubits into state |1⟩ using X-gates. Then, however, we would not have used phase kickback. And this is the lesson that the algorithm teaches us.