Optimization

Brute Force Minimization

Types

The brute-force minimization functions in Forge rely on custom types for problem specification, constraints, and results.

class qcware.types.optimization.PolynomialObjective(polynomial: Dict[Tuple[int, ...], int], num_variables: int, domain: Union[qcware.types.optimization.variable_types.Domain, str] = Domain.BOOLEAN, variable_name_mapping: Optional[Dict[int, str]] = None, validate_types: bool = True)

Integer-valued polynomial of binary variables with int coefficients.

Objects of this class specify polynomials of some number of binary variables with integer coefficients. “Binary variables” can either mean variables taking on the values 0 and 1 or variables taking on the values 1 and -1. The former a referred to as boolean variables and the latter are referred to as spin variables

Objects of this class are meant to be treated as objective functions for optimization. They do not know about constraints. Constraints can be specified separately using a Constraints object.

Polynomials are specified with a dict that specifies the coefficients for the polynomial. For example, suppose that we are interested in the polynomial of three boolean variables defined by:

p(x, y, z) = 12 x - 2 y z + x y z - 50

The three variables should be associated with the integers 0, 1, and 2. We choose the association x ~ 0, y ~ 1, and z ~ 2.

There are four terms in p. Consider the term -2yz. We can specify this term by matching the tuple (1, 2), which represents yz, with the coefficient -2. This can be encoded with an entry in a dict (1, 2): -2. Overall, p can be defined by:

{
    (): -50,
    (0,): 12,
    (1, 2): -2,
    (0, 1, 2): -50
}

The number of variables must be specified explicitly, even if it seems obvious how many variables there are. The reason for this is to allow for the possibility that there are more variables than appear explicitly in the polynomial. For example, the polynomial p(a, b) = 12 b might be mistaken for q(b) = 12 b.

polynomial

The polynomial is specified by a dict as described above. We only use tuples of int as keys and the range of ints must be from 0 to num_variables - 1. Values for the dict must be type int. This is because we are only treating integer-coefficient polynomials.

Type

Dict[Tuple[int, …], int]

variables

Set of ints representing the variables.

Type

Set[int]

num_variables

The number of variables for the polynomial. This number can be larger than the actual number of variables that appear in polynomial but it cannot be smaller.

Type

int

degree

The degree of the polynomial. This is not the mathematically correct degree. It is instead the length of the longest key in the polynomial dict or -inf in the case when the dict is {}. For example, the boolean PolynomialObjective {(1,): 12, (0, 1): 0} has mathematical degree 1 but the attribute degree is 2.

Type

Union[int, float]

domain

Specifies if variables take on boolean (0, 1) or spin (1, -1) values.

Type

qcware.types.optimization.variable_types.Domain

clone()

Make a copy of this PolynomialObjective.

compute_value(variable_values: dict, use_variable_names: bool = False)

Compute the value of this polynomial at a specified input.

pretty_str(include_domain: bool = True)

Make a string that presents the polynomial algebraically.

The names of variables can be controlled with the attribute variable_name_mapping.

Adapted from qubovert–thanks to Joseph T. Iosue.

qubovert(use_variable_names: bool = False)

Get a qubovert model describing this polynomial.

This method will return a qubovert PUBO or PUSO depending on the domain of the variables.

This method creates a cached qubovert object once it is called. TODO: This fact makes it particularly important that

PolynomialObjective is immutable. We should try to enforce this.

Parameters

use_variable_names – When True, the variables in the qubovert object will use the same string names as appear in the attribute variable_name_mapping.

qubovert_boolean()

Get a boolean qubovert model equivalent to this polynomial.

This produces a PUBOMatrix which is qubovert’s enumerated form of a PUBO (polynomial unconstrained boolean optimization). This transformation may change the variable ordering and for that reason we also return a mapping that can be used to recover the original variable identifiers.

qubovert_spin()

Get a spin qubovert model equivalent to this polynomial.

This produces a PUSOMatrix which is qubovert’s enumerated form of a PUSO (polynomial unconstrained spin optimization). This transformation may change the variable ordering and for that reason we also return a mapping that can be used to recover the original variable identifiers.

reduce_variables()

Return a PolynomialObjective with trivial variables removed.

As an example, suppose that we have a PolynomialObjective defined by

PolynomialObjective(

polynomial={(1,): 1}, num_variables=3

)

