How to Solve a Problem with Quantum Computing

Quantum computing comes with quite a few caveats.

• When transforming qubits, we have to ensure reversibility.
• We can’t copy a qubit in an arbitrary state.
• Most importantly, we can’t measure a qubit without collapsing its state of superposition.

A qubit can do things a classical bit can’t. A qubit is not restricted to 0 or 1. It can be a combination of both states. Moreover, we can entangle two qubits so that they share a state of superposition.

With these characteristics, qubits are a powerful tool, if used properly. Of course, we can treat qubits like ordinary bits and solve a problem the same way you solve other computational problems. We wouldn’t benefit from the advantage a quantum computer promises, though. When solving a problem classically, we won’t see any quantum speedup. The algorithm will be much slower because a quantum computer is prolonged (in terms of clock frequency) and minimal (the number of qubits).

This lesson teaches us how to solve a problem through an algorithm faster than a classical one. By that, we mean that the quantum algorithm will solve a problem in fewer steps than a classical algorithm requires. If both computers were equal in speed and size, the quantum computer would solve the problem faster. However, a classical computer might compensate for the larger number of steps by its sheer speed and size. With the increasing complexity of the problem to solve, speed and size will no longer suffice. There are problems, such as the factorization problem, that are too complex for a classical computer, regardless of its speed and size, but not too complex for a quantum computer, at least theoretically.

The problem we use as our example is not one of these problems. A classical computer solves it in a split second, but the example allows us to demonstrate how to solve a problem the quantumic way.

Let’s assume we have a function $f$. It takes a single bit as input–either 0 or 1, and provides a single bit as its output, too. Again, either 0 or 1. There are four different possible functions.

• The function $f_0$ always returns 0.
• The function $f_1$ returns 0 if the input is 0, and returns 1 if the input is 1.
• The function $f_2$ returns 1 if the input is 0, and returns 0 if the input is 1.
• The function $f_3$ always returns 1.

The functions $f_1$ and $f_2$ provide balanced outputs because for half of the inputs, they return 0 ($f_1$ if the input is 0 and $f_2$ if the input is 1), and for the other half, they return 1 ($f_1$ if the input is 1 and $f_2$ if the input is 0).

If we’re given one of these functions at random, how can we determine whether the function is constant ($f_0$ or $f_3$) or balanced ($f_1$ or $f_2$)? We don’t care about the specific function we got. We only care about whether it is constant or balanced.

Classically, we’ll have to run the function twice. We’ll run it with the input 0. Suppose you then get 0. As a result, the function at hand could be the constant function $f_0$ that always returns 0. It could be the balanced function $f_1$ that returns 0 if the input is 0. We’ll have to rerun the function with input 1 to decide whether the function is constant or balanced. The constant function $f_0$ still returns 0, but the balanced function $f_1$ returns 1 for input 1.

The same situation applies if we get 1 because of running the function for the input 0. We would need to distinguish between the balanced function $f_2$ and the constant function $f_3$.

It doesn’t help to run the function with the input 1 first, either. With either result, 0 and 1, the function at hand could be constant or balanced. We need to rerun the function with input 0.

In quantum computing, we only need to run the function once.

We start with a new quantum gate, the gate $O_i$. This gate should represent our four functions $f_i$. Mathematically, this would be:

$$O_i(|x\rangle)=|f_i(x)\rangle$$

It transforms an arbitrary quantum state $|x\rangle$ into the quantum state $|f_i(x)\rangle$, the output of the function $f_i$ given the input $x$.

Given that $O_i$ is a quantum transformation gate, it must be reversible. Therefore, it must have the same size of input and output, and each output must uniquely identify the input it originates from.

But that’s a problem. The constant functions always return the same value regardless of their inputs. Given their output, we can’t tell what the input was.

We can deal with this problem with a little trick. We add a second qubit $|y\rangle$, and we use the exclusive or (XOR, $\oplus$) operator to track the function’s result $f_i$.

Mathematically, the refined gate $O_i$ is:

$$O_i(|x\rangle\otimes|y\rangle)=|x\rangle\otimes|y\oplus f_i(x)\rangle$$

---