Published on

Deutsch's Algorithm: One Query is Better Than Two Queries

Authors
deutsch-algorithm-circuit

This is another win for Quantum Computing over Classical Computing, to solve Deutsch's Problem, Quantum Computing needs less query compared to Classical Computing. What's Deutsch's Problem?

Deutsch's Problem

It's pretty simple, imagine a function f(x)yf(x) \rightarrow y, where (x,y){0,1}(x,y) \in \{0,1\}. Your job is to simply determine whether the function is Constant or Balanced. What does it means? please look at this table:

xax_afa(xa)f_a(x_a)xbx_bfb(xb)f_b(x_b)
0
0
0
0
1
0
1
1
xcx_cfc(xc)f_c(x_c)xdx_dfd(xd)f_d(x_d)
0
1
0
1
1
0
1
1

We can divide these functions into two groups, constant: fa(xa)f_a(x_a), fd(xd)f_d(x_d), and balanced: fb(xb)f_b(x_b), fc(xc)f_c(x_c). In other way, we could see this problem as the same as doing XORXOR to all possible outputs of given inputs x0,1x \in {0,1}:

f(x1)f(x_1)f(x2)f(x_2)f(x1)f(x2)f(x_1) \otimes f(x_2)
0
0
0
0
1
1
1
0
1
1
1
0

As you can see that we could group the function by looking at their results of XORXOR-ing all possible inputs (0,1)(0,1).

Classical Computing

deutsch-algorithm-classical-circuit
https://learning.quantum.ibm.com/course/fundamentals-of-quantum-algorithms/quantum-query-algorithms

We can solve this problem using Classical Computing by querying all possible inputs to the function. Why two queries? Because, knowing f(x1)=0f(x_1) = 0 doesn't give you enough information whether to determine whether it's a Constant or Balanced function. f(x2)f(x_2) could still be 0 which will make this function Constant, or it could also be 1 which will make this function Balanced.

So, the best of what Classical Computing can do to solve this problem is by doing two queries.

Quantum Computing

deutsch-algorithm-circuit

Better than Classical Computing, by using Quantum Computing, we're able to solve the Deutsch's Problem using just single query. All we need to have is a unitary matrix UfU_f which is a permutation matrix that will somehow have the capability to XORXOR the value of the first qubit xx with the second qubit yy.

As you can see that the circuit above is capable to solve the Deutsch's Problem by using just single query. By looking at the result of the measurement of the first qubit, we will be able to determine whether the function ff is Constant or Balance. It will output 00 when the function is Constant and 11 when the function is Balanced.

Mathematical Explanation

I will breakdown the explanation into three states, we will observe the evolution of the qubit states: a\ket{a},b\ket{b},c\ket{c}:

deutsch-algorithm-circuit-grouped

Initially we have this a\ket{a} state:

a=+=120(01)+121(01)\ket{a} = \ket{+}\ket{-} = \frac{1}{2}\ket{0}(\ket{0} - \ket{1}) + \frac{1}{2}\ket{1}(\ket{0} - \ket{1})

We will keep the \ket{-}, because it will be easier to be used to explain the transformation to the next state after applying the UfU_f gate:

b=+=120(0f(0)1f(0))+121(0f(1)1f(1))\ket{b} = \ket{+}\ket{-} = \frac{1}{2}\ket{0}(\ket{0 \otimes f(0)} - \ket{1 \otimes f(0)}) + \frac{1}{2}\ket{1}(\ket{0 \otimes f(1)} - \ket{1 \otimes f(1)})

Okay, it seems a little bit complicated 🙄, let's simplify the equation with one notes (we need to keep the \ket{-} state isolated), because it will intuitively tells us that the second qubit is unchanged. By observing the equation above, we could generalize the equation to be like this:

0a1a=(1)a(01)\ket{0 \otimes a} - \ket{1 \otimes a} = (-1)^a(\ket{0} - \ket{1})

A gentle reminder: x0=1x^0 = 1. By using this generalization, we could transform our b\ket{b} state to be like this:

b=120(1)f(0)(01)+121(1)f(1)(01)\ket{b} = \frac{1}{2}\ket{0}(-1)^{f(0)}(\ket{0} - \ket{1}) + \frac{1}{2}\ket{1}(-1)^{f(1)}(\ket{0} - \ket{1})

or

b=(0(1)f(0)+1(1)f(1)2)\ket{b} = \ket{-}\bigl(\frac{\ket{0}(-1)^{f(0)} + \ket{1}(-1)^{f(1)}}{\sqrt{2}}\bigl)

Actually, we can also take out (1)f(0)(-1)^{f(0)}:

