[ad_1]
Implementing the Quantum Approximate Optimization Algorithm using functional programming
This article will explain the most important parts of the Quantum Approximate Optimization Algorithm (QAOA). QAOA is a machine learning algorithm that you can use to solve combinatorial optimization problems.
The special thing is this algorithm caters to the specificities of quantum computers — a new kind of computer that promises exponential speedups in problem-solving.
Even though quantum machine learning (QML) — that is, using quantum computing to solve machine learning algorithms — is one of the most promising technologies, it is as challenging!
Therefore, this article aims to explain the concepts underlying QAOA in an accessible way.
Quantum computing, optimization, and machine learning rely heavily on mathematics. Unless you’re a mathematician, it will be a daunting endeavor.
Fortunately, some QML libraries, such as IBM Qiskit, solve this problem. They provide easy-to-use interfaces and hide all the complexity from you.
As I showed in my previous post, they even take care of the problem formulation.
In that post, I used the Quantum Approximate Optimization Algorithm (QAOA) to solve a combinatorial optimization problem — how to respond to wildfires.
The only thing you have to do is to specify the individual values of your problem.
It is too good to be true, no?
Even though these libraries let you use quantum machine learning without bothering about math, quantum mechanics, or anything complicated, they likewise do not teach you much.
If you want to understand how an algorithm works, you’re right back to where you started. If the Qiskit library is that good, why don’t you look at their examples to understand how the QAOA works?
The following figure depicts an excerpt of their example.
I think there’s not much to add, is there?
…
A little, perhaps.
So, let me offer you an alternative explanation. One that does not ask for a math degree. But one that exploits the expressiveness of functional programming (in Python).
The story of functional programming is quickly told.
Functional programming breaks down an application into a set of functions. Ideally, functions only take inputs and produce outputs and have no internal state that affects the output produced for a given input.
In that sense, the QAOA algorithm is a function that solves a problem by optimizeing a set of params. In other words, we aim to find the best values for these params.
To decide which params are best, we assess them based on the result we obtain from compute ing a (quantum) circuit that uses these params to encode the problem (problem_circuit) and its solution (ansatz_circuit).
This is what Qiskit’s description refers to as a variational algorithm. It uses a classical optimization algorithm that makes queries to a quantum computer.
And this is the code.
def qaoa(
problem, optimize, assess, compute,
to_circuit, problem_circuit, ansatz_circuit):return optimize(
lambda params: assess(
problem,
compute(to_circuit(
problem, params,
problem_circuit, ansatz_circuit
))
)
)
Pretty neat, isn’t it?
Let’s proceed to the innermost function, to_circuit.
from qiskit import QuantumCircuitdef to_circuit(problem, params, problem_circuit, ansatz_circuit):
cnt_qubits = problem.size
qc_qaoa = QuantumCircuit(cnt_qubits)
# initial_state
qc_qaoa.h(range(cnt_qubits))
# append problem circuit
qc_qaoa.append(problem_circuit(problem, params[0]), range(cnt_qubits))
# append ansatz circuit
qc_qaoa.append(ansatz_circuit(problem, params[1]), range(cnt_qubits))
qc_qaoa.measure_all()
return qc_qaoa
This function takes the problem and the params. We use the size of the problem to determine the number of quantum bits (qubits) in our quantum circuit.
A qubit is the basic unit of computation in a quantum computer. Even though its internal state is pretty complicated, when you look at it, it is either 0 or 1 — just like a regular bit.
We start with applying the Hadamard gate (h) to all qubits. This puts the qubits into a state where they are equally likely to result in 0 and 1.
Then, we append two sub-circuits using the functions problem_circuit and ansatz_circuit. This is what Qiskit’s explanation refers to as “the unitary U(β,γ) has a specific form and is composed of two unitaries U(β) and U(γ)…”
The first function problem_circuit adds a quantum circuit representing the problem we aim to solve.
def problem_circuit(problem, gamma):
qc_p = QuantumCircuit(problem.size)
for i, j in problem.relations:
qc_p.rzz(gamma, i, j)
qc_p.barrier()return qc_p
In this case, we loop through all relations in our problem. Apparently, we expect a relation to consist of a pair of integer values (i, j). We apply the rzz gate on the two qubits at these positions. The rzz gate is a parameterized (by parameter gamma) rotation around the ZZ-axis of a two-qubit system.
The second function ansatz_circuit adds a quantum circuit representing the solution to our problem.
def ansatz_circuit(problem, beta):
qc_a = QuantumCircuit(problem.size)
for i in range(problem.size):
qc_a.rx(beta, i)return qc_a
This time, we loop through all parts of our problem and apply the rx gate on the respective qubit. This is a parameterized (by parameter beta) rotation around the X-axis of a qubit.
from qiskit import Aer, executedef compute(circuit):
return execute(
circuit,
Aer.get_backend('qasm_simulator'),
shots=1000
).result().get_counts()
Essentially, these circuits use the two params (called beta and gamma) to create a quantum circuit that produces a particular quantum state that Qiskit describes vividly as |𝜓(𝛽,𝛾)⟩. Here, 𝜓 (“psi”) is a placeholder for a quantum state. 𝛽 and 𝛾 are the parameters that define this state.
This quantum circuit creates a state that could result in any value, good or bad. Of course, we would prefer to create meaningful results. Therefore, we need a measure of “goodness.” That’s the purpose of the assess function.
def assess(problem, result):
avg = 0
sum_count = 0
for solution, count in result.items():
performance = 0
for i, j in problem.relations:
if solution[i] != solution[j]:
performance -= 1avg += performance * count
sum_count += count
return avg/sum_count
Given our problem, we calculate the performance of a result that we obtained from executing the quantum circuit. We look at the relations inside the problem definition and decrease (note lower is better here) the performance if the qubits representing this relation are not equal (solution[i] != solution[j]). Remember, a qubit either results in 0 or 1. So, solution[i] and solution[j] are either 0 or 1.
Now, with the ability to create circuits and assess their results, we can feed a classical optimization algorithm. This algorithm repeatedly evaluates different values and their results, based on which it moves towards values that promise better results.
from scipy.optimize import minimizedef optimize(f_params_to_problem):
return minimize(
# callable function
f_params_to_problem,
# initial guess on beta and gamma
[1.0, 1.0],
# optimization method
method='COBYLA')
So, let’s look at the structure of the problem. We used two characteristics of it: size and relations. So, let’s create a class to hold these data.
class Problem():
def __init__(self, nodes, relations):
self._nodes = nodes
self._relations = relations@property
def size(self) -> int:
return len(self._nodes)
@property
def relations(self) -> int:
return self._relations
Finally, we need to formulate the instance of our problem and feed it into the qaoa algorithm.
problem = Problem([0, 1, 2], [(0, 1), (1, 2)])
result = qaoa(
problem, optimize, assess, compute,
to_circuit, problem_circuit, ansatz_circuit
)
We define the problem to consist of three nodes (0, 1, 2) and a couple of relations. The nodes 0, 1 and 1, 2 are connected. The following listing denotes the output.
fun: -1.632
maxcv: 0.0
message: 'Optimization terminated successfully.'
nfev: 32
status: 1
success: True
x: array([1.05618646, 2.28854173])
The nfev denotes the number of iterations. And most importantly, x represents the params values that produced the best results.
To see what these values mean, we feed these values back into the circuit and look at the result.
from qiskit.visualization import plot_histogramplot_histogram(compute(to_circuit(
problem, result.x, problem_circuit, ansatz_circuit
)))
The output shows that two solutions occur more frequently: 010 and 101. So, these denote the solution to the problem specified.
When we look back into assess function, we see that we value each relation as -1 if the two connected nodes have different values. Further, we defined 0, 1 and 1, 2 to be connected.
Thus, the best solutions are those where these connected nodes have different values. And these are 010 and 101.
This problem is known as Max-Cut. It is the same problem solved in Qiskit’s example and could be considered the “Hello World” of combinatorial optimization.
This post explains the essential parts of the Quantum Approximate Optimization Algorithm (QAOA). Even though it is neither the first nor the only explanation, it does not require you to study mathematics first.
A non-mathematical explanation has quite a few advantages.
- It is much more accessible to most of us.
- It is hands-on. We directly solved a problem with it.
- You can see how the parts of the algorithm fit together.
Source link
