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 $$ ...