which essentially means the polynomial p defined by p(x, y, z) = y. This has two variables that p doesn’t actually depend on. In this case, the method reduce_variables will return a polynomial of one variable along with a mapping to identify variables appropriately. Specifically, in this case the return would be

{
‘polynomial’: PolynomialObjective(polynomial={(0,): 1},

num_variables=1 )

‘mapping’: {1: 0}

}.

classmethod validate_type(v)

This validator only confirms that we are dealing with an object of the expected type. This does not validate internal consistency of attributes for the Objective function because that is done by __init__.

class qcware.types.optimization.Constraints(constraints: Dict[qcware.types.optimization.predicate.Predicate, List[qcware.types.optimization.problem_spec.objective.PolynomialObjective]], num_variables: int, domain: Optional[Union[qcware.types.optimization.variable_types.Domain, str]] = None, variable_name_mapping: Optional[dict] = None, validate_types: bool = True)

Specification of constraints on binary variables.

An object of class Constraints does not have information about the objective function on which the constraints are applied. It is simply a collection of constraints which can then be imposed on something.

To specify constraints, we use a “constraint dict”. The format of this dict is:

{type of constraint: list of constraints of that type}.

The “type of constraint” means a Predicate object. The list of constraints of a given Predicate are a list of PolynomialObjective s.

This can be understood fairly easily by example. Suppose that f is an PolynomialObjective with 3 boolean variables. We take:

f(x, y, z) = (x + y + z - 1)^2

which is minimized when exactly one of the three variables is 1.

If we want to impose the condition that either x or z is zero, we can roughly use the constraint dict:

{Predicate.ZERO: [p]}

where p is the PolynomialObjective representing the function:

p(x, y, z) = OR(x, z) = x + z - x z

(To build this, see the documentation for PolynomialObjective.) If we additionally want to add the constraint that the sum of the three variables is at least 2, we can make our dict:

{Predicate.ZERO: [p], Predicate.POSITIVE: [q]}

where q is a PolynomialObjective representing q(x, y, z) = x + y + z - 1. The reason that we are using [p] and [q] instead of just p and q is that we can add additional constraints of those types in this fashion by adding more entries to the lists.

constraint_exists(order: Optional[Union[int, Iterable[int]]] = None, predicate: Optional[qcware.types.optimization.predicate.Predicate] = None)

Return True iff a constraint exists with given order or predicate.

order can be an int or an iterable of ints. predicate is a Predicate object.

If order and predicate are both None, this function returns True iff any constraint exists.

get_constraint_group(predicate: qcware.types.optimization.predicate.Predicate, order: Optional[Union[int, Iterable[int]]] = None)

Iterate over constraints with specified predicate and order.

If order is not specified, all orders are generated.

num_constraints(predicate: Optional[qcware.types.optimization.predicate.Predicate] = None)

Return the number of constraints.

If a predicate is specified, only return the number of constraints for that predicate.

class qcware.types.optimization.BruteOptimizeResult(*, domain: qcware.types.optimization.variable_types.Domain, value: int = None, argmin: List[str] = [], solution_exists: bool = True)

Return type for brute force maximization and minimization.

When solution_exists == False, we must have value is None and argmin == [].

Arguments are specified with a list of strings that describe solutions. For the boolean case, this means something like [‘00101’, ‘11100’] and for the spin case, this means something like [‘++-+-’, ‘—++’].

The method int_argmin can be used to obtain minima in the format

Boolean case: [[0, 0, 1, 0, 1], [1, 1, 1, 0, 0]]

or

Spin case: [[1, 1, -1, 1, -1], [-1, -1, -1, 1, 1]].

int_argmin() List[List[int]]

Convert argmin to a list of list of ints.

Functions

qcware.forge.optimization.brute_force_minimize(objective: qcware.types.optimization.problem_spec.objective.PolynomialObjective, constraints: Optional[qcware.types.optimization.problem_spec.constraints.Constraints] = None, backend: str = 'qcware/cpu')

Minimize given objective polynomial subject to constraints.

Arguments:

Parameters
  • objective (types.PolynomialObjective) – The integer-coefficient polynomial to be evaluated should be specified by a PolynomialObjective. See documentation for PolynomialObjective for more information. Note that variables are boolean in the sense that their values are 0 and 1.

  • constraints (Optional[types.Constraints]) – Optional constraints are specified with an object of class Constraints. See its documentation for further information., defaults to None

  • backend (str) – String specifying the backend. Currently only [qcware/cpu] available, defaults to qcware/cpu

