NP-hard problems

Among all the combinatorial problems, the ones with highest practical importance and repeated appearance are the NP-hard problems. Real quantum annealers have been dedicated to tackle such problems, when represented in an Ising or QUBO form (refer to Annealing programming and this notebook). Some of them, like Max Cut, Vertex Cover, Number Partitioning, etc. could be easily formulated in these ways using myQLM tools. A description of these problems can be found below and the respective helper classes for each problem are given in the API. An example notebook for each problem could be found in the overview.

Unconstrained Graph Problems

These problems concern graphs for which any output result is valid. In other words, any solution will obey the criteria for a right solution. However, this result may not be the most optimal.

Max Cut
Graph Partitioning

Constrained Graph Problems

A graph problem is constrained when the output solution needs to obey some conditions in order to be valid. For example, Vertex Cover requires that every edge is connected by at least one coloured node - so if the solution graph does not have this property, it is not valid. Therefore, we call constrained all problems with conditional correctness on their solution.

K-Clique
Vertex Cover

Other problems

Some problems are more numbers-oriented, like Number Partitioning, which also belongs to NP-hard and can be well solved via Simulated Annealing (SA).

Number Partitioning

For all the problems above we provide a set of fine tuned parameters which Simulated Quantum Annealing that is offered in the full Qaptiva Appliance would need. The solver was tested with various benchmarks and the respective performances were recorded. Along with the problem size and annealing times, the results are presented in the benchmarking section below.

Note

Many of these parameters showed overall good performances with Simulated Annealing as well.

Simulated Quantum Annealing Benchmarking and Performance

Although Simulated Quantum Annealing is only provided in the full Qaptiva Appliance, we present here its performance for some of the different NP problems to hint on its capabilities. Below are shown the benchmark sources, the range of spins for the problem instances, together with the average execution times.

  • Performance optimized: \(\frac {\text{number of Max Cut edges found}} {\text{best number of Max Cut edges}}\)

  • Problem instances:

  • Spin count: from 20 to 10 000

  • Performance: > 98%

  • Execution time: mostly < 1 sec and up to 5 seconds for 10 000 spins

  • Performance optimized: \(\frac {\text{number of edges with vertices of different colours}} {\text{number of all edges}}\)

  • Problem instances:

    • Benchmarks: 6 - random graphs and a Leighton graph from DIMACS Graphs

    • Others: 13 random graphs

  • Spin count: from 60 to 24 000

  • Performance: 88% for best colouring, 95% - 99% for a few more colours

  • Execution time: < 10 sec for up to 24 000 spins

  • Performance optimized: \(\frac {\text{number of edges in the subgraph found}} {\text{required number of edges for the subgraph to be complete}}\)

  • Problem instances:

  • Spin count: from 450 to 4000

  • Performance: > 98%

  • Execution time: mostly < 1 sec when below 4000 spins

  • Performance optimized: \(\frac {\text{best number of coloured nodes}} {\text{found number of coloured nodes}}\)

  • Problem instances:

  • Spin count: from 450 to 4000

  • Performance: > 98%

  • Execution time: mostly < 1 sec and up to 10 seconds for 4000 spins

  • Performance optimized: \(\frac {\text{sum of numbers in smaller sum subset}} {\text{sum of numbers in larger sum subset}}\)

  • Problem instances: > 30 random number sets of integer or real, non-repeating or repeating numbers

  • Spin count: from 20 to 40 000

  • Performance: > 99%

  • Execution time: from instantly to 15 sec for 40 000 spins