Introduction¶

An instrinsic feature of all NP problems is that they can be formulated as minimization or maximization problems, i.e. with a cost function. At the same time finding the lowest energy of a physical system, represented by a cost Hamiltonian, is also a minimization problem.

Due to this intimate relation, we can represent the cost function of an NP problem by a cost Hamiltonian. Such a Hamiltonian $H$, either in an Ising or QUBO form (see below) has two important properties:

  1. We can encode the solution of our problem in its ground state (which is the one of minimum energy).

  2. We can bring $H$ to this minimum energy by a heuristic Simulated Annealer (SA).

This is where Qaptiva HPC comes in $-$ it is equipped with tools for performing SA on whatever Hamiltonian, provided it is formulated as Ising or QUBO. Hence, each of the NP problems can be solved in this way.

The QLM has an even more powerful solver for Simulated Quantum Annealing (SQA). It has been tested on numerous benchmarks for the NP problems supported and produces results quality $>98\%$ on most instances. Please refer to the documentation for details.

Ising formulation¶

Ising problems are represented by a cost Hamiltonian of the following form:

$$ \displaystyle \large H = - \sum_{i,j \neq i}^{n} J_{ij}s_{i}s_{j} - \sum_{i=1}^{n} h_{i}s_{i} - E_{I}$$

where $J$ is the coupling constant, i.e. $J_{ij}$ is the interaction strength between spins $s_i$ and $s_j$, $h$ is the transverse magnetic field acting on all spins. $E_{I}$ is the Ising energy offset. For each of the $n$ spins $s_i \in \{1, -1\}$.

The variety in problems we can encode comes from the choice of $h_i$ and $J_{ij}$. For any given problem, our aim is to pick $h$ and $J$ such that only one particular combination of spin values $(s_1, s_2, \dots, s_n)$ will make $H$ lowest. And this configuration will encode the solution of our problem in a similar way binary numbers encode decimals, $(11001)_2 = (25)_{10}$ for example.

QUBO formulation¶

A Quadratic Unconstrained Binary Optimization (QUBO) problem can be represented by a cost Hamiltonian given by:

$$ \displaystyle \large H = - \sum_{i,j=1}^{n} Q_{ij}x_{i}x_{j} - E_{Q}$$

where $Q_{ij}$ serves as the equivalent of interaction strength between the binary variables $x_i, x_j \in \{1,0\}$ and $E_{Q}$ is the QUBO offset energy. The diagonal terms $Q_{ii}$ play a role similar to that of the magnetic field $h$ in the Ising formulation.

This time it is the choice of $Q$ that allows the expression of a large variety of problems. And analogously to Ising, we would want to choose $Q_{ij}$ such that it encodes all the properties of the problem of interest. Furthermore, there should be only one combination of binary values $(x_1, x_2, \dots, x_n)$ that makes $H$ the smallest possible.

Solving NP problems on Qaptiva HPC¶

A list of the currently supported NP problems could be found in the Overview, along with a notebook for each problem.

For each of the notebooks, we are first presented with the cost Hamiltonian to be minimized. The user can then encode a problem instance in this Hamiltonian form by calling one of the in-build classes: a Max Cut with MaxCut by providing a networkx graph, Number Partitioning by calling NumberPartitioning with a numpy.array() of numbers, etc.

Afterwards, the problems can be lead to a solution in two different ways:

Quantum Approximate Optimization Algorithm (QAOA)¶

  1. The QAOA variational ansätz is created with the cost function of the problem, and a variational job is sent to thePyLinalg QPU to determine the optimal parameters of the variational ansätz.

  2. The optimal parameters that are found are applied into the cost Hamiltonian, and another sampling job is executed to find the most probable states of the distribution corresponding to the optimized QAOA parameters.

Simulated Annealing (SA)¶

  1. Via the method to_job() we then create a job from the problem, ready to run on SimulatedAnnealing $-$ a class wrapped with a Quantum Processing Unit (QPU) interface. After specifying a temperature schedule for the anneling, such a QPU can be created.

  2. The job is submitted via the .submit() method of the QPU. A Result is returned, from which we extract the spin configuration for the lowest energy found Hamiltonian.

  3. We are then presented with problem-specific functions to decode the solution in a user-friendly format and to examine its quality and validity.

The whole QLM is based around sending jobs to a large variety of QPUs so if one were to switch to the full version of the software, one would have a head start in making use of its capabilities.