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, Graph Colouring, Number Partitioning, etc. could be easily formulated in these ways using the Qaptiva 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.
Constrained Graph Problems
A graph problem is constrained when the output solution needs to obey some conditions in order to be valid. For example, Graph Colouring requires that every two nodes connected by an edge are coloured differently - 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.
Other problems
Some problems are more numbers-oriented, like Number Partitioning and Binary Integer Linear Programming (BILP). These also belong to NP-hard and can be solved via Simulated Quantum Annealing (SQA).
For all the problems above we provide a set of fine tuned parameters which SQAQPU 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.
Simulated Quantum Annealing Benchmarking and Performance
To solve each of the NP problems with Simulated Quantum Annealing (SQA) we need to feed the
solver in SQAQPU with parameters tailored for the specific problem. We provide such fine tuned parameters for
a given set of instances for each problem class. They can be accessed from the get_best_parameters method of the respective problem class.
Below, we present the benchmark sources and the performances we obtain with the parameters found. We also show the range of spins of these 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:
Benchmarks: 9 planar and random graphs from the Gset benchmark dataset
Others: > 20 random trees
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:
Benchmarks: 27 differently generated graphs from the BHOSLIB, DIMACS and Clique benchmark datasets
Others: 5 random graphs
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:
Benchmarks: 21 random graphs from the BHOSLIB and OEIS benchmark datasets
Others: 5 random graphs
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