The Probabilistic Deutsch-Jozsa Quantum Algorithm
Making use of the probabilistic nature of a qubit
In a series of previous posts (“An Illustrative Case Of Quantum Advantage” and “Improving The Deutsch And Jozsa Quantum Algorithm”), we looked at one of the first quantum algorithms proving to be exponentially faster than its classical counterpart. David Deutsch’s developed this algorithm and generalized it later together with Richard Jozsa.
These algorithms are all about determining whether an input function is constant or balanced. The first analogy coming to mind is a coin.
The coin could be tricked, thus always landing on one side. Or, it could be fair, landing on either side equally likely.
Deutsch’s first algorithm covered only two tosses of the coin. The latter generalization considers an arbitrary number of tosses. But here comes the big but: it assumes the balanced function to be balanced within a specific boundary. If, for instance, the boundary is two (as in Deutsch’s first algorithm), then the algorithm assumes one toss to result in heads-up and the other result in tails-up.
This assumption is unrealistic. Therefore, Deutsch and Jozsa generalized the algorithm to work with any number of tosses.
So, what if we say the boundary is four? Does a fair coin land on each side exactly twice? Maybe it does. Maybe it doesn’t. What if you see four times the same side? Can you say for sure that this coin is tricked?
How about eight tosses? How about a hundred tosses? Could a fair coin land on the same side a hundred times in a row?
No matter what number you say, you can’t say the coin is tricked with certainty. If a tricked coin always produces the same result and a fair coin lands on either side with the same probability, you can never be sure the coin is tricked. When you see both sides at least once, you know it is fair. But when you repeatedly see the same side, it only reinforces your belief in a tricked coin. But there is no certainty about it.
The question is subjective. It depends on you to decide when to stop tossing.
So, why don’t we create a quantum circuit that produces an objective assessment of whether a coin is fair or tricked?
Similar to Deutsch and Jozsa’s algorithm, our algorithm consists of four parts: qubits in superposition, an oracle, the separation algorithm, and a measurement.
We start with the first and simple, the qubits in superposition. We use one qubit per coin toss. Let’s say we have three tosses, therefore three qubits representing these tosses.
We put them into superposition by applying Hadamard gates. For Qiskit initializes qubits in state |0⟩, the Hadamard gates put them in state |+⟩. In this state, the qubit has equal probabilities of being measured as 0 or 1.
In our circuit, we use an auxiliary qubit. We put it into state |−⟩. We achieve this by applying an X-gate and a Hadamard gate. In this state, the qubit has equal probabilities of being measured as 0 or 1, too. But this state differs from |+⟩ by its phase. While the phase does not affect the value we measure a qubit as it does matter when we apply gates on the qubit. For instance, the Hadamard gate turns a qubit in state |+⟩ back into state |0⟩ and a qubit in state |−⟩ into state |1⟩.
from qiskit import QuantumCircuit, QuantumRegister, ClassicalRegister, Aer, execute
from qiskit.visualization import plot_histogram
TOSSES = 3
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)
With that in mind, we look at the oracle. The quantum oracle is not a mysterious person providing prophetic predictions. It is a placeholder for a transformation gate.
Similar to the previous post, we do not use a holistic oracle for a fair coin and another for a tricked one. While this would even make the rest of the work pretty straightforward, we would need to know whether the coin is fair or tricked when we select the right oracle, already. But this is what we do not know yet. Classifying the coin is the purpose of our quantum circuit in the first place. We don’t want the algorithm to rely on an oracle that we could only create if we knew the solution already.
Thus, we treat each toss of the coin separately. We know from Deutsch and Jozsa’s algorithm how to use a controlled-NOT gate to flip a qubit from |+⟩ to |−⟩. While the controlled-NOT gate applies an X-gate on the target qubit for the control qubit is in state |1⟩, it also applies the phase of the target qubit on the control qubit. We know this phenomenon as phase kickback.
So, for each toss that is heads-up, we apply a controlled-NOT gate with the auxiliary qubit as the target. Since this is in state |−⟩, it does not change its state. The X-gate reflects a qubit state by the X-axis. But since |−⟩ resides on this axis, the X-gate has no effect on the target qubit.
But the controlled-NOT gate affects the control qubit representing the toss. It changes its phase, and therefore, it turns it into state |−⟩.
For each toss that is tails-up, we apply a Hadamard gate.
We create a helper function to create the oracle for us.
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)
else:
oc.h(qr[pos]
# We return the oracle as a gate
oracle = oc.to_gate()
oracle.name = "oracle"
return oracle
For instance, the following circuit depicts the initialization and the oracle for heads-tails-heads.
And the next figure represents the circuit thus far representing three heads in a row.
Contrary to the original algorithm, we do not use another series of Hadamard gates to bring back the qubits into the basis states. Instead, we bring the auxiliary qubit back into state |0⟩ and we apply a triple-controlled-NOT gate with the toss-qubits as the controls and the auxiliary qubit as the target.
If all qubits represent heads-up (they are in state |−⟩) we flip the auxiliary qubit to |1⟩ when all the other qubits are in state |1⟩, too. When we run the circuit, we see the probability of this state is 1/2³=1/8=0.125. And, this is the exact probability of the coin being fair, given the evidence of three heads in a row.
Inaccuracies are due to the empirical nature of the simulation we use.
When one toss shows tails, the triple-controlled-NOT gate does not apply because the qubit we applied the Hadamard gate on is in state |0⟩. Then, the auxiliary qubit stays in state |0⟩ representing a fair coin. Consequently, we always measure the auxiliary qubit as 0.
Challenge: we want state |1⟩ of the auxiliary qubit to represent the probability of the coin being fair. How do we need to change the circuit?
Yet, our circuit is not complete. If all three qubits represent tails-up tosses, we currently measure the auxiliary qubit as 0, too. That would imply a fair coin. But it is more likely a tricked coin.
So, we add another part to our circuit. At the end of this part, we also want to apply a triple-controlled-NOT gate with the three toss-qubits as the controls and the auxiliary qubit as the target.
Therefore, we need to put qubits that are in state |0⟩ (representing tails-up) into state |+⟩ because we measure a qubit in state |+⟩ as 1 in 1/2 of the cases. If all three qubits are in this state, the triple-controlled-NOT gate applies to 1/2³ of the cases.
At the same time, we need to put qubits that are in state |−⟩ (representing heads-up) into state |0⟩, so that the triple-controlled-NOT gate does not apply at all if a single qubit is in that state.
We achieve these transformations by applying a Z-gate and a Hadamard-gate to each qubit.
The Z-gate turns the heads-up qubits from |−⟩ back into |+⟩ but it has no effect on the tails-up qubits in state |0⟩. The following Hadamard gates turn the heads-up qubit from |+⟩ into |0⟩ and the tails-up qubits from |0⟩ into |+⟩. As a result, we turned qubits representing tails-up tosses into |+⟩ and heads-up tosses into |0⟩. When all three qubits represent the tails-up state, the triple-controlled-NOT gate puts the auxiliary qubit into state |1⟩ in 1/2³ of the cases. That is the probability of a fair coin given the evidence of three tails in a row.
Let’s run the circuit with an oracle representing three tails in a row and see the results.
Again, we see a probability of a fair coin of around 0.1250.125.
But once there is a single heads-up toss in the circuit, the triple-controlled-NOT gate does not apply for one control is in state |0⟩.
When there are heads-up and tails-up tosses, we know that we have a fair coin.
Deutsch and Josza’s algorithm teaches us how we can use phase kickback to flip to turn a qubit from |+⟩ to |−⟩.
Then, they savvily create a circuit that uses this small difference to determine whether a function is balanced (fair coin) or constant (tricked coin).
However, they assume the balanced function to be balanced within a specific boundary. But this is an unnecessary simplification. Qubits are probabilistic by nature. As we saw, we can use them to represent the probability of a fair coin given the evidence.
When we think classically, we want our programs to be deterministic. We provide some clear input and expect an unambiguous output. Yet, the world we live in is not deterministic. Neither are our quantum circuits.
So, quantum circuits are a natural fit to the everyday problems we cope with. But we are too used to put our problems into a deterministic frame that we miss out on opportunities this new exciting technology offers.
Finally, there is still room for improvement. When our circuit includes heads-up and tails-up tosses, we are sure the coin is fair. Then, we always measure the auxiliary qubit as a 0.
But when our circuit includes either one tosses only, measuring the qubit as a 1 indicates the coin is fair. Of course, we want the same measurement value to represent the fairness of the coin.
Can you edit the circuit correspondingly?