qat.opt.VertexCover

class qat.opt.VertexCover(graph, A=2, B=1, **kwargs)

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 class QUBO and would be needed if one wishes to solve the problem through Simulated Quantum Annealing (SQA) via the SQAQPU - see the Vertex Cover notebook. This QPU also requires a few additional parameters, the specification of which may vary the quality of the solution. We provide the initial parameters inspired by the problem through get_sqa_initial_parameters(), that can be further improved by fine-tuning..

For a right encoding, one should ensure that \(A > B\).

Reference:: “Ising formulations of many NP problems”, A. Lucas, 2014 - Section 4.3.

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

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 QUBO problem. If a ‘terms’ Observable is chosen, the QUBO problem will first be translated to a CombinatorialProblem.

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 proving 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

get_q_and_offset()

This method returns the \(Q\) matrix and QUBO energy offset, which define the QUBO object.

Returns:

2-element tuple containing

Q (2D numpy array) - a symmetric 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

get_sa_initial_parameters(**kwargs)

Compute initial parameters for Simulated Annealing (SA): temperature, number of annealing steps and shots. From the qubo formulation of the combinatorial problem, we sample random configurations and estimate an average energy fluctation produced initially, from which we choose a temperature to match an acceptance ratio for the initial Monte Carlo moves. T_total represent the time budget and is proportional to the number of Monte Carlo steps. This budget is split between number of annealing steps \(n_{steps}\) and number of sampling shots \(n_{shots}\), according to \(T_{ratio} = n_{shots}/n_{steps}\).

These parameters can be used with SQAQPU if the number of Trotter replicas is 1.

Returns a dictionary with parameter values.

Parameters:

T_total (int,optional) – Time budget expressed as number of annealing steps times the number of shots. By default is 8000.
T_ratio (float, optional) – The ratio used for sharing the time budget between number of steps and number of shots: where a and b are float. By default, T_ratio = 1/10.
initial_samples (int, optional) – number of random energy evaluations to derive the temperature. Default is 1000.
acceptance_ratio (float, optional) – target acceptance ratio for initial Monte Carlo moves when determining the initial temperature. Default is 0.15.

Returns:

dictionary of SA parameters: \(T_{max}\), \(T_{min}\), \(n_{shots}\), \(n_{steps}\) (with max schedule time \(t_{max}\) and total number of Monte Carlo moves \(n_{MC}\)).

Return type:

dict

get_sqa_initial_parameters(**kwargs)

Compute initial parameters for Simulated Quantum Annealing (SQA): gamma, temperature, number of annealing steps, and number of Trotter replicas. From the qubo formulation of the combinatorial problem, we sample random configurations and estimate an average energy fluctation produced initially by the initial Monte Carlo moves, from which we choose an effective temperature \(T^* = T imes n_{trotters}\) to match an acceptance ratio (set to 0.15 by default), where \(\Gamma\) is the temperature and \(n_{trotters}\) is the number of Trotter replicas, set by default to 10. The parameter \(\Gamma\) is chosen according as the maximum (or a percentile) of the on-site energies obtained from the Qubo matrix, to match the problem energy unit. \(T_{total}\) represents the time budget and is proportional to the number of individual shots \(n_{shots}\) multiplied by the number of annealing steps per shot \(n_{steps}\). This budget is split between number of annealing steps \(n_{steps}\) and number of sampling shots \(n_{shots}\), according to \(T_{ratio} = n_{shots}/n_{steps}\). Finally, we can combine the \(\Gamma\) schedule with a temperature schedule (like in classical Simulated Annealing) if combine_SA is set to True.

Returns a dictionary with parameter values.

Parameters:

T_total (int,optional) – Time budget expressed as number of annealing steps times the number of shots. By default is 8000.
T_ratio (float, optional) – The ratio used for sharing the time budget between number of steps and number of shots. Default is 1/10.
gamma_strategy (str, optional) – Strategy used for determining the transverse field \(\Gamma\). By default, the strategy is “max”, which evaluates the maximum energy scale per site from the qubo matrix values. Alternative strategy is “percentile”, that returns the n-th percentile of the local maximum energy scale.
percentile (float, optional) – the percentile to use for the gamma_strategy = “percentile”. Default is 90.
initial_samples (int, optional) – number of random energy evaluations to derive the effective temperature. Default is 1000.
acceptance_ratio (float, optional) – target acceptance ratio for initial Monte Carlo moves when determining the initial temperature.
combine_SA (bool, optional) – If True, the temperature is also decreased during the annealing. Default is True.

Returns:

dictionary of SQA parameters: \(\Gamma_{max}\), \(\Gamma_{min}\), \(T_{max}\), \(T_{min}\), \(n_{shots}\), \(n_{steps}\), \(n_{trotters}\) (with max schedule time \(t_{max}\) and total number of Monte Carlo moves \(n_{MC}\)).

Return type:

dict

parse_result(result, inverse=False)

Returns the approximated solution of the Vertex Cover problem from a list of samples

Parameters:: result (BatchResult) – BatchResult containing a list of samples

property q_matrix: The Q-matrix of the QUBO Hamiltonian as a symmetric numpy 2D array

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 QUBO 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

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.

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 QUBO problem to DWave’s Binary Quadratic Model from the library dimod.

Returns:: a BinaryQuadraticModel object
Return type:: BinaryQuadraticModel

to_combinatorial_problem()

Translates the QUBO problem into a combinatorial problem.

Returns:: a combinatorial problem instance
Return type:: CombinatorialProblem

to_ising()

Translates the QUBO problem into an Ising problem over spins.

Returns:: an Ising instance
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

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