Returns

BruteOptimizeResult object specifying the minimum value of the objective function (that does not violate a constraint) as well as the variables that attain this value.

Return type

types.BruteOptimizeResult

Binary Optimization

Types

class qcware.types.optimization.BinaryProblem(*, objective: qcware.types.optimization.problem_spec.objective.PolynomialObjective, constraints: qcware.types.optimization.problem_spec.constraints.Constraints = None, name: str = 'my_qcware_binary_problem')
property constrained

True if this problem instance is constrained.

property constraint_dict

Constraints in a dict format.

property domain

The domain (boolean or spin) for the problem instance.

dwave_dict()

Returns a dict valid for D-Wave problem specification.

classmethod from_dict(objective: Dict[Tuple[int, ...], int], domain: qcware.types.optimization.variable_types.Domain = Domain.BOOLEAN)

Creates the BinaryProblem from a dict specifying a boolean polynomial.

num_constraints(predicate: Optional[qcware.types.optimization.predicate.Predicate] = None)

Return the number of constraints.

If a predicate is specified, only return the number of constraints for that predicate.

property num_variables

The number of variables for the objective function.

class qcware.types.optimization.BinaryResults(*, sample_ordered_dict: collections.OrderedDict, original_problem: qcware.types.optimization.problem_spec.binary_problem.BinaryProblem, task_metadata: dict = None, result_metadata: dict = None)
property domain: qcware.types.optimization.variable_types.Domain

The domain (boolean or spin) of the variables.

items()

Iterate through the sample data.

The order of iteration goes from lowest values of the objective function to the highest.

keys()

Iterate through str representations of samples.

The keys are binary strings like ‘0101’. The order of the iteration goes from lowest values of the objective function to highest.

property lowest_value: int

Lowest observed value of the objective function.

property lowest_value_bitstring: Tuple[int, ...]

A Bitstring with the lowest value of the objective function.

This property only provides one example of a bitstring with the lowest value. To get all bitstrings with lowest value, use lowest_value_sample_list.

property lowest_value_sample_list: List[qcware.types.optimization.results.results_types.Sample]

List of samples with lowest observed objective value.

property num_bitstrings_lowest_value: int

The number of observed bitstrings of the lowest value.

num_bitstrings_under(val: int) int

The number of distinct bitstrings below a given objective value.

num_occurrences(bitstring: Union[str, Iterable[int]]) int

Get the number of occurrences for a given binary string.

If the specified bitstring does has no samples, 0 is returned.

property num_occurrences_lowest_value: int

The number of observed occurrences of the lowest value.

num_occurrences_under(val: int) int

The number of occurrences below a given objective value.

property num_variables: int

The number of binary variables for the objective function.

property sample_list: List[qcware.types.optimization.results.results_types.Sample]

List of all samples ordered by objective value.

property total_num_occurrences: int

The total number of occurrences of any bitstring.

Includes in the count multiple occurrences of the same strings.

Functions

qcware.forge.optimization.optimize_binary(instance: qcware.types.optimization.problem_spec.binary_problem.BinaryProblem, backend: str, constraints_linear_A: list = [], constraints_linear_b: list = [], constraints_sat_max_runs: int = 3100, constraints_hard: bool = False, constraints_penalty_scaling_factor: int = 1, constraints_equality_R: list = [], constraints_equality_c: list = [], constraints_inequality_S: list = [], constraints_inequality_d: list = [], return_all_solutions: bool = False, num_runs: int = 50, dwave_algorithm: str = None, dwave_solver_limit: str = None, dwave_target_energy: str = None, dwave_find_max: str = None, dwave_reduce_intersample_correlation: str = None, dwave_num_spin_reversal_transforms: str = None, dwave_programming_thermalization: str = None, dwave_reinitialize_state: str = None, dwave_anneal_offsets: str = None, dwave_anneal_offsets_delta: str = None, dwave_num_reads: int = 1, dwave_max_answers: str = None, dwave_flux_biases: str = None, dwave_beta: str = None, dwave_answer_mode: str = None, dwave_auto_scale: str = None, dwave_postprocess: str = None, dwave_annealing_time: str = None, dwave_anneal_schedule: str = None, dwave_initial_state: str = None, dwave_chains: str = None, dwave_flux_drift_compensation: bool = None, dwave_beta_range: str = None, dwave_num_sweeps: str = None, dwave_precision_ancillas: str = None, dwave_precision_ancillas_tuples: str = None, constraints_hard_num: int = 4, sa_num_sweeps: int = 200, use_sample_persistence: bool = False, sample_persistence_solution_threshold: float = 0.5, sample_persistence_persistence_threshold: float = 0.5, sample_persistence_persistence_iterations: int = 0, google_num_steps: int = 1, google_n_samples: int = 1000, google_arguments_optimizer: dict = {}, google_step_sampling: bool = True, google_n_samples_step_sampling: int = 1000, number_of_blocks: int = 1, iterations: int = 50, initial_solution: list = None, always_update_with_best: bool = True, update_q_each_block_solution: bool = True, qaoa_nmeasurement: int = None, qaoa_optimizer: str = 'COBYLA', qaoa_beta: float = None, qaoa_gamma: float = None, qaoa_p_val: int = 1)

