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("terms")

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

aqo_job(tmax=None, mixing=None, **kwargs): Generates an Adiabatic Quantum Optimization (AQO) job performing a linear interpolation between an initial mixing Hamiltonian and the problem’s Hamiltonian.

classmethod decode_rydberg(job, result)

Returns the MWIS simulation result of the input graph.

Parameters

job (Job) – generated job
result (Result) – result of the simulation of the crossing lattice graph.

Returns

MWIS simulation result of the input graph.

Return type

Result

static decode_rydberg_meta_data(meta_data: dict, result)

Returns the MWIS simulation result of the input graph.

Parameters

meta_data (dict[str, str]) – generated job meta_data
result (Result) – result of the simulation of the crossing lattice graph

Returns

MWIS simulation result of the input graph

Return type

Result

get_observable(obs_type)

Returns an ising- or a terms-type of Observable from the CombinatorialProblem. For an ‘ising’ Observable, the Ising problem will first be translated to an Ising problem.

In the case of a ‘terms’ Observable, a diagonal cost Hamiltonian is generated. It associates 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 is flipped. This means that the “best” solution is always encoded in the ground state of the returned Hamiltonian.

Parameters

obs_type (string) –

The type of Observable to be returned: 'ising' or 'terms'.

'ising' observables can be used to create a Schedule (by also providing gamma_t if SQAQPU will be used) and consecutively produce a Job to be sent for Simulated Quantum Annealing.
'terms' observables can be used for gate-based quantum computations with a Circuit or analog quantum computations, also with a Schedule.

Returns

an Ising Observable or an Observable with terms representing the problem

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

qaoa_job(depth, cnots=True, strategy='coloring', to_circ_args=None, **kwargs)

Generates a QAOA Ansatz Job for gate-based computations using the cost observable returned by the abstract method get_observable.

Warning

When setting the cnots option to False, the circuit might make use of generalized many-qubits Z rotations. In that case, you might want to instantiate your variational plugins using a gate set that contains definition of these gates. If not, some matrices in the circuit structure will be missing and some QPUs may not be able to handle the circuit.

The following piece of code should allow you to link the correct gate set to a variational plugin:

from qat.plugins import ScipyMinimizePlugin
from qat.vsolve.ansatz import get_qaoa_gate_set

# This plugin will no be able to bind variables inside a
# job generated with cnot set to False!
my_plugin = ScipyMinimizePlugin()

# This plugin can now be used with job generated with the
# cnots option sets to False!
my_plugin = ScipyMinimizePlugin(gate_set=get_qaoa_gate_set())

Parameters

depth (int) – the depth of the Ansatz
strategy (str) – the strategy to adopt to generate the circuit. Possible strategies are “default” or “coloring”. The “coloring” strategy uses a greedy coloring heuristics to try to optimize the overall depth of the Ansatz. Default is “default” which synthesize the circuit without optimizing the term ordering.
cnots (optional, bool) – If set to True the Ansatz will only use CNOT gates. If set to False, some abstract gates will be used to generate collective pauli rotations, resulting in a lower gate count. Defaults to True.
**kwargs – optional arguments that will be transfered to the job’s constructor (e.g nbshots, etc).

Returns

a Qaptiva job, ready to run

Return type

Job

ryd_job(optimize=True, time_budget_sec=3, tmax=10, **kwargs)

Returns a ryd-type job for the problem - ready to run with the AnalogQPU

Parameters

optimize (bool) – if True, the node overhead will be reduced.
time_budget_sec (float) – time budget allocated for the core part of the optimization function.
tmax (float) – time duration of the adiabatic simulation.

Returns

a ryd-type job ready to run on an analog QPU.

Return type

Job

sqa_job(gamma_t=None, tmax=1.0, **kwargs)

Returns a sqa-type of Job for the problem - ready to run with SQAQPU. If the problem is not quadratic, it might raise an exception.

Parameters

tmax (float, optional) – time duration of the annealing. Default is 1.
gamma_t (ArithExpression, optional) – a function specifying the time dependence of Gamma. It should be produced using the variable ‘t’ created by the class Variable.

Returns

a ready to run sqa-type of Job for the problem

Return type

Job

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_job(job_type, *args, **kwargs)

A general method allowing the creation of an aqo-, qaoa- or sqa-type of Job from a problem description - ready to run on the respective QPU.

'aqo' is for Adiabatic Quantum Optimization (with analog QPUs). Internally, method aqo_job() is used to generate the job.
'qaoa' is for using the Quantum Approximate Optimization Algorithm (with gate-based QPUs). Internally, method qaoa_job() is used to generate the job.
'sqa' is for Simulated Quantum Annealing (with SQAQPU). Internally, method sqa_job() is used to generate the job.
'ryd' is for Rydberg (with AnalogQPU). Internally, method ryd_job() is used to generate the job.

Parameters

job_type (string) – The type of job to be returned: 'aqo', 'qaoa', 'sqa', or 'ryd'.
*args – additional arguments passed to aqo_job(), qaoa_job(), sqa_job(), or ryd_job().
**kwargs – additional keyword arguments passed to aqo_job(), qaoa_job(), sqa_job(), or ryd_job().

Returns

a ready to run Job for the respective type of problem

Return type

Job

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