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 a terms Observable for a gate-based or analog manipulation
comb_prob_obs = comb_prob.get_observable("terms")
print("As terms Observable:")
print(comb_prob_obs)

# If the problem had only two variables, one could also translate to an
# ising Observable for an annealing manipulation
# comb_prob_obs = comb_prob.get_observable("ising")

3-SAT:
 5 variables, 3 clauses 

As terms 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