After having a rest day yesterday, today, I’m continuing with the most advanced exercise on the algorithms track. The task is an extension to the Deutsch-Jozsa algorithm. You are given four individual functions, of which either all four are equally balanced/constant or two are balanced and two are constant. The algorithm has to decide which case is materialized, using no more than 8 qubits.
Now, I think it is easiest to evaluate the functions one by one, and sum up the result bits using the QFT-adder logic from a previous exercise and distinguish the cases depending on the resulting count.
Optimizing for gate count
If you want to minimize the gate count, you can perform each function once, writing the results of each function to individual qubits. Eventually, you can make controlled increments on a two qubit register (mod 4), where each wire serves as a control. You need 8 qubits in total
- two input qubits
- four qubits to store the function results
- two qubits for the counter
You have three possible cases:
- Four balanced functions, no increments are performed, the counter register reads |00>
- Four constant functions, four increments are performed, the counter register overflows and eventually reads |00>
- Two balanced functions and two constant functions, the counter register reads |10>
Optimizing for qubit number
If you want to minimize the number of qubits needed, I came up with a similar solution that uses only four qubits:
- two input qubits
- one control qubit
- one qubit for the counter
With the known two possible result cases, you can opt to make half increments, instead of full increments, this reduces the counter register size by one qubit.
After performing the controlled counting, you can undo the oracle operation by applying the inverse and therefore freeing up the control qubit for further use.
Here is my code, doing just that …
def deutsch_jozsa(fs):
"""Function that determines whether four given functions are all of the same type or not.
Args:
- fs (list(function)): A list of 4 quantum functions. Each of them will accept a 'wires' parameter.
The first two wires refer to the input and the third to the output of the function.
Returns:
- (str) : "4 same" or "2 and 2"
"""
dev = qml.device("default.qubit", wires=4, shots=1)
inp_wires = range(2)
def controlled_half_increment(crtl_wire, wire):
"""Quantum function capable of performing a half increment on a single qubit (i.e. mod 1)
Args:
- ctrl_wire (int): wire to control the operation
- wire (int): wire on which the function will be executed on.
"""
wires = [wire, ]
qml.QFT(wires=wires)
qml.CRZ(np.pi/2, wires=[crtl_wire, wires[0]])
qml.adjoint(qml.QFT)(wires=wires)
@qml.qnode(dev)
def circuit():
"""Implements the modified Deutsch Jozsa algorithm."""
qml.broadcast(qml.Hadamard, wires=inp_wires, pattern="single")
for f in fs:
f(range(3))
controlled_half_increment(2,3)
qml.adjoint(f)(range(3))
qml.broadcast(qml.Hadamard, wires=inp_wires, pattern="single") # this is
return qml.sample(wires=[3,]) # 1 .. 2 and 2, 0 .. 4 the same
sample = circuit()
four_same = "4 same"
two_and_two = "2 and 2"
return four_same if sample == 0 else two_and_twoTesting the algorithm
The starter code includes a scheme for generating the functions. First, I tested the code, by passing the provided test data to the algorithm – but to me it looked like the results were published wrong. I continued by passing the same function four times – checks out, and then passing combinations of two functions – and ended up observing both cases: equal situations and two and two situations. I took it for a successful test.