Solve a binary optimization problem using one of the solvers provided by the platform. This function solves a binary optimization problem that is either

  • Unconstrained (quadratic or higher order)

  • Linearly and/or quadratically Constrained (quadratic)

Constraints may be linear or quadratic. Specifically, the function is capable of solving a function of the form

\[ \begin{align}\begin{aligned}\begin{split}\min_x x^T& Q x \\\end{split}\\\begin{split}\text{such that} \hspace{4em} Ax &= b \\\end{split}\\\begin{split}x^T R_i x &= c_i \\\end{split}\\\begin{split}x^T S_i x &\geq d_i \\\end{split}\end{aligned}\end{align} \]

Here, \(x\) is a length-\(n\) vector of binary values, i.e., \(\{0,1\}^n\) (this is what the solver finds). \(Q\) is a \((n\times n)\) matrix of reals. \(A\) is a \((m \times n)\) matrix of reals (partially specifying \(m\) different linear constraints). \(b\) is a length-\(m\) vector of reals (specifying the other component of m different linear constraints). Every \(R_i\) and \(S_i\) is a \((n \times n)\) matrix of reals, and every \(c_i\) and \(d_i\) is a real constant. The \((R_i, c_i)\) pairs specify quadratic equality constraints, and the \((S_i, d_i)\) pairs specify quadratic inequality constraints.

In the simplest case, the only variables required to be passed to this function are a valid access key for the platform and a dictionary representing a QUBO. Additional options are available to:

  • Specify constraints for a problem

  • Select different solvers (note: different accounts have different solvers available)

  • Specify solver-specific parameters

Error handling is provided by the platform, and warnings and errors that are detected while attempting to run a problem are returned in the JSON object returned by this function.

Possible warnings include:

Warning Code

Warning Message

7

Precision required not supported by the machine, still proceeding.

10

Hardware solver failed, solving in software solver.

22

Automatic parameter setting failed; solving using default values.

Possible errors include:

Error Code

Error Message

6

Integer formulation for HFS not found.

11

D-Wave hardware solver returned error.

100

Invalid solver selected.

It is strongly recommended to wrap a call to optimize_binary in a try/catch block since it is possible for the platform or the client library to raise an exception.

Arguments:

