A Busy Developer’s Guide to Quantum Computing Part 4
In the previous Part of the series I briefly showed how programming a quantum computer looks like.
Check all the articles from the series:
In this Part I’m going to show you a working example of quantum search (see: Grover’s algorithm). The code for this blog is available on GitHub. Here, I’d like to quickly walk you through the main points.
The code is implemented using IBM Qiskit Python SDK. Qiskit provides a simulator that allows one to experiment with the code on a local desktop.
A running example with quantum search
Overall structure
The algorithm is implemented as a sequence of operations. They are defined bottom-up forming a nested structure.
Static predicate
The first operation is StaticPredicate.
An example of a quantum circuit with the StaticPredicate
Basically, it is a test stub that represents some search problem. It is statically configured with a binary sequence (a “password”) which defines the input we are looking for.
The qubits q0, q1 and q2 represent inputs and q3 is an ancilla qubit. (I was discussing ancilla qubits in Part 3.) The qubits representing inputs are expected to be in a superposition of all possible binary combinations and the ancilla qubit should be set to 0. All inputs are compared with the password and for the selected input the ancilla is flipped to 1.
The StaticPredicate is a composite operation. You can peek inside it to see its internal structure.
A structure of the StaticPredicate with the password "011"
The gates X (Not) and I (Identity; used here as a placeholder) encode the “password” and the MCX (Multi-Controlled-Not) flips the ancilla qubit.
Here you can see a result of an experiment running a quantum circuit with the StaticPredicate alone.
A result of a quantum circuit with the StaticPredicate (2000 shots; the selected input is highlighted)
As a side effect, the ancilla qubit gets entangled with the input qubits.
Stub function
The next operation is StubFunction.
An example of a quantum circuit with the StubFunction
It wraps around the StaticPredicate. But it encodes the result differently — to comply with the requirements of the Amplifier operation defined next. The Amplifier requires the selected input to be marked with a flipped phase. Simultaneously, it requires the ancilla qubit to be disentangled and reset to 0.
Here you can see the result of an experiment running a quantum circuit with the StubFunction alone.
A result of a quantum circuit with the StubFunction (2000 shots; the selected input is highlighted)
The ancilla qubit is flipped back to 0. The flipped phase is not visible in the result.
To compute the result, the StubFunction first applies a StaticPredicate. Then it flips the phase of the selected input using a Z gate. (I talked about phase in Part 2 and defined the Z gate in Part 3) And then it disentangles the ancilla qubit by applying the StaticPredicate in reverse. (The pattern we are using here is called uncomputation.)
A structure of the StubFunction (the "dg" suffix denotes an inverse)
Amplifier
The Amplifier operation implements the generic part of the quantum search algorithm. Basically, it amplifies somewhat the probability of any input marked with the flipped phase.
The Amplifier is also a composite operation. You can peek inside it to see its internal structure.
A structure of the Amplifier
The Amplifier is generic. It is unaware of the “password” encoded in the StubFunction. (The particular gate structure is taken from Quantum Computing by Nihal Mehta. Its functionality is clearly explained in Quantum Computing for Everyone by Chris Bernhardt.)
Here you can see a result of applying the Amplifier to the result of the StubFunction.
A result of applying the Amplifier to the result of the StubFunction!
The Amplifier operation can be repeated a couple times. Each time it amplifies the probability further. Accidentally, in doing so, it flips the phase back and the marking of the selected input gets lost. So, to amplify the probability further, we need to repeat the StubFunction as well.
Search Iteration
The StubFunction and the Amplifier both form a single SearchIteration.
A structure of a single SearchIteration
The SearchIteration needs to be repeated a couple times to maximize the probability of the selected input.
A quantum circuit with two search iterations
It can be shown that the best possible probability is achieved after O(√n) iterations. After that, the probability starts to degrade.
Here you can see a result of 2 iterations, which is optimal for 3 input qubits.
A result of 2 iterations for 3 input qubits (2000 shots)
Happy testing
I encourage you to play with the example project. Among other things, the code allows to easily increase the number of input qubits.
For example, here you can see a result of 724 iterations for 20 input qubits.
A result of 724 iterations for 20 input qubits (2000 shots)
For this number of iterations the probability of finding the “password” approaches 0.98. Note that on a classical computer it would take 10⁶ iterations to find the selected input with equal probability.
Summary
In this Part I presented a walkthrough of a working implementation of quantum search. I constructed a solution from two complex gates:
- the StubFunction — representing a custom search problem,
- the Amplifier — a generic implementation of Grover’s algorithm.
If you replace the StubFunction with any cost function fulfilling basic assumptions defined in Part 1, you’ll get a generic schema for solving a wide range of optimization problems using a quantum computer.
Where to go from here
Nowadays, there are a number of great sources to start learning about quantum computing. A lot of effort has been made to make the subject more approachable since its inception.
For those, who prefer a clear theoretical background, I can highly recommend Quantum Computing for Everyone by Chris Bernhardt. Those, who prefer a more hands-on approach, might want to look at Quantum Computing by Nihal Mehta.
The IBM Qiskit site is another great source of learning materials.
Reviewed by Paweł Stawicki
Check all the articles from the series: