Multiverse 2.357

Welcome back for another look at the basics of quantum computer programming. We’re going to continue to use IBM’s excellent programming framework called Qiskit, and Jupyter notebooks to demonstrate with the usual disclaimer that you can code this without the notebook, and the same ideas can be realized in any quantum programming language. If you need a refresher on the basic math of quantum programming, we covered it in the previous two posts, although there is much more to it. If you want to review the entanglement program we wrote, first ran on a local simulator and then ran on a real quantum computer, feel free to review those as well, or maybe just review how to get started uing IBM Q.

The issue for this post is what can a quantum computer do that a conventional computer cannot? If Richard Feynman was the father of quantum computing, then David Deutsch was probably the uncle. Deutsch described a problem that takes multiple steps to solve on a classical computer and can be solved in a single step on a quantum computer. In this post we’ll describe the original version of the problem and show the quantum computer solution with hopefully a solid explanation.

David Deutsch is a physicist who was an early pioneer in quantum computing. In 1985 he came up with the simple example we’ll illustrate today. In 1992 he collaborated on a version known as the Deutsch–Jozsa problem, which generalizes the problem to n bits instead of the original one bit. The upshod is that a polynomial speedup is possible using a quantum computer. In the simple case a classical computer will need two steps to solve it and the quantum computer needs only one step.

Here is the basic problem description: given a black box (an oracle) containing a function that takes one binary input and produces a binary output, determine whether that function is constant or variable. Here a constant function means that it always returns 0 or that it always returns 1. If it is a variable function, it will return a 0 half the time and will return a 1 half the time. For our quantum computer solution, we’ll use two qubits: one for the input x, and one for the result f(x) because with quantum computers these gates need to be reversible.

So consider the black box to contain one of the four functions that operate on a single operand and produce a single result: the identity operator, the negation operator, the constant 0 function, and the constant 1 function. The variable functions are the first two, since for an input of either 0 or 1, the identity function returns that 0 or 1. Similarly for inputs of 0 or 1 the negation function will return a 1 or 0 respectively. The constant functions return a constant value regardless of the input. Our first qubit x is the input, and f(x) represents the answer qubit.

Constant functions above: the zero function simply measures the initial |0> state of the answer qubit regardless of the input value, and the one function simply does a bit flip on the initial |0> state then measures.

The balanced functions are shown below: identity and negation. The identity function leaves the answer qubit in the |0> state if x is |0> and does a bit flip if x is |1>. The negation function is the same as the identity function, but does a bit flip on the answer qubit before the measure operation.

The solution looks funny but the math works; we’ll massage the qubit values before and after the black box part of the circuit. We’re going to consider all four of these function as being inside our black box, one at a time, in order to demonstrate that this circuit decides correctly if the mystery function is one of the constant or variable functions.

Two qubits are first bit-flipped then the Hadamard gate is applied to each, followed by the mystery function. After applying one of those four operations, Hadamard gates are applied once more and then the measures. The claim is that regardless of which specific function is contained in that black box, a constant function will produce an output of |11>, and a variable function will produce a |01> or |10> depending on which qubit has x as the input.

Our qubits always start in the |0> state, so creating a constant zero function is trivial – just do nothing. This is depicted below by having no gates in between our barriers that indicate the black box. Sure enough, the result of our measures shown in the histogram gives us |11> as predicted.

Similarly we put a single x gate inside the barriers as our constant one function, and our measure gets a |11> state as you can see below. Both constant functions have resulted in this |11> being measured.

Our identity function is not put inside the barriers and sure enough, as predicted, our measure results in a |10> since it’s a variable function.

And when we put the two gates from our negation function inside the black box as shown below, our measure operation results in a |10> as well.

This is what David Deutsch figured out in 1985, but it was generalized in the 1990s to n bits of input instead of one. This “oracle problem” was important because it laid the groundwork for Simon’s algorithm, which in turn led to Shor’s famous factoring algorithm.

Here is the entire solution to Deutsch’s Oracle with my best attempt at explanations in a Jupyter notebook, so you can run these for yourself.