Parameters
  • instance (BinaryProblem) – The objective function matrix in the optimization problem described above. In the case of a quadratic problem, this is a 2D matrix; generally, in the case of higher-order problems, this is an \(n\)-dimensional matrix (a tensor). Since \(Q\) is usually sparse, \(Q\) should be specified as a Python dictionary with integer or string pairs \((i,j)\) as keys (representing the \((i,j)\)) and integer or float values. In the case of a cubic function, for example, some dictionary keys will be 3-tuples of integers, rather than pairs. Alternatively, \(Q\) may be specified as a numpy array or list, in which case mat_to_dict is called on \(Q\) before sending it to the platform. Note that that helper function assumes \(Q\) is symmetric, which may not be true in general. It is strongly encouraged to format \(Q\) is a dictionary.

  • backend (str) –

    The name of the backend to use for the given problem. Currently valid values are:

    • ”dwave/2000q”, “dwave/advantage”: Run on a physical d-wave machine using quantum annealing

    • ”qcware/cpu”: Run on a classical computing backend using a brute-force solver

    • ”qcware/cpu_simulator”: Run on a classical computing simulation of a quantum computer, using QAOA

    • ”qcware/gpu_simulator”: Run on a gpu-accelerated simulation of a quantum computer, using QAOA

  • constraints_linear_A (list) – The \(A\) matrix for specifying linear constraints. \(A\) should be formatted as a two-dimensional Python list. Default value []., defaults to []

  • constraints_linear_b (list) – The \(b\) vector for specifying linear constraints. \(b\) should be formatted as a one-dimensional Python list. Default value []., defaults to []

  • constraints_sat_max_runs (int) – The maximum number of iterations the platform should run in order to find a formulation where all constraints are satisfied. Default value 3100., defaults to 3100

  • constraints_hard (bool) – Whether to strictly enforce all constraints; if False, constraint penalties may be low enough such that constraints are violated, with the benefit of an improved energy landscape. Default value False., defaults to False

  • constraints_penalty_scaling_factor (int) – An extra constant scaling factor for the Lagrange multipliers associated with the penalty terms for the constraints. This may be helpful if constraints are being violated too much or too often. Default value 1., defaults to 1

  • constraints_equality_R (list) – The \(R\) matrices for specifying quadratic equality constraints. \(R\) should be formatted as a list of two-dimensional lists (i.e., a list of matrices). Default value []., defaults to []

  • constraints_equality_c (list) – The \(c\) vectors for specifying quadratic equality constraints. \(c\) should be formatted as a list of one-dimensional Python lists (i.e., a list of vectors). Default value []., defaults to []

  • constraints_inequality_S (list) – The \(S\) matrices for specifying quadratic inequality constraints. \(S\) should be formatted as a list of two-dimensional lists (i.e., a list of matrices). Default value []., defaults to []

  • constraints_inequality_d (list) – The \(d\) vectors for specifying quadratic inequality constraints. \(d\) should be formatted as a list of one-dimensional Python lists (i.e., a list of vectors). Default value []., defaults to []

  • return_all_solutions (bool) – Whether to return all the candidate solutions found for a problem; if False, the platform will only return the solution corresponding to the lowest energy found. Default value False., defaults to False

  • num_runs (int) – The number of iterations to run with the selected solver. Default value 50., defaults to 50

  • dwave_algorithm (str) – , defaults to None

  • dwave_solver_limit (str) – , defaults to None

  • dwave_target_energy (str) – , defaults to None

  • dwave_find_max (str) – , defaults to None

  • dwave_reduce_intersample_correlation (str) – D-Wave hardware system parameter. See reduce_intersample_correlation., defaults to None

  • dwave_num_spin_reversal_transforms (str) – D-Wave hardware system parameter. See num_spin_reversal_transforms., defaults to None

  • dwave_programming_thermalization (str) – D-Wave hardware system parameter. See programming_thermalization., defaults to None

  • dwave_reinitialize_state (str) – D-Wave hardware system parameter. See reinitialize_state., defaults to None

  • dwave_anneal_offsets (str) – D-Wave hardware system parameter. See anneal_offsets., defaults to None

  • dwave_anneal_offsets_delta (str) – Parameter greater or equal to 0 that is used to generate anneal offsets, cannot be specified if dwave_anneal_offsets is also specified. We recommend the value to be in [0, 0.05]. See https://arxiv.org/pdf/1806.11091.pdf., defaults to None

  • dwave_num_reads (int) – D-Wave hardware system parameter. See num_reads., defaults to 1

  • dwave_max_answers (str) – D-Wave hardware system parameter. See max_answers., defaults to None

  • dwave_flux_biases (str) – D-Wave hardware system parameter. See flux_biases., defaults to None

  • dwave_beta (str) – D-Wave hardware system parameter. See beta., defaults to None

  • dwave_answer_mode (str) – D-Wave hardware system parameter. See answer_mode., defaults to None

  • dwave_auto_scale (str) – D-Wave hardware system parameter. See auto_scale., defaults to None

  • dwave_postprocess (str) – D-Wave hardware system parameter. See postprocess., defaults to None

  • dwave_annealing_time (str) – D-Wave hardware system parameter. See annealing_time., defaults to None

  • dwave_anneal_schedule (str) – D-Wave hardware system parameter. See anneal_schedule., defaults to None

  • dwave_initial_state (str) – D-Wave hardware system parameter. See initial_state., defaults to None

  • dwave_chains (str) – D-Wave hardware system parameter. See chains., defaults to None

  • dwave_flux_drift_compensation (bool) – D-Wave hardware system parameter. See flux_drift_compensation., defaults to None

  • dwave_beta_range (str) – D-Wave software system parameter. See beta_range., defaults to None

  • dwave_num_sweeps (str) – D-Wave software system parameter. See num_sweeps., defaults to None

  • dwave_precision_ancillas (str) – , defaults to None

  • dwave_precision_ancillas_tuples (str) – , defaults to None

  • constraints_hard_num (int) – , defaults to 4

  • sa_num_sweeps (int) – If using a simulated annealing solver, how many sweeps to perform per run of the algorithm. Default value 200., defaults to 200

  • use_sample_persistence (bool) – Whether to use the sample persistence method of https://arxiv.org/abs/1606.07797 , which aims to improve the probability of a quantum annealer to obtain an optimal solution., defaults to False

  • sample_persistence_solution_threshold (float) – A threshold that is used to filter out higher-energy candidate solutions from the sample persistence method. A percentage that ranges from 0 to 1., defaults to 0.5

  • sample_persistence_persistence_threshold (float) – A threshold between 0 and 1 such that a variable is fixed if its mean absolute value across the filtered sample is larger than the value of the threshold. Called fixing_threshold in the original paper., defaults to 0.5

  • sample_persistence_persistence_iterations (int) – The number of iterations to run the sample persistence algorithm. Generally speaking, more iterations will make the algorithm more successful, at the cost of increased computation time., defaults to 0

  • google_num_steps (int) – The number of QAOA steps implemented by the algorithm. Default value 1., defaults to 1

  • google_n_samples (int) – The number of runs corresponding to the final sampling step. Default value 1000., defaults to 1000

  • google_arguments_optimizer (dict) – The dictionary that contains the parameters of the bayesian-optimization optimizer. Default value {'init_point': 10, 'number_iter': 20, 'kappa': 2}., defaults to {}

  • google_step_sampling (bool) – Whether to sample the circuit with the current parameters at every step of the optimization (True) or just at the final one. Default value True., defaults to True

  • google_n_samples_step_sampling (int) – The number of runs corresponding to sampling at every step of the optimization. Default value 1000., defaults to 1000

  • number_of_blocks (int) – number of blocks to decompose problem into using random decomposition. Default value :obj: 1 meaning no decomposition., defaults to 1

  • iterations (int) – number of iterations to cycle through when using random decomposition. Only valid if number_of_blocks is greater than 1. Each iterations corresponds to solving all blocks of the decomposition once. Default value 50., defaults to 50

  • initial_solution (list) – initial solution seed for constructing the blocks using random decomposition. If none is provided, a random solution is initialized. Default value :obj: None. initial_solution should be the same type as Q../, defaults to None

  • always_update_with_best (bool) – solutions found using decomposition do not monotonically get better with each iterations. The best solution is always returned, but this flag determines whether or not to construct new decomposition using best solution. Default value :obj: True., defaults to True

  • update_q_each_block_solution (bool) – each blocks decomposed Q matrix can be constructed at the onset of block composition, or updated every time a block is solved. Default value :obj: True., defaults to True

  • qaoa_nmeasurement (int) – The number of measurements to use for the QAOA algorithm if a simulator is chosen. Leave at null to attempt an ideal Pauli measurement. Ideal Pauli measurements can only be used on backends which support statevectors and will raise an exception otherwise., defaults to None

  • qaoa_optimizer (str) – The optimizer to use for the QAOA algorithm if a simulator backend is chosen. Valid options are COBYLA, bounded_Powell, and analytical, or None if qaoa_beta and qaoa_gamma are provided., defaults to COBYLA

  • qaoa_beta (float) – A \(\beta\) angle(s) to provide to the QAOA algorithm if a simulator backend is chosen. This can either be a float or a list of floats of length qaoa_p_val. Invalid unless qaoa_gamma is also provided and has the same length., defaults to None

  • qaoa_gamma (float) – A \(\gamma\) angle(s) to provide to the QAOA algorithm if a simulator backend is chosen. This can either be a float or a list of floats of length qaoa_p_val. Invalid unless qaoa_beta is also provided and has the same length., defaults to None

  • qaoa_p_val (int) – A p_val to provide the qaoa algorithm if a simulator backend is chosen. Must be equal to the number of \(\beta\) and \(\gamma\) angles provided in qaoa_beta and qaoa_gamma., defaults to 1