b=(1)f(0)(0+1(1)f(0)f(1)2)\ket{b} = (-1)^{f(0)}\ket{-}\bigl(\frac{\ket{0} + \ket{1}(-1)^{f(0) \otimes f(1)}}{\sqrt{2}}\bigl)

When f(0)f(1)=0f(0) \otimes f(1) = 0, we will get:

(1)f(0)+(-1)^{f(0)}\ket{+}\ket{-}

otherwise, when f(0)f(1)=1f(0) \otimes f(1) = 1 we will get:

(1)f(0)(-1)^{f(0)}\ket{-}\ket{-}

Now, we arrived to the observation of last state c\ket{c}. In this state, we just simply apply HH (Hadamard) operation to the first qubit and it will simply give us this states:

When f(0)f(1)=0f(0) \otimes f(1) = 0, we will get:

(1)f(0)0(-1)^{f(0)}\ket{0}\ket{-}

When f(0)f(1)=1f(0) \otimes f(1) = 1 we will get:

(1)f(0)1(-1)^{f(0)}\ket{1}\ket{-}

As you can see that the second qubit is unchanged (\ket{-}) while the first qubit's state is depending on the result of f(0)f(1)f(0) \otimes f(1). After the measurement on the first qubit, we will get the classical value 00 when the function is Constant and 11 when the function is Balanced.

Qiskit Implementations

First, we need to define the four functions fa(x)f_a(x),fb(x)f_b(x),fc(x)f_c(x),fd(x)f_d(x). All these four functions is just a quantum circuit with some qubit operations that represent the behaviour of each function:

Import qiskit library:

from qiskit import QuantumCircuit

fa(x)f_a(x): (f(0)=0\bigl(f(0) = 0, f(1)=0)f(1) = 0\bigl):

def f_a() -> QuantumCircuit:
    circuit = QuantumCircuit(2)
    return circuit

print(f_a())

Output:

q_0: 
     
q_1: 

fb(x)f_b(x): (f(0)=0(f(0) = 0, f(1)=1)f(1) = 1).

def f_b() -> QuantumCircuit:
    circuit = QuantumCircuit(2)
    circuit.cx(0, 1)
    return circuit

print(f_b())

Output:

q_0: ──■──
     ┌─┴─┐
q_1:X     └───┘

fc(x)f_c(x): (f(0)=1(f(0) = 1, f(1)=0)f(1) = 0).

def f_c() -> QuantumCircuit:
    circuit = QuantumCircuit(2)
    circuit.cx(0, 1)
    circuit.x(1)
    return circuit

print(f_c())

Output:

q_0: ──■───────
     ┌─┴─┐┌───┐
q_1:X ├┤ X     └───┘└───┘

fd(x)f_d(x): (f(0)=1(f(0) = 1, f(1)=1)f(1) = 1).

def f_d() -> QuantumCircuit:
    circuit = QuantumCircuit(2)
    circuit.x(1)
    return circuit

print(f_d())

Output:

q_0: ─────
     ┌───┐
q_1:X     └───┘

Next, we need to create a circuit for our Deutsch Algorithm:

def deutsch_algo_circuit(function: QuantumCircuit):
    n = function.num_qubits - 1
    circuit = QuantumCircuit(n + 1, n)
    
    circuit.x(n)
    circuit.h(range(n + 1))

    circuit.barrier()
    circuit.compose(function, inplace=True)
    circuit.barrier()

    circuit.h(range(n))
    circuit.measure(range(n), range(n))

    return circuit

print(
    deutsch_algo_circuit(
        f_c()
    )
)

Output:

     ┌───┐      ░            ░ ┌───┐┌─┐
q_0:H ├──────░───■────────░─┤ H ├┤M     ├───┤┌───┐ ░ ┌─┴─┐┌───┐ ░ └───┘└╥┘
q_1:X ├┤ H ├─░─┤ X ├┤ X ├─░───────╫─
     └───┘└───┘ ░ └───┘└───┘ ░       ║ 
c: 1/════════════════════════════════╩═
                                     0 

All we need to do now is just running our algorithm on Quantum Computing simulator:

from qiskit_aer import AerSimulator

circuit = deutsch_algo_circuit(f_c())
result = AerSimulator().run(circuit, shots=1, memory=True).result()
measurements = result.get_memory()

if measurements[0] == "0":
    print("constant")
else:
    print("balanced")

Output:

balanced

Yeay! We've successfully solve the Deutsch's Problem using Deutsch's Algorithm and run it on Quantum Computing simulator and get expected result. You could try to test another function and see whether it's returning the expected or not.

If you have anything to discuss, please drop your comments below! 🍻🍻