Understanding the Power of Quantum Computing 1: Deutsch Problem
Ping Zhou, 2021-04-01
Introduction
Quantum computing is one of the hottest topic these days. You might have already heard about hypes like “quantum supremacy”. But why quantum computers can be faster on solving some problems? And how does it work behind the scene?
In this article I’m going to use a simple problem (the Deutsch Problem) as an example and walk you through the process.
Ok, let’s get started.
Terms and Basic Concepts
Before we start discussing the problem, let’s first review some basic terms and concepts.
Qubits
A single classical bit can be either 0 or 1 at any time. A qubit, similarly, can be at one of the“base” states -
Quantum Gates
Some of the quantum gates we’ll use in this example:
gate: “Identity” gate, which outputs same as its input. gate: aka Hadamard gate. We’ll use this gate to put our qubits into superposition state. Essentially, H gate will turn into , and turn into . Another attribute we want to note here is that , meaning that applying two H gates in a row will cancel each other. gate: Flips the input (i.e. it turns into , and turns into ). gate: This gate operates on the “phase” of the input. The output of Z gate is . If we supply input to a Z gate, we’ll still get . But if we supply to a Z gate, we’ll get at the output. gate: aka “Controlled NOT” gate. This gate takes 2 qubits as inputs, let’s say and . If is 1 then is flipped, otherwise is unchanged.
Some other useful theorems of these quantum gates (we’ll need them later in discussion):
Quantum Circuit
A quantim circuit is like a blueprint of the algorithm. Each qubit is a line in the diagram, with quantum gates connect the lines (qubits) and time flows from left to right.

Deutsch Problem
The problem we are going to solve with quantum computing is called the Deutsch Problem. It is, in my opinion, the simplest problem that we can use for demonstrating the advantage of quantum computing.
Suppose someone gave us a 1-bit function (i.e. both its input and output are 1-bit). The function was given as a “blind box”, meaning that we don’t know how it works. The only thing we can do with this function is to evaluate it - by feeding it with input and observing its output.
Since this function takes 1-bit input and outputs 1-bit results, there aren’t many possible variants. In fact, there are only 4 possible 1-bit funcitons:
, the function always outputs 0 regardless of input. , the function always outputs 1 regardless of input. , the function outputs same bit as the input. , the function outputs the inverse of the input bit.
Among these 4 functions, the first two are called “constant” functions because they return constant values regardless of input. The other two functions are called “balanced” functions because they return 0 or 1 for half of the possible inputs respectively.
Deutsch Problem: If we are given a 1-bit function f(x) as a blind box, how do we decide whether it is constant or balanced? Remember, the only thing we can do with the function is to evaluate it!
If we are using a classical computer, how many times do we need to evaluate the function? Apparently we’ll need two evaluations - one evaluation won’t be enough to tell if it’s constant or balanced.
But if we are using a quantum computer, we just need to run our circuit once and we’ll know the answer!
Solving Deutsch Problem with Quantum Computing
Transform the problem for quantum circuit
To solve Deutsch Problem with quantum computing, we need to somehow “incorporate” f(x) in our quantum circuit. However in quantum circuit, every operator must be reversible (i.e. you must be able to compute input back from output). The function we are given is not likely to meet this requirement - E.g. constant functions are not reversible. So how do we interact with f(x) in our quantum circuit?
Fortunately there is a generic solution to this issue: We transform the function f(x) into a quantum operator (a block of quantum circuit)

This quantum operator uses an additional (auxilary) input (y), in additional to the original input to function f(x). And on the output side, it outputs x and the Exclusive OR of y and return value of f(x). It’s easy to validate that this operator
So with quantum computing, we need to transform the Deutsch Problem a little bit so it can be computed by our quantum circuit. We need to ask the person who gave us the function f(x):
Instead of giving me function f(x) as a blind box, can you give me its corresponding
(also as a blind box)?
The person kindly wrapped f(x) into
Build our quantum circuit
The quantum circuit for solving Deutsch Problem is actually pretty simple. We initialize two qubits to

We run the circuit and measure the first qubit. If we get 0 from measurement, then function f(x) must be constant. Or else it must be a balanced function.
That’s it! We only run the circuit once and we get the result of Deutsch Problem!
How it works
The quantum circuit worked like magic - we just need to run circuit once and it tells us whether the function is constant or balanced. But how it actually achieves this acceleration? In this section I’ll walk you through the analysis.
We split our circuit into time steps and check the system state of each time step.

Time step t0:
Our system is at initial state
Time step t1:
The H gates put the two qubits into superpositions. The first qubit becomes
Time step t2:
The input of
- If f(x) is 0, then the second qubit will remain unchanged:
, or . - If f(x) is 1, then the second qubit will be the inverse of y (
). But y is in superposition state, how do we inverse it? Here is the trick: You can distribute the inverse operation into the equation - becomes and vice versa. So the second qubit becomes after inversion. But wait… isn’t this just with a negative sign ( )?
Summarizing the two outcomes of f(x), the second qubit will get a negative sign if f(x) is 1. In other words, the second qubit can be expressed like this:
What does this tell us? It tells us that if we supply
In other words, the value of f(x) now becomes the global phase of our system - it controls the negative sign before
But how does this even help us determine the attribute of f(x)? Global phase is not distinguishable when we measure the state, after all.
Let’s examine the four possibilities of f(x) and what
- If f(x) is a constant function that always returns 0, then
. So is equivalent to an gate. - If f(x) is a constant function that always returns 1, then
. So is equivalent to ( gate with negative sign). - If
(i.e. it returns the same bit as x), then . Recall that a Z gate gives us , this means is equivalent to a Z gate in this circumstance. - Similarly if
(i.e. it returns the inverse of x), it’s easy to show that is equivalent to gate (a Z gate with negative sign).
Now we are getting somewhere: If f(x) is constant,
Time step t3:
Recall these theorems we mentioned earlier:
Looking at the first qubit of our circuit - what happened from t0 to t2? We got an H gate, then the
- If
is equivalent to gate (meaning that the function is constant), the operations from t0 to t3 on the first qubit will be , , then again. And since , the operations from t0 to t3 will be equivalent to a gate on the first qubit. - Similarly, if
is equivalent to (i.e. the function is balanced), operations from t0 to t3 will be . So from t0 to t3 it was as if we did a gate on the first qubit.
Now let’s measure the first qubit - guess what we’ll get?

If the function f(x) is constant, from t0 to t3 the first qubit will go through a
If the function f(x) is balanced, the first qubit will go through a
Now we know how quantum computing solves Deutsch Problem with just one run!
Conclusion and Thoughts
What do we learn from this journey? We can see that superposition played a crucial role in solving the Deutsch Problem with just one run. By putting our qubits into superpositions and feeding them into
“Evaluation twice vs. run circuit once” might seem trivial to you. But think about it - what if we expand the input (number of bits) to the problem? On a classical computer, the number of evaluations will grow exponentially (well, if we want to be 100% sure about the answer). But with quantum computer we’ll still only need to run the circuit once!
Appendix: How to construct ?
One question you may still have is: How does the person who gives us function f(x) contruct the corresponding

This can be done by examining the truth table of
x | 0 | 1 |
---|---|---|
f(x) | 0 | 1 |
So y is inversed if x is 1 and unchanged otherwise. Apparently