Returns

A BinaryResults object

Return type

BinaryResults

Quantum Approximate Optimization Algorithm (QAOA)

qcware.forge.optimization.find_optimal_qaoa_angles(Q: dict = {}, num_evals: int = 100, num_min_vals: int = 10, fastmath_flag_in: bool = True, precision: int = 30)

Finds the optimal expectation values for a given cost function, to be used in QAOA.

Arguments:

Parameters
  • Q (dict) – The objective function matrix. As \(Q\) is usually sparse, it should be specified as a Python dictionary with integer pairs \((i,j)\) as keys (representing the \((i,j)\)) and integer or float values., defaults to {}

  • num_evals (int) – The number of evaluations used for \(\beta\)/\(\gamma\), defaults to 100

  • num_min_vals (int) – The number of returned minima, defaults to 10

  • fastmath_flag_in (bool) – The “fastmath” flag in Numba, defaults to True

  • precision (int) – Inverse proportional to the minimum distance between peaks (nx/precision), defaults to 30

Returns

A tuple of three values min_val, min_beta_gamma, Z where:

  • min_val is a list of the best num_min_vals expectation values found, sorted from minimum to maximum.

  • min_beta_gamma is a list of [\(\beta\), \(\gamma\)] pairs representing the best num_min_vals expectation values found, in the same order as the expectation values

  • Z is a numpy.ndarray of shape (num_evals, num_evals) representing the expectation value for the beta/gamma pair. Each row represents a choice of \(\gamma\) and each column represents a choice of \(\beta\), so Z[1,2] represents the expectation value from the \(\gamma\) value Y[1] and the \(\beta\) value X[2]

