Quantum Algo: Deutsch Algorithm
Is quantum parallelism so important?
In this article, we will discuss about the Deutsch Algorithm problem statement and its capabilities. Deriving and implement the Deutsch Algorithm using classical, Qiskit and Cirq.
Quantum parallelism is a fundamental feature of many quantum algorithms. It allows quantum computers to evaluate a function f(x) for many different values of x simultaneously. As shown in red box
Quantum interference is a result of superposition. In quantum computers, this allows for a collapse of the multiple states into probabilities of the desired outcome.
Deutsch’s algorithm combines quantum parallelism with a property of quantum mechanics known as interference.
The setup:
There is a univariate function f, defined over the binary alphabet 0,1 with output range in the same alphabet 0, 1 i.e., f(x): {0, 1} → {0, 1}.
How to model f(x) in the quantum circuit model?
- What makes the task slightly non-trivial is that, recall by Postulate 2 of quantum mechanics, all quantum operations must be unitary and hence reversible.
- In general, however, given the output f(x) of a function, it is not always possible to invert f to obtain the input x. In other words, we have to compute f(x) in such a way as to guarantee that the computation can be undone.
This is achieved via the following setup:
Now 𝑈𝑓 is reversible, this is because running 𝑈𝑓 again on its output, |x⟩|y ⊕ f(x)⟩, yields state |x⟩|y ⊕f(x)⊕f(x)⟩ = |x⟩|y⟩, since f(x)⊕f(x) = 0 (adding the same bit twice and dividing by 2 leaves remainder zero). We have not specified the inner workings of 𝑈𝑓 (i.e. we have not given a circuit implementing the functionality stated above). we shall treat 𝑈𝑓 as a “black box” or “oracle” which we presume we can run, but cannot “look inside” to see its implementation details.
The Problem:
With a bit of inspection, and making no assumptions about f(x), there are four possible configurations for the function f(x):
- Both inputs 0, 1 are mapped to the output 0: f(0) = f(1) = 0.
- Both inputs 0, 1 are mapped to the output 1: f(0) = f(1) = 1.
- Inputs pass through f(x) unchanged: f(0) = 0 and f(1) = 1.
- Inputs are exchanged after passing through f(x): f(0) = 1 and f(1) = 0.
We will call the first two cases as f(x) being constant (i.e., whatever input we insert, the function behaves the same way) and the last two cases as f(x) being balanced.
The question is the following:
Given a function f(x): {0, 1} → {0, 1} and without knowing anything more than that, determine whether f(x) is a constant or a balanced function with the minimum number of function evaluations.
What a classic algorithm would do?
In the classical sense, an algorithm that solves this problem would implement an if-then-else statement as shown in fig 2. As you can see, we require two function evaluations to figure out the answer. So certainly at most two queries to 𝑈𝑓 suffice to solve this problem.
Can we do it with just one query?
Classical NO. But quantumly, Deutsch showed how to indeed achieve this with a single query.
In the study of quantum query complexity, one is given a black box 𝑈𝑓 implementing some function f, and asked what the minimum number of required queries to 𝑈𝑓 is in order to determine some desired property of f.
We are interested in minimizing cost function in solving Deutsch’s problem is the number of quantum queries to 𝑈𝑓 as defined above.
The Algorithm:
first attempt a simpler, more naïve approach — since we are allowed to query 𝑈𝑓 quantumly, (as shown in Fig 1)
- what happens if we just query 𝑈𝑓 in superposition in the input register?
- In other words, what happens if we run the circuit for 𝑈𝑓 with input state |x⟩ replaced with α|0⟩ + β|1⟩ and output state |y⟩ with |0⟩?
Intuitively, here we have set the input register to both possible inputs 0 and 1, and so we expect 𝑈𝑓 to return a superposition of both possible outputs, f(0) and f(1). Indeed, by linearity of 𝑈𝑓 , the output of the circuit will be
Wait, although we have both outputs f(0) and f(1) in superposition, we cannot hope to extract both answers via measurement.
Luckily, Deutsch goal is not to extract both f(0) and f(1) after a single query. Rather, want something possibly simpler, evaluate the expression f(0) ⊕ f(1).
Where this expression f(0) ⊕ f(1) came from?
Convince yourself from this article’s XOR that f is constant if f(0) ⊕ f(1) = 0 and f is balanced if f(0) ⊕ f(1) = 1. Thus, Deutsch’s problem is equivalent to evaluating f(0) ⊕ f(1).
Deutsch’s algorithm:
well the interesting question be why |0⟩ and |1⟩?
- |0⟩ is as first qubit input it can be any value of 0, 1. for generality let’s consider first qubit be |x⟩ and x ∈ {0, 1} at |ψ1⟩
- But, |1⟩ as an second qubit is more interesting because to achieve the concept of phase kick back which is not possible with |0⟩ as second input.
with the above considerations, the wave function becomes:
Now, there are two possibilities: Either f(x) = 0, or f(x) = 1
If f(x) = 0, the equation simplifies to |ψ⟩ = |x⟩ ⊗ 1 √ 2 (|0⟩ − |1⟩) = |x⟩|−⟩ where 1 ⊕ 0 = 1
i.e. the input state is unchanged by the action of Uf
If f(x) = 1, the equation simplifies to |ψ⟩ = |x⟩ ⊗ 1 √ 2 (|1⟩ − |0⟩) = -|x⟩|−⟩ where 1 ⊕ 1 = 0
i.e. -1 phase factor is produced
We can summarize both these cases in a single equation
After applying last Hadamard gate and Suppose now that f is constant, i.e. f(0) = f(1) from fig 5 which results as
After applying last Hadamard gate and considering initial input as |0⟩ and Suppose now that f is balanced, i.e. f(0) != f(1) from fig 5 which results as
from Fig 8, if f(0) = 0 then f(1) = 1 and f(0) = 1 then f(1) = 0 which brings+ or -term and leaves -at middle always, which results to |-⟩ state as shown in Fig 8.
Conclusion: If f is constant, the algorithm outputs 0, and if f is balanced, the algorithm outputs 1. Thus, the algorithm decides whether f is constant or balanced, using just a single query!
Implementation using Qiskit and Cirq:
In the below Fig 10, we can observe all the possible ways of implementation of Oracle for both constant as well balanced conditions.
Implement using IBMQ Composer:
In the below Imp 1 the result shows |00⟩ with 100% probability, where q1 is |0⟩ and q2 is also |0⟩. From q1 as |0⟩ concludes f(x) or Oracle function is constant.
In the below Imp 2the result shows |00⟩ with 100% probability, where q1 is |0⟩ and q2 is also |0⟩. From q1 as |0⟩ concludes f(x) or Oracle function is constant.
In the below Imp 3 the result shows |01⟩ with 100% probability, where q1 is |1⟩ and q2 is also |0⟩. From q1 as |1⟩ concludes f(x) or Oracle function is balanced.
In the below Imp 4 the result shows |01⟩ with 100% probability, where q1 is |1⟩ and q2 is also |0⟩. From q1 as |1⟩ concludes f(x) or Oracle function is balanced.
Implement using IBMQ Qiskit:
In the following code blocks we walk through over implementation of Oracle mentioned in fig 10 and Deutsch Algorithm using qiskit.
As shown in the below qiskit 1, generates Oracle for the given secret fucntion
As shown in qiskit 2 below, creates Deutsch Algorithm with initial conditions and Oracle
As shown in qiskit 3 below, creates a quantum circuit, assigns number of qubits, generates a random Boolean secret function and visualizes the circuit.
As shown in qiskit4 below, which runs the circuit over a simulator and measures the result.
we achieved fig 10 from the below result1, result2, result3, result4 using IBM qiskit
Implement using Cirq:
In the following code blocks we walk through over implementation of Oracle mentioned in fig 10 and Deutsch Algorithm using Cirq.
As shown in the below cirq 2, generates Oracle for the given secret fucntion
As shown in cirq 3 below, creates Deutsch Algorithm with initial conditions and Oracle
As shown in cirq 4 below, create a quantum circuit, assign number of qubits, generates a random Boolean secret function, run the circuit over a simulator and measure the result.
The result generated is shown in below img 1
References: Qiskit Textbook, Cirq Tutorials, IITM course , Qubit by Qubit(The Coding School) course.
