Deutsch’s Algorithm Simulation with PennyLane
In 1985, a British physicist at the University of Oxford devised the first quantum computational algorithm; one that tackles a seemingly unimportant/contrived problem. Although it has no use in today’s realm of QC, this primal algorithm, nonetheless, serves as an excellent proof of concept that, in certain instances, quantum computers can exponentially outperform their classical analogues.
For those unfamiliar with QC, a quantum algorithm, in short, is a type of computational algorithm that harnesses the phenomena/postulates of quantum mechanics. Think of it as a step-by-step procedure — a circuit of quantum logic gates which acts on some input qubits and terminates with a measurement. Once we get into the body of this article, this definition will become more intuitive.
Before we begin, if you are interested in learning more about the foundations of quantum computing, as well as a fascinating application of this technology in the pharmaceutical industry, feel free to give my first article a read.
Deutsch’s Problem
Although he was not the first to come up with the idea of quantum computing (that can be credited to Richard Feynman and Yuri Manin), David Deutsch, the pioneer of Deutsch’s algorithm, is widely recognized as a founding father in the field. He is an extreme optimist. Proposing that “all evils are due to a lack of knowledge”, David Deutsch believes that we’ll solve war, global warming, and consciousness — and that will just be the beginning. He’s “opposed to the thesis that a scientist must believe his theory”. Now, whether it was a result of his pure genius, ubiquitous optimism, or a combination of both, David Deutsch is renowned for sparking a paradigm shift in the field of computer science— the beginning of the quest to attaining ‘quantum supremacy’.
Philosophies aside, Deutsch’s problem was a pretty simple one. Essentially, the algorithm seeks to determine whether some function, one that maps a single bit to another ( f : {0,1}→{0,1} ), is constant or balanced. While a balanced function outputs either value, one or zero, half of the time (f(0) ≠f(1)) , a constant function yields the same value for any given input (f(0) = f(1)).
In the world of classical computation, solving this problem would require two oracle calls; that is, evaluations of a given function. Say that we found f(0) to be equal to zero. This is only half of the battle. Our function could be constant (always yields zero), or rather, it could be balanced (f(1) yields one instead of zero). The only way of finding out would be to call f(1) separately. Classically, the solution to Deutsch’s problem requires two steps, which, for Deutsch (among many others), was one step too many.
By utilizing the powers of superposition, David Deutsch proved that his problem could be solved in one go — a single quantum oracle that performs a single logical query. Furthermore, the quantum computer can evaluate multiple values of ‘x’ for f(x) instantaneously.
Deutsch’s Solution
Consider two input qubits, one initialized in the state, |0⟩, the other in the state, |1⟩. Visualizing this in vector form, the qubits begin as:
From this, we apply a Hadamard transformation to each qubit. This quantum operator is a one-qubit rotation, mapping the above basis vectors to two superposition states where there is equal probability of measuring either zero or one. Its normalized unitary matrix is defined below as:
Thus, our qubits will now be in the state:
The next — and most profound — step in the algorithm is to pass our, now, superposed qubits through a unitary operator that maps |x, y⟩ → |x, y ⊕ f(x)⟩, where ⊕ indicates addition modulus two (add two values, divide by two, print remainder). For those more familiar with computer science, addition modulus two is also known as a XOR gate. Before performing this operation, the qubits are expanded to the form:
Now, as the qubits pass through the unitary matrix, they are acted on as follows:
Let’s expand upon this oracle in a case-by-case basis, in order to gain better intuition of what is truly going on in this algorithm.
Let f(0) = 0, f(1) = 0.
Let f(0) = 1, f(1) = 1.
Let f(0) = 0, f(1) = 1.
Let f(0) = 1, f(1) = 0.
With the factored results of all four possible cases, we must now pass the first qubit through a Hadamard gate once again and measure the values. This final step of the algorithm yields the following:
As you can see, for cases one and two — where f(0) = f(1) — Deutsch’s algorithm does not change the state of the first qubit. Whereas for cases three and four — where f(0) ≠ f(1) — the first qubit is flipped from |0⟩ → |1⟩. Contrary to classical means of solving Deutsch’s problem, we can determine a character of two functions be only performing one evaluation.
Deutsch’s Algorithm in PennyLane
Let’s now code Deutsch’s algorithm using PennyLane framework. The program begins by creating our quantum device; essentially a simulated ‘quantum computer’ through which we can run our algorithm. Although there is a vast array of different quantum devices that are built-in to PennyLane software, for the purpose of this algorithm, we will be using default.qubit — “a simple state-vector qubit simulator written in Python”. The ‘wires’ and ‘shots’ in the code below defines the number of qubits, and times that a measurement will occur, respectively.
Now, we must define the function that will be evaluated (one of the four cases explained in the above section). Let’s consider case one — where f(0) = 0 and f(1) = 0.
Before starting on the actual circuit, we can prepare the oracle through which our qubits will pass through.
Further, let’s define our unitary matrix as the oracle calling the function we defined above.
In hybrid computation, an algorithm consists of both classical and quantum components. In PennyLane’s framework, these quantum units are represented using an object called a quantum node, notated as QNode. A quantum node consists of a quantum function, such as the circuit used in this simulation, and a device on which it executes. The code below defines our QNode.
We will start with two qubits initialized in the state |00⟩, before passing the second one through a PauliX gate. This puts our qubits into the initial state, |01⟩.
Let’s now apply the Hadamard gates on both superposed qubits.
Now, we apply the oracle that was previously defined.
The final step of this algorithm is to apply another Hadamard gate on the first qubit, measure that qubit, and call the circuit.
Based upon the algorithm’s function, the value, ‘0’, is the 1x1 array that is returned. As explained in the previous section, this would be the result in either case one or two, where the defined function is constant. The algorithm would, contrarily, return ‘1’ if the function were to be balanced — case three or four.
As mentioned, this algorithm is solely for proof-of-concept purposes. Especially considering we are running the program on a classical device, it isn’t real quantum computing. That said, PennyLane’s framework does serve as excellent means to simulate or build your own quantum algorithms— ones that can be of much greater complexity (and usefulness) than this one.
Connect with Me :)
LinkedIn — https://www.linkedin.com/in/ella-ceroni-800992220/
Medium — https://medium.com/@ellaceroni
Email — ellaceroni@gmail.com