Return type

tuple

qcware.forge.optimization.qaoa_expectation_value(problem_instance: qcware.types.optimization.problem_spec.binary_problem.BinaryProblem, beta: numpy.ndarray, gamma: numpy.ndarray, num_samples: Optional[int] = None, backend: str = 'qcware/cpu')

Get the QAOA expectation value for a BinaryProblem instance. This function sets up the conventional quantum state for the quantum approximate optimization algorithm (QAOA) based on the objective function in the BinaryProblem problem_instance. Because this is conventional QAOA, problem_instance must be unconstrained: the user can add terms to their objective function to account for constraints. This function can be used in a QAOA workflow to optimize or study angles.

Arguments:

Parameters
  • problem_instance (BinaryProblem) – Unconstrained BinaryProblem instance specifying the objective function.

  • beta (numpy.ndarray) – NumPy array with shape (p,) giving beta angles as typically defined in the QAOA).

  • gamma (numpy.ndarray) – NumPy array with shape (p,) giving gamma angles as typically defined in the QAOA).

  • num_samples (Optional[int]) – The number of measurements to use to estimate expectation value. When set to None (the default value), simulation is used (if the backend allows it) to get an exact expectation value. This can be much faster than using samples., defaults to None

  • backend (str) – String specifying the backend. Currently only [qcware/cpu] available, defaults to qcware/cpu

Returns

The expectation value for the QAOA state.

Return type

ndarray

qcware.forge.optimization.qaoa_sample(problem_instance: qcware.types.optimization.problem_spec.binary_problem.BinaryProblem, beta: numpy.ndarray, gamma: numpy.ndarray, num_samples: int, backend: str = 'qcware/cpu')

Build a QAOA circuit for given (objective, angles) and sample. This function sets up the conventional quantum state for the quantum approximate optimization algorithm (QAOA) based on the objective function in the BinaryProblem problem_instance. That state is then samples and a histogram of results is returned. Because this is conventional QAOA, problem_instance must be unconstrained: the user can add terms to their objective function to account for constraints.

Arguments:

Parameters
  • problem_instance (BinaryProblem) – Unconstrained BinaryProblem instance specifying the objective function.

  • beta (numpy.ndarray) – NumPy array with shape (p,) giving beta angles as typically defined in the QAOA).

  • gamma (numpy.ndarray) – NumPy array with shape (p,) giving gamma angles as typically defined in the QAOA).

  • num_samples (int) – The number of samples to take from the QAOA state.

  • backend (str) – String specifying the backend. Currently only [qcware/cpu] available, defaults to qcware/cpu

Returns

BinaryResults providing a histogram of bit samples.

Return type

BinaryResults