General Combinatorial Problems

The most general way to specify a combinatorial problem is by explicitly declaring boolean variables (Var) and clauses (Clause) combining these variables. This is achieved via the qat.opt.CombinatorialProblem class. While Ising and QUBO effectively accept only up to two-variable terms, one can define clauses in CombinatorialProblem with as many variables as desired. Here is an example of encoding a simple instance of the famous 3-SAT NP-hard problem:

from qat.opt import CombinatorialProblem

# Create a problem
comb_prob = CombinatorialProblem("3-SAT")

# Declare five variables
x0, x1, x2, x3, x4 = comb_prob.new_vars(5)

# Add (weighted) clauses between variables - for 3-SAT they will only contain <= 3 variables
comb_prob.add_clause( x0 &  x2 ^ ~x3 , weight=0.75)
comb_prob.add_clause(~x1 ^  x3 ^  x4 , weight=1.12)
comb_prob.add_clause( x4 & (x0 ^ ~x1), weight=0.86)

print(comb_prob, "\n")

# Can translate to an Observable for a gate-based manipulation
comb_prob_obs = comb_prob.get_observable()
print("As Observable:")
print(comb_prob_obs)

3-SAT:
 5 variables, 3 clauses 

As Observable:
1.1500000000000001 * I^5 +
0.1875 * (Z|[3]) +
0.1875 * (ZZ|[0, 3]) +
0.1875 * (ZZ|[2, 3]) +
-0.1875 * (ZZZ|[0, 2, 3]) +
0.56 * (ZZZ|[1, 3, 4]) +
-0.215 * (Z|[4]) +
0.215 * (ZZ|[0, 1]) +
-0.215 * (ZZZ|[0, 1, 4])

Note

  • Only for the case of no more than two variables per clause, a translation to the Ising and QUBO formulations is available (via the to_ising() and to_qubo() methods) and hence can be solved with Simulated Annealing (SA).

  • However, Combinatorial problems with more than 2-variable clauses can still be translated to a gate-based Observable (as exemplified above) and e.g. solved via the Quantum Approximate Optimization Algorithm (QAOA) as we describe in the Combinatorial Optimization section.