qatopt: representation and encoding of combinatorial problems, QAOA¶
This section describes how to define and solve combinatorial problems using myQLM tools.
Declaring and manipulating combinatorial problems¶
The most generic class used to describe combinatorial problems is the qat.opt.CombinatorialProblem
class.
It provides a simple interface to declare boolean variables and clauses, and ways to turn abstract problems into Job
or objects that can be fed to solvers.
In the (quite common case) where the problem’s clauses only involve at most two variables at a time (QUBO), we also provide a couple of optimized classes to describe the problem
directly in terms of Ising coupling matrix or QUBO \(Q\) matrix (see below).
Backandforth translations are avaible between the three problem classes using the to_XXX
methods.
Generic combinatorial optimization¶

class
qat.opt.
CombinatorialProblem
¶ Basic interface to describe a combinatorial optimization problem.
The problem declaration is done via methods
new_var()
(ornew_vars()
to declare arrays) andadd_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 * (ZZ[0, 1]) + 0.125 * (Z[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 objectweight (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

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_ising
()¶ Translates the problem into an Ising problem. Might raise an exception if the problem is not quadratic.
 Returns
an Ising object
 Return type
Clauses (Clause
) are declared by combining variables (Var
). The cost Hamiltonian extraction is handled by the
(Clause
) class. The final cost Hamiltonian consists of the weighted sum of the cost Hamiltonian of its clauses.

class
qat.opt.boolexpr.
Clause
¶ Class representing a boolean clause (boolean formula).
Clauses are trees whose leaves are
Var
objects and internal nodes are labelled by boolean operators (&, , ^, ~).Clauses are meant to be built either using the .and_clause, .or_clause, .xor_clause, neg_clause static methods, or via boolean operators overloading:
 Parameters
operator (str) – the operator (in [“&”, “”, “^”, “~”])
arity (int) – the arity of the operator
*children (
Clause
) – the subclauses

get_observable
()¶ Returns a boolean valued diagonal cost observable matching the evaluation of the clause.
The cost observable is built by induction:
\(H(A \wedge B) = H(A) H(B)\)
\(H(A \vee B) = H(A) + H(B)  H(A) H(B)\)
\(H(A \oplus B) = H(A) + H(B)  2 H(A) H(B)\)
\(H(\neg A) = 1  H(A)\)
\(H(v) = (1  \sigma_z^v)/2\)
Consequently: the resulting Hamiltonian is {0, 1} valued and has as 1eigenstates the states that satisfy the clause.
The variable class is quite simple and overloads logical operators to closely interact with the Clause class:

class
qat.opt.boolexpr.
Var
¶ Simple class for boolean variables

index
¶ the variable index (unique identifier)
 Type
int
 Parameters
index (int) – the variable index

get_observable
()¶ Returns a boolean valued diagonal cost observable matching the evaluation of the variable: \((1  \sigma_z^i) / 2\) where \(i\) is the index of the variable.
The observable will act upon self.index + 1 qubits.

get_variables
()¶ Returns a singleton with the index of the variable

Quadratic problems: QUBO and Ising¶

class
qat.opt.
QUBO
¶ Class representing Quadratic Unconstrained Binary Optimization problems.
The class allows for the representation of a problem as QUBO  by providing with a \(Q\) matrix and a QUBO offset energy \(E_Q\), both of which coming from the respective Hamiltonian encoding,
\[H =  x^T Q x  E_Q\]where \(x\) is the vector of binary values \(\{0,1\}\) we look for, such that \(H\) is minimum.
The class can also translate from a QUBO problem to an Ising problem via
to_ising()
by returning an Ising object.QUBO problems can be translated to a
CombinatorialProblem
object viato_combinatorial_problem()
.This class also inherits from the
CircuitGenerator
class which allows to construct QAOAAnsätze. Parameters
Q (2D numpy array) – an array representing the \(Q\) matrix from the Hamiltonian of the problem
offset_q (optional, double) – the value of the QUBO offset energy in the Hamiltonian of the problem

get_best_parameters
()¶ This method returns a dictionary with the best found parameters (after benchmarking) for simulated quantum annealing (SQA) of the respective QUBO problem. SQA is available in QLM, but the temperature parameters temp_max and temp_min could also be used for simulated annealing (SA), available in myQLM.
The method should be called from one of the child problem classes (e.g. GraphColouring, VertexCover, etc.) and not directly from the parent QUBO class as this will raise an exception.

get_observable
()¶ Returns a cost Hamiltonian for the problem.
 Returns
an Ising Hamiltonian encoding the problem
 Return type

get_q_and_offset
()¶ This method returns the \(Q\) matrix and QUBO energy offset, which define the QUBO object.
 Returns
2element tuple containing
Q (2D numpy array)  an array representing the \(Q\) matrix from the Hamiltonian of the problem
offset_q (double)  the value of the QUBO offset energy in the Hamiltonian of the problem

to_combinatorial_problem
()¶ Translates the QUBO problem into a combinatorial problem.
 Returns
a combinatorial problem instance
 Return type

to_ising
()¶ Translates the QUBO problem into an Ising problem over spins.
 Returns
an Ising instance
 Return type

to_job
(gamma_t=None, tmax=1.0, **kwargs)¶ Returns a Job for the problem  ready to run on a QPU for simulated annealing (SA) or simulated quantum anealing (SQA). The second one comes in the QLM.
 Parameters:
tmax (float, optional)  time duration of the annealing. Default is 1.
gamma_t (
ArithExpression
, SQA only)  a function specifying the time dependence of Gamma. It should be produced using the variable ‘t’ created by the classVariable
.
 Returns
a ready to run Job for the problem
 Return type

class
qat.opt.
Ising
¶ Class representing Ising problems.
The class allows for the representation of a problem in the Ising framework  by providing with a coupling matrix \(J\), magnetic field \(h\) and an Ising offset energy \(E_I\), all of which coming from the respective Hamiltonian encoding,
\[H =  s^T J s  h^T s  E_I\]where \(s\) is the spin vector we look for with values \(\{1,1\}\), such that \(H\) is minimum.
The class can also translate from an Ising problem to a QUBO problem through
to_qubo()
by returning aQUBO
object.Ising problems can be translated to a
CombinatorialProblem
object viato_combinatorial_problem()
.Similarly to QUBO and CombinatorialProblem, this class inherits from the
CircuitGenerator
class, thus is able to generate QAOAAnsätze. Parameters
J (2D numpy array) – an array with the coupling between each two spins  it represents the \(J\) matrix from the Hamiltonian of the problem
h (1D numpy array) – an array with the magnetic field acting on each of the spins, coming from the Hamiltonian of the problem
offset_i (optional, double) – the value of the Ising offset energy in the respective Hamiltonian

get_best_parameters
()¶ This method returns a dictionary with the best found parameters (after benchmarking) for simulated quantum annealing (SQA) of the respective Ising problem. SQA is available in QLM, but the temperature parameters temp_max and temp_min could also be used for simulated annealing (SA), available in myQLM.
The method should be called from one of the child problem classes (e.g. MaxCut, NumberPartitioning, etc.) and not directly from the parent Ising class as this will raise an exception.

get_j_h_and_offset
()¶ This method returns the \(J\) coupling matrix, the magnetic field \(h\) and Ising energy offset, which define the Ising object.
 Returns
3element tuple containing
J (2D numpy array)  an array with the coupling between each two spins  it represents the \(J\) matrix from the Hamiltonian of the problem
h (1D numpy array)  an array with the magnetic field acting on each of the spins, coming from the Hamiltonian of the problem
offset_i (double)  the value of the Ising offset energy in the respective Hamiltonian

get_observable
()¶ Returns a cost Hamiltonian for the problem.
 Returns
an Ising Hamiltonian encoding the problem
 Return type

to_combinatorial_problem
()¶ Translates the Ising problem into a CombinatorialProblem.
 Returns
a combinatorial problem instance
 Return type

to_job
(gamma_t=None, tmax=1.0, **kwargs)¶ Returns a Job for the problem  ready to run on a QPU for simulated annealing (SA) or simulated quantum anealing (SQA). The second one comes in the QLM.
 Parameters:
tmax (float, optional)  time duration of the annealing. Default is 1.
gamma_t (
ArithExpression
, SQA only)  a function specifying the time dependence of Gamma. It should be produced using the variable ‘t’ created by the classVariable
.
 Returns
a ready to run Job for the problem
 Return type
Generating the QAOA Ansatz¶
The Quantum Approximate Optimization Algorithms is a heuristics to design variational Ansätze for combinatorial optimization. It is inspired from the digitalization of an analog evolution using a linear ramp, starting from a simple initial Hamiltonian \(H_0 =  \sum_i \sigma_x^i\) to a diagonal Hamiltonian whose ground state encodes the solution to our problem. This digitalization leads to a layered parametrized quantum circuit consisting of entangling layers sperated by collective \(R_X\) rotations.
QAOA Ansätze are usually parametrized by a depth parameter specifying the number of alternating layers.
It is possible to directly generate ready to run QAOA jobs (containing an Ansatz and the target Hamiltonian) from an instance
of qat.opt.CombinatorialProblem
/qat.opt.QUBO
/qat.opt.Ising
instance via the following interface:

class
qat.opt.circuit_generator.
CircuitGenerator
¶ Class for circuit generation interface from a diagonal observable.

qaoa_ansatz
(depth, cnots=True, strategy='coloring', to_circ_args=None, **kwargs)¶ Generates a QAOA Ansatz 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 manyqubits 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 qlm job, ready to run
 Return type

The qat.vsolve.ansatz.AnsatzFactory
provides a recipe to produce such a variational circuits from a target Hamiltonian.

class
qat.vsolve.ansatz.
AnsatzFactory
¶ This class regroups the implementation all the different Ansätze available in the QLM.

static
qaoa_circuit
(observable, depth, strategy='default', cnots=True, **to_circ_args)¶ Generates a QAOA Ansatz from an observable and an Ansatz depth
Example
from qat.core import Observable, Term from qat.vsolve.ansatz import AnsatzFactory line_obs = Observable(10) for i in range(9): line_obs.add_term(Term(1., "ZZ", [i, i+1])) ansatz_with_cnots = AnsatzFactory.qaoa_circuit(line_obs, 3) print("The Ansatz has {} gates".format(len(ansatz_with_cnots.ops))) ansatz_with_rzz = AnsatzFactory.qaoa_circuit(line_obs, 3, cnots=False) print("The Ansatz has {} gates".format(len(ansatz_with_rzz.ops)))
The Ansatz has 121 gates The Ansatz has 67 gates
The synthesis strategy may influence the depth of the circuit:
def depth(circuit): ''' Computes the depth of a circuit ''' slices = [set()] for op in circuit: qbits = op.qbits insert_in = None for index, slic in enumerate(reversed(slices)): if all(qb not in slic for qb in qbits): continue insert_in = index break if insert_in is None: for qb in qbits: slices[0].add(qb) elif insert_in == 0: slices.append(set(qbits)) else: for qb in qbits: slices[len(slices)  insert_in].add(qb) return len(slices) from qat.core import Observable, Term from qat.vsolve.ansatz import AnsatzFactory line_obs = Observable(10) for i in range(9): line_obs.add_term(Term(1., "ZZ", [i, i+1])) ansatz_default = AnsatzFactory.qaoa_circuit(line_obs, 3, strategy="default") print("The Ansatz has depth {}".format(depth(ansatz_default))) ansatz_coloring = AnsatzFactory.qaoa_circuit(line_obs, 3, strategy="coloring") print("The Ansatz has depth {}".format(depth(ansatz_coloring)))
The Ansatz has depth 43 The Ansatz has depth 22
When considering QAOA instances with large Clauses (i.e clauses with more than 2 variables), the “gray_synth” strategy can often remove lots of CNOTS:
def cnot_count(circuit): ''' count cnots in a circuit ''' return sum(1 if name == "CNOT" else 0 for name, args, qbits in circuit.iterate_simple()) from qat.core import Observable, Term from qat.vsolve.ansatz import AnsatzFactory n = 5 line_obs = Observable(n) for i in range(n  2): line_obs.add_term(Term(1., "ZZZ", [i, i+1, i+2])) ansatz_default = AnsatzFactory.qaoa_circuit(line_obs, 3, strategy="default") ansatz_gray_synth = AnsatzFactory.qaoa_circuit(line_obs, 3, strategy="gray_synth") print("Cnot count in default:", cnot_count(ansatz_default)) print("Cnot count in gray synth:", cnot_count(ansatz_gray_synth))
Cnot count in default: 36 Cnot count in gray synth: 24
Synthesis strategies:
default: uses the default term ordering provided by the input observable
coloring: orders terms using a graph coloring technique in order to reduce circuit depth
gray_synth: uses Amy et al GraySynth algorithm to synthesize the entangling layer. This might help in reducing the overall CNOT count.
 Parameters
observable (
Observable
) – some diagonal observabledepth (int) – the depth of the Ansatz
strategy (str) – the strategy to adopt to generate the circuit.
cnots (optional, bool) – if set to True, the generator will onlt use CNOT gates as entangling gates. Default to True. This argument is ignored for some strategies.
**to_circ_args – arguments passed to the to_circ method

static
Encoding NPhard Problems¶
We present here classes for encoding some of the famous NP problems. An instrinsic feature of these problems is that they can be formulated as minimization or maximization problems, i.e. with a cost function. At the same time finding the lowest energy of a physical system, represented by a cost Hamiltonian, is also a minimization problem. Therefore, we can represent the cost function of an NP problem by a cost Hamiltonian. Such a Hamiltonian, given in an Ising form can then be annealed using Simulated Annealing (SA).
Furthermore, problems formulated as Quadratic Unconstrained Binary Optimisation (QUBO), can also be annealed, since we can translate them to Ising via our to_ising()
method.
Note
The Simulated Quantum Annealing is not available in myQLM. QUBO and Ising problems can still be used to construct QAOA Ansätze using the .qaoa_ansatz method or solved via Simulated Annealing.
Unconstrained Graph Problems¶
Max cut¶

class
qat.opt.max_cut.
MaxCut
¶ Specialization of the
Ising
class for Max Cut.This class allows for the encoding of a Max Cut problem for a given graph. The method
produce_j_h_and_offset()
is automatically called. It calculates the coupling matrix \(J\), magnetic field \(h\) and Ising energy offset corresponding to the Hamiltonian representation of the problem, as described in the reference. These are stored in the parent classIsing
and would be needed if one wishes to solve the problem through Simulated Annealing (SA), for instance. Reference
import networkx as nx from qat.opt import MaxCut graph = nx.full_rary_tree(2, 2**8) maxcut = MaxCut(graph) print("To anneal the problem, the solver would need " + str(len(graph.nodes())) + " spins.")
To anneal the problem, the solver would need 256 spins.
 Parameters
graph (networkx.Graph) – a networkx graph

get_best_parameters
()¶ This method returns a dictionary with the best found parameters (after benchmarking) for simulated quantum annealing (SQA), available in the QLM. However, the temperature parameters could also be used for simulated annealing (SA).
 Returns
6key dictionary containing
n_monte_carlo_updates (int)  the number of Monte Carlo updates
n_trotters (int)  the number of “classical replicas” or “Trotter replicas”
gamma_max (double)  the starting magnetic field
gamma_min (double)  the final magnetic field
temp_max (double)  the starting temperature
temp_min (double)  the final temperature

qat.opt.max_cut.
produce_j_h_and_offset
(graph)¶ Returns the \(J\) coupling matrix of the problem, along with the magnetic field \(h\) and the Ising energy offset.
 Parameters
graph (networkx.Graph) – a networkx graph
Graph Partitioning¶

class
qat.opt.graph_partitioning.
GraphPartitioning
¶ Specialization of the
Ising
class for Graph Partitioning.This class allows for the encoding of a Graph Partitioning problem for a given graph. The method
produce_j_h_and_offset()
is automatically called. It computes the coupling matrix \(J\), magnetic field \(h\) and Ising energy offset corresponding to the Hamiltonian representation of the problem, as described in the reference. These are stored in the parent classIsing
and would be needed if one wishes to solve the problem through Simulated Annealing (SA), for instance.For right encoding we need \(\frac { A } { B } \geq \frac { min(2D, N) } { 8 }\) with \(D\)  the maximal degree of a node in the graph and \(N\)  the number of nodes.
import numpy as np import networkx as nx from qat.opt import GraphPartitioning graph = nx.Graph() graph.add_nodes_from(np.arange(10)) graph.add_edges_from([(0,1), (0,4), (0,6), (1,2), (1,4), (1,7), (2,3), (2,5), (2,8), (3,5), (3,9), (4,6), (4,7), (5,8), (5,9), (6,7), (7,8), (8,9)]) B = 2 A = 5 graph_partitioning_problem = GraphPartitioning(graph, A, B=B) print("To anneal the problem, the solver would need " + str(len(graph.nodes())) + " spins.")
To anneal the problem, the solver would need 10 spins.
 Parameters
graph (networkx.Graph) – a networkx graph
A (double) – a positive constant by which the terms inside \(H_A\) from \(H = H_A + H_B\) are multiplied. This equation comes from the Hamiltonian representation of the problem.
B (optional, double) – similar to \(A\), \(B\) is a positive factor for the \(H_B\) terms, default is 1

get_best_parameters
()¶ This method returns a dictionary with the best found parameters (after benchmarking) for simulated quantum annealing (SQA), available in the QLM. However, the temperature parameters could also be used for simulated annealing (SA).
 Returns
6key dictionary containing
n_monte_carlo_updates (int)  the number of Monte Carlo updates
n_trotters (int)  the number of “classical replicas” or “Trotter replicas”
gamma_max (double)  the starting magnetic field
gamma_min (double)  the final magnetic field
temp_max (double)  the starting temperature
temp_min (double)  the final temperature

qat.opt.graph_partitioning.
produce_j_h_and_offset
(graph, A, B=1)¶ Returns the \(J\) coupling matrix of the problem, along with the magnetic field \(h\) and the Ising energy offset. For right encoding we need \(\frac{A}{B} \geq \frac{min(2D, N)}{8}\) with \(D\)  the maximal degree of a node in the graph and \(N\)  the number of nodes.
 Parameters
graph (networkx.Graph) – a networkx graph
A (double) – a positive constant by which the terms inside \(H_A\) from \(H = H_A + H_B\) are multiplied. This equation comes from the Hamiltonian representation of the problem.
B (optional, double) – similar to \(A\), \(B\) is a positive factor for the \(H_B\) terms, default is 1
Constrained Graph Problems¶
Graph Colouring¶

class
qat.opt.graph_colouring.
GraphColouring
¶ Specialization of the
QUBO
class for Graph Colouring.This class allows for the encoding of a Graph Colouring problem for a given graph and a number of colours. The method
produce_q_and_offset()
is automatically called. It computes the \(Q\) matrix and QUBO energy offset corresponding to the Hamiltonian representation of the problem, as described in the reference. These are stored in the parent classQUBO
and would be needed if one wishes to solve the problem through Simulated Annealing (SA), for instance.import numpy as np import networkx as nx from qat.opt import GraphColouring graph = nx.Graph() graph.add_nodes_from(np.arange(4)) graph.add_edges_from([(0,1), (0,2), (1,2), (1,3), (2,3)]) number_of_colours = 3 graph_colouring_problem = GraphColouring(graph, number_of_colours) print("To anneal the problem, the solver would need " + str(len(graph.nodes()) * number_of_colours) + " spins.")
To anneal the problem, the solver would need 12 spins.
 Parameters
graph (networkx.Graph) – a networkx graph
number_of_colours (int) – the number of colours

get_best_parameters
()¶ This method returns a dictionary with the best found parameters (after benchmarking) for simulated quantum annealing (SQA), available in the QLM. However, the temperature parameters could also be used for simulated annealing (SA).
 Returns
6key dictionary containing
n_monte_carlo_updates (int)  the number of Monte Carlo updates
n_trotters (int)  the number of “classical replicas” or “Trotter replicas”
gamma_max (double)  the starting magnetic field
gamma_min (double)  the final magnetic field
temp_max (double)  the starting temperature
temp_min (double)  the final temperature

qat.opt.graph_colouring.
produce_q_and_offset
(graph, number_of_colours)¶ Returns the \(Q\) matrix and the offset energy of the problem.
 Parameters
graph (networkx.Graph) – a networkx graph
number_of_colours (int) – the number of colours
KClique¶

class
qat.opt.k_clique.
KClique
¶ Specialization of the
QUBO
class for KClique.This class allows for the encoding of a KClique problem for a given graph and positive factors \(K, A, B\). The method
produce_q_and_offset()
is automatically called. It computes the \(Q\) matrix and QUBO energy offset corresponding to the Hamiltonian representation of the problem, as described in the reference. These are stored in the parent classQUBO
and would be needed if one wishes to solve the problem through Simulated Annealing (SA), for instance.For a right encoding, one should ensure that \(A > B * K\).
import numpy as np import networkx as nx from qat.opt import KClique graph = nx.Graph() graph.add_nodes_from(np.arange(6)) graph.add_edges_from([(0,1), (0,2), (0,3), (0,4), (0,5), (1,2), (1,5)]) B = 1 K = 3 A = B*K + 1 k_clique_problem = KClique(graph, K, A, B=B) print("To anneal the problem, the solver would need " + str(len(graph.nodes())) + " spins.")
To anneal the problem, the solver would need 6 spins.
 Parameters
graph (networkx.Graph) – a networkx graph
K (int) – the size of the clique
A (double) – a positive constant by which the terms inside \(H_A\) from \(H = H_A + H_B\) are multiplied. This equation comes from the Hamiltonian representation of the problem.
B (optional, double) – similar to \(A\), \(B\) is a positive factor for the \(H_B\) terms, default is 1

get_best_parameters
()¶ This method returns a dictionary with the best found parameters (after benchmarking) for simulated quantum annealing (SQA), available in the QLM. However, the temperature parameters could also be used for simulated annealing (SA).
 Returns
6key dictionary containing
n_monte_carlo_updates (int)  the number of Monte Carlo updates
n_trotters (int)  the number of “classical replicas” or “Trotter replicas”
gamma_max (double)  the starting magnetic field
gamma_min (double)  the final magnetic field
temp_max (double)  the starting temperature
temp_min (double)  the final temperature

qat.opt.k_clique.
produce_q_and_offset
(graph, K, A, B=1)¶ Returns the \(Q\) matrix and the offset energy of the problem. The constant \(A\) should be bigger than \(K*B\) for a right encoding. They are also all positive.
 Parameters
graph (networkx.Graph) – a networkx graph
K (int) – the size of the clique
A (double) – a positive constant by which the terms inside \(H_A\) from \(H = H_A + H_B\) are multiplied. This equation comes from the Hamiltonian representation of the problem.
B (optional, double) – similar to \(A\), \(B\) is a positive factor for the \(H_B\) terms, default is 1
Vertex Cover¶

class
qat.opt.vertex_cover.
VertexCover
¶ Specialization of the
QUBO
class for Vertex Cover.This class allows for the encoding of a Vertex Cover problem for a given graph and positive constants \(A\) and \(B\). The method
produce_q_and_offset()
is automatically called. It computes the \(Q\) matrix and QUBO energy offset corresponding to the Hamiltonian representation of the problem, as described in the reference. These are stored in the parent classQUBO
and would be needed if one wishes to solve the problem through Simulated Annealing (SA), for instance.For a right encoding, one should ensure that \(A > B\).
import numpy as np import networkx as nx from qat.opt import VertexCover graph = nx.Graph() graph.add_nodes_from(np.arange(6)) graph.add_edges_from([(0,1), (0,2), (0,3), (0,4), (0,5), (1,5)]) A = 2 B = 1 vertex_cover_problem = VertexCover(graph, A=A, B=B) print("To anneal the problem, the solver would need " + str(len(graph.nodes())) + " spins.")
To anneal the problem, the solver would need 6 spins.
 Parameters
graph (networkx.Graph) – a networkx graph
A (optional, double) – a positive constant by which the terms inside \(H_A\) from \(H = H_A + H_B\) are multiplied, default is 2. This equation comes from the Hamiltonian representation of the problem.
B (optional, double) – similar to \(A\), \(B\) is a positive factor for the \(H_B\) terms, default is 1

get_best_parameters
()¶ This method returns a dictionary with the best found parameters (after benchmarking) for simulated quantum annealing (SQA), available in the QLM. However, the temperature parameters could also be used for simulated annealing (SA).
 Returns
6key dictionary containing
n_monte_carlo_updates (int)  the number of Monte Carlo updates
n_trotters (int)  the number of “classical replicas” or “Trotter replicas”
gamma_max (double)  the starting magnetic field
gamma_min (double)  the final magnetic field
temp_max (double)  the starting temperature
temp_min (double)  the final temperature

qat.opt.vertex_cover.
produce_q_and_offset
(graph, A=2, B=1)¶ Returns the \(Q\) matrix and the offset energy of the problem. The constant \(A\) should be bigger than \(B\) for a right encoding. They are also both positive.
 Parameters
graph (networkx.Graph) – a networkx graph
A (optional, double) – a positive constant by which the terms inside \(H_A\) from \(H = H_A + H_B\) are multiplied, default is 2. This equation comes from the Hamiltonian representation of the problem.
B (optional, double) – similar to \(A\), \(B\) is a positive factor for the \(H_B\) terms, default is 1
Other problems¶
Number Partitioning¶

class
qat.opt.number_partitioning.
NumberPartitioning
¶ Specialization of the
Ising
class for Number Partitioning.This class allows for the encoding of a Number Partitioning problem for a given array of numbers. The method
produce_j_h_and_offset()
is automatically called. It computes the coupling matrix \(J\), magnetic field \(h\) and Ising energy offset corresponding to the Hamiltonian representation of the problem, as described in the reference. These are stored in the parent classIsing
and would be needed if one wishes to solve the problem through Simulated Annealing (SA), for instance.import numpy as np from qat.opt import NumberPartitioning array_of_numbers_size = np.random.randint(low=1, high=10000, size=1)[0] array_of_numbers = np.random.randint(low=1, high=10000, size=array_of_numbers_size) number_partitioning_problem = NumberPartitioning(array_of_numbers) print("To anneal the problem, the solver would need " + str(array_of_numbers_size) + " spins.")
To anneal the problem, the solver would need 4131 spins.
 Parameters
numbers_array (1D numpy array) – an array with all the numbers we want to partition

get_best_parameters
()¶ This method returns a dictionary with the best found parameters (after benchmarking) for simulated quantum annealing (SQA), available in the QLM. However, the temperature parameters could also be used for simulated annealing (SA).
 Returns
6key dictionary containing
n_monte_carlo_updates (int)  the number of Monte Carlo updates
n_trotters (int)  the number of “classical replicas” or “Trotter replicas”
gamma_max (double)  the starting magnetic field
gamma_min (double)  the final magnetic field
temp_max (double)  the starting temperature
temp_min (double)  the final temperature

qat.opt.number_partitioning.
produce_j_h_and_offset
(array_of_numbers)¶ Returns the \(J\) coupling matrix of the problem, along with the magnetic field \(h\) and the Ising energy offset.
 Parameters
numbers_array (1D numpy array) – an array with all the numbers we want to partition
Binary Integer Linear Programming¶

class
qat.opt.binary_linear_integer_programming.
BILP
¶ Specialization of the
QUBO
class for Binary Integer Linear Programming (BILP).This class allows for the encoding of a BILP problem from a given matrix \(S\), vectors \(b\) and \(c\) and positive constants \(A\) and \(B\). The aim is to maximise \(c * x\) subject to \(x\) obeying \(S * x = b\). The method
produce_q_and_offset()
is automatically called. It computes the \(Q\) matrix and QUBO energy offset corresponding to the Hamiltonian representation of the problem, as described in the reference. These are stored in the parent classQUBO
and would be needed if one wishes to solve the problem through Simulated Annealing (SA), for instance.For a right encoding, one should ensure that \(A \gg B\) and \(A > 0, B > 0\).
import numpy as np from qat.opt import BILP c = np.array([0,1,1,1]) S = np.array([[1,0,1,1], [0,1,0,1]]) b = np.array([1,1]) B = 1 A = 10*B bilp_problem = BILP(c, S, b, A, B=B) print("To anneal the problem, the solver would need " + str(len(c)) + " spins.")
To anneal the problem, the solver would need 4 spins.
 Parameters
c (1D numpy array of size N) – a specified vector \(c\). We want to maximize \(c * x\).
S (2D numpy array of size m*N) – the matrix, for which \(S * x = b\). This equation is our constraint.
b (1D numpy array of size m) – a specified vector \(b\) obeying the constraint \(S * x = b\)
A (double) – a positive constant by which the terms inside \(H_A\) from \(H = H_A + H_B\) are multiplied. This equation comes from the Hamiltonian representation of the problem.
B (optional, double) – similar to \(A\), \(B\) is a positive factor for the \(H_B\) terms, default is 1

get_best_parameters
()¶ This method returns a dictionary with the best found parameters (after benchmarking) for simulated quantum annealing (SQA), available in the QLM. However, the temperature parameters could also be used for simulated annealing (SA).
 Returns
6key dictionary containing
n_monte_carlo_updates (int)  the number of Monte Carlo updates
n_trotters (int)  the number of “classical replicas” or “Trotter replicas”
gamma_max (double)  the starting magnetic field
gamma_min (double)  the final magnetic field
temp_max (double)  the starting temperature
temp_min (double)  the final temperature

qat.opt.binary_linear_integer_programming.
produce_q_and_offset
(c, S, b, A, B=1)¶ Returns the \(Q\) matrix and the offset energy of the problem. For right encoding \(A \gg B\) and \(A > 0, B > 0\).
 Parameters
c (1D numpy array of size N) – a specified vector \(c\). We want to maximize \(c * x\).
S (2D numpy array of size m*N) – the matrix, for which \(S * x = b\). This equation is our constraint.
b (1D numpy array of size m) – a specified vector \(b\) obeying the constraint \(S * x = b\)
A (double) – a positive constant by which the terms inside \(H_A\) from \(H = H_A + H_B\) are multiplied. This equation comes from the Hamiltonian representation of the problem.
B (optional, double) – similar to \(A\), \(B\) is a positive factor for the \(H_B\) terms, default is 1