The Quantum Oracle, Demystified

The qubit is not 0 or 1. It is in a relationship between states 0 and 1.

Notwithstanding, the ability to entangle two qubits is mind-blowing. We measure one qubit, and another instantly changes its state, no matter how far away it is. It’s hard to believe that anyone would not think of teleportation like in Star Trek.

Once we start working with (simulated) qubits, the superposition state comes down as a probability. Entanglement emerges as a way to manipulate these probabilities. We may not be able to see how this kind of computing could be so much faster until we come across the quantum oracle.

In the previous lesson, we already got to know the quantum oracle. As part of David Deutsch’s algorithm, it allowed us to solve a problem in fewer steps than a classical algorithm would need. It identifies the type of function in a single shot. This is less than the two shots a classical algorithm needs.

So how does it work?

It’s like a magic trick that baffles us when we see it for the first time, but when we find out how it works, it loses its mystery. When we join the community of magicians, a select few who know the trick, we can’t look at it anymore and think, “Wow.”

The magician presents a coin to us. While the coin is in the air, the magician predicts the coin to show heads. They catch the coin, and when they reveal the side, the coin is heads up.

How could they have known? One assumption is that the coin might have been manipulated, but when the magician presents it to us, it looks like a regular coin. Before they toss it again, they ask us to predict the result. This time, we say tails–the coin lands, tails up.

When we examine the coin again, it will still look like a normal coin. But this time, it’s a quantum coin. When we look at the coin, it’s either heads or tails, but, unlike a regular coin, it’s in a state of superposition once we toss it.

A regular coin is sensitively dependent on the initial conditions. If we knew everything in complete detail, such as the applied force when tossing the coin, the rotational force, the air pressure, and even the slight air movements, then we could calculate how a normal coin would land. If we knew everything in detail, “randomness” would disappear.

A quantum coin, by contrast, is truly random. So how does the quantum coin allow the magician to predict the outcome?

While a quantum superposition contains randomness, it does not behave arbitrarily. The quantum system abides by strict rules, and these rules can be specified. One of these rules involves a quantum oracle.

Our magician created a quantum system that seems to let them know the outcome of tossing the coin. It sounds like an oracle, doesn’t it?

What the magician actually did was create a quantum system that would listen to their predication and behave accordingly. If this doesn’t seem plausible, we can try creating this quantum system programmatically with Python and Qiskit.

A qubit denotes our quantum coin. Once we toss it, it is in a state of superposition of the states $|0\rangle$ and $|1\rangle$. If we look at it, it is either 0 representing the coin lands heads up or 1 representing tails up, each with a probability of 0.5.

Mathematically, the state of the qubit that we also know as $|+\rangle$ is $\psi=|+\rangle=\frac{1}{\sqrt{2}}|0\rangle+\frac{1}{\sqrt{2}}|1\rangle=\begin{bmatrix} \frac{1}{\sqrt{2}} \\ \frac{1}{\sqrt{2}} \end{bmatrix}$.

We’ve seen this state before. We can create it by applying the Hadamard-gate on a qubit in the state $|0\rangle$.

The magician’s prediction is a quantum transformation gate, too.

They crafted two gates and connected them with their prediction. They connected the $I$-gate with the prediction “heads up”, and connected the $R_Y(\pi)$-gate with the prediction “tails up.”

The $I$-gate is the Identity-gate. Its output is equal to its input. It does not change anything.

...