qat.opt.CombinatorialProblem

class qat.opt.CombinatorialProblem(name=None, maximization=False, **kwargs)

Basic class to describe a combinatorial optimization problem.

The problem declaration is done via methods new_var() (or new_vars() to declare arrays) and add_clause().

from qat.opt import CombinatorialProblem

problem = CombinatorialProblem("MyProblem")
# Declare two fresh variables
var1, var2 = problem.new_vars(2)
# Add a new clause consisting of the logical AND of the two variables
problem.add_clause(var1 & var2)
# Add a new clause consisting of the XOR of the two variables
problem.add_clause(var1 ^ var2)

print(problem)

MyProblem:
 2 variables, 2 clauses

It is possible to add weights to the clauses:

from qat.opt import CombinatorialProblem

problem = CombinatorialProblem()
var1, var2 = problem.new_vars(2)
problem.add_clause(var1 & var2, weight=0.5)

print(problem)

Problem:
 2 variables, 1 clauses

A diagonal Hamiltonian encoding the cost function of the problem can be extracted using the get_observable() method.

from qat.opt import CombinatorialProblem

problem = CombinatorialProblem()
var1, var2 = problem.new_vars(2)
problem.add_clause(var1 & var2, weight=0.5)

obs = problem.get_observable()

print(obs)

0.125 * I^2 +
-0.125 * (Z|[0]) +
-0.125 * (Z|[1]) +
0.125 * (ZZ|[0, 1])

Finally, this class inherits from the CircuitGenerator class, which provides a method to directly generate variational Ansätze to try and minimize the energy of the cost Hamiltonian.

Parameters

name (optional, str) – a name to display when the problem is printed
maximization (optional, bool) – Used to specify that the problem is a maximization problem (i.e its cost function is the sum of its clauses). In practice, it will simply flip the sign of the generated cost Hamiltonian. Default to false.

add_clause(clause, weight=None)

Adds a new clause to the problem.

Parameters

clause (Clause) – a clause object
weight (optional, float) – optionally a weight (default to 1)

Returns

the problem itself

get_observable()

Generates a cost Hamiltonian for the problem.

The cost Hamiltonian is diagonal and associate to each bitstring \(|s\rangle\) an energy \(\sum_\alpha w_\alpha C_\alpha(s)\) where \(C_\alpha\) are the clauses of the problem, seen as \(\{0, 1\}\) valued functions and \(w_\alpha\) their corresponding weights.

This encoding is done recursively and is described in the documentation of the Clause class.

If the problem is specified as a maximization problem, the sign of the cost Hamiltonian if flipped. This means that the “best” solution is always encoded in the ground state of the returned Hamiltonian.

Returns: a cost Hamiltonian
Return type: Observable

new_var()

Returns a fresh variable

Returns: a fresh variable
Return type: Var

new_vars(nbvars)

Returns a list of fresh variables.

Parameters: nbvars (int) – the number of fresh variables to declare
Returns: a list of fresh variables of length nbvars
Return type: list

to_bqm()

Transforms a Combinatorial problem to DWave’s Binary Quadratic Model from the library dimod.

Returns: a BinaryQuadraticModel object
Return type: BinaryQuadraticModel

to_ising()

Translates the problem into an Ising problem. Might raise an exception if the problem is not quadratic.

Returns: an Ising object
Return type: Ising

to_qubo()

Translates the problem into a QUBO problem. Might raise an exception if the problem is not quadratic.

Returns: a QUBO object
Return type: QUBO