The Quantum Oracle Demystified

The trick no magician would reveal

This post is part of the book: Hands-On Quantum Machine Learning With Python.

When I first started learning quantum computing it took me quite a while to understand how it possibly could be faster than classical computing. Something mysterious must be going on.

Of course, the quantum superposition a qubit can be in is astonishing. 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. You measure one qubit and another one instantly changes its state, no matter how far away it is. It is hard to believe that anyone would not think of teleportation as in Star Trek.

But once I started actually working with (simulated) qubits, the state of superposition came down as a probability. Entanglement emerged as a way to manipulate these probabilities. All this is pretty cool. But it isn’t mysterious at all. I could not really see how this kind of computing could actually be so much faster.

Then, I came across the quantum oracle. The name itself speaks of mystery. Finally, I must have found the magic ingredient I was searching for. The one thing that, once I understood how it works, would enable me to solve the problems intractable for a classical computer.

In the last post, 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.

Sounds magical. Doesn’t it?

So, how does it work? you ask.

It’s like a magic trick. It baffles you when you see it for the first time. You want to know how it works. But once someone tells you the secret, it becomes mundane. It loses its mystery. While you join the community of magicians, a selected group who knows the trick, you can’t look at it anymore and just think “wow”.

You still wanna know? Good. Read on.

The magician presents a coin. While the coin is in the air, the magician predicts the coin to show heads. She catches the coin. Guess what you see. The coin is heads up.

How could she know? You’d bet the coin is manipulated. But she presents it to you. It looks like a normal coin. One side heads. The other side tails.

She tosses it again. She asks you to predict the result. This time, you say tails. The coin lands. Guess what you see? The coin is tails up.

You examine the coin again. It still looks like a normal coin. But it is not a normal coin. It is a quantum coin. When you look at the coin, it is either heads or tails, but once you toss it, it is in a state of superposition. It is unlike a normal coin.

A normal coin is sensitively dependent on the initial conditions. If you knew everything in absolute detail, if you knew the applied force when tossing the coin, the rotational force, the air pressure, and even slight air movements, then you could calculate how a normal coin would land. If you knew everything in detail, randomness would disappear.

A quantum coin, by contrast, is truly random. Why then should the quantum coin be the one that allows 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 her know the outcome of tossing the coin. Sounds like an oracle, doesn’t it?

But this is not what she did. Rather, she created a quantum system that would listen to her prediction and behave accordingly.

This doesn’t seem plausible?

Then, why don’t we create this quantum system programmatically with Python and Qiskit?

A qubit denotes our quantum coin. Once you toss it, is in a state of superposition of the states |0⟩ and |1⟩. If.you 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 |+⟩ is

We have seen this state before. We can create it by applying the Hadamard-gate on a qubit in the state |0⟩.

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

She crafted two gates and connected them with her prediction. She connected the I-gate with the prediction “heads up”. And she connected the RY(π)-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.

The RY-gate rotates the qubit state vector around the Y-axis. This is the axis that affects the measurement probabilities. It takes as a parameter the angle by which to rotate the state. The angle π denotes exactly half of a full circuit.

The following image depicts the rotation of the qubit state vector graphically.

When a state vector ends on the left-hand side of the Y-axis, then one of the two amplitudes becomes negative.

When we start in the state |+⟩ a rotation by π results in the state |−⟩ because cos(π/2)=0 and sin(π/2)=1.

Turning the state |+⟩ into |−⟩ did not change the probabilities of measuring 0 or 1 because the probability is the square of the amplitude. And this is positive, in our case it is

In the end, neither one of the two gates changed the measurement probability of the qubit. But the two states differ.

When she prepares the magic trick, the magician does not limit her trick to either one prediction. She wants the flexibility to use a different prediction any time she performs the trick. So, during her preparation, she adds a placeholder into her quantum circuit. She calls it the O-gate. The oracle.

She only knows the oracle can be either the I-gate or the RY(π)-gate.

The I-gate represents her “heads up” prediction and leaves the qubit in the state |+⟩. The RY(π)-gate represents her “tails up” prediction and changes the qubit state to |−⟩.

The savvy magician sees the differences between these two states. This is her chance to make her prediction come true. All she needs to do is to transform the output of the oracle into the state that corresponds to her prediction. She needs to turn the state |+⟩ into |0⟩ and the state |−⟩ into |1⟩. She applies another Hadamard gate on her quantum coin, ehm qubit. It has the desired effect for both possible outputs of the oracle. Have a look:

Sometimes, it may be harder to transform the differences into a meaningful output. But the principle is the same. Identify the differences between the possible outcomes of the oracle and make sure these outcomes result in different measurement results.

Our magician is well prepared now. She has a quantum circuit with an oracle. This is a placeholder. When she runs the circuit, she must fill this placeholder with a valid qubit transformation gate what she does by speaking out loud her prediction.

Here’s the code the magician created.

The magician created a reusable function. It takes as a parameter a callback function — the oracle (line 5). First, we create the QuantumCircuit with a single qubit (line 8). Tossing the coin sets it into superposition. This is what the first Hadamard gate does (line 11). Then, we apply the oracle (line 14). Whatever it is. The magician applies the second Hadamard gate to transform the result of the oracle into the desired state (line 17). Finally, we run the circuit (line 23) and return the results (line 26).

Let’s run the circuit with the heads up prediction.

When the magician predicts heads up, we always measure the qubit as 0, which represents heads up. Let's do the same for the "tails up" prediction.

The “tails up” prediction always results in a qubit that we measure as 1 - the representation of "tails up".

The audience is baffled by her ability to see into the future. But, as usual with magic tricks, this is an illusion. An intended illusion thoroughly crafted by arranging the stage — or in this case — the circuit.

Conclusion

The quantum oracle is nothing but a placeholder for a transformation gate. While it changes the state of the system, it does not tell the future or answer any question. It is up to you to identify how the different gates it may stand for, affect the quantum state differently. And, it is up to you to craft a quantum circuit around the oracle to transform these differences into an answer to your question.

The quantum oracle is a tool. It allows you to distinguish different states of the world. During the construction of your circuit, you specify how these different states should affect the outcome. When you run your circuit in a certain state, it produces the outcome you prepared it to result in.

The oracle is like the switch-case control structure you may know from classical programming. You have a variable, the oracle. When you write your program, the circuit, you don’t know the specific value the variable will have during runtime. So, you specify the behavior for each possible value it may have. Once you run your program, the variable will have a specific value and your circuit will act the way you specified it to and result in the outcome you wanted it to result in.

The quantum oracle is not a magical ingredient. It is a control structure used in quantum computing.

This post is part of the book: Hands-On Quantum Machine Learning With Python.

Get the first three chapters for free here.