Binary Optimization

qcware.optimization.solve_binary(Q: dict, 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: str = None, 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, api_key: str = None, host: str = None)

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 solve_binary in a try/catch block since it is possible for the platform or the client library to raise an exception.

Arguments:

Parameters
  • Q (dict) – 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”: Run on a physical d-wave machine using quantum annealing

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

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

    • ”vulcan/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 (str) – D-Wave hardware system parameter. See num_reads., defaults to None

  • 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, 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 dict, containing zero or more of the fields:

  • ’solution’ (dict): A Python dictionary representing the solution vector. If return_all_solutions is True, this is a list of dicts. However, if the input Q is a 2D numpy array, then each :obj`solution` will be a 1D numpy array; if the input Q is a list of lists, then each :obj`solution` will also be a list. :obj`solution` maps variables labels to their binary values, thus :obj`solution[i]` is the value of the :obj`i`th binary variable.

  • ’num_runs’ (int): How many total runs of the chosen solver were performed in order to produce the returned solution.

  • ’num_qubits’ (int): How many physical qubits (or simulated qubits, in the case of a software solver) were used for solving the problem.

  • ’num_logical_variables’ (int): How many logical variables were contained in the problem.

  • ’warnings’ (list): A list of strings containing warning messages from the platform generated when attempting to solve the problem. This key does not exist if no warnings were raised.

  • ’warning_codes’ (list): A list of ints containing warning codes from the platform generated when attempting to solve the problem. This key does not exist if no warnings were raised.

  • ’error’ (str): A string containing an error message from the platform generated when attempting to solve the problem. This key does not exist if no error occurred.

  • ’error_code’ (int): An int containing an error codes from the platform generated when attempting to solve the problem. This key does not exist if no error occurred.

  • ’extra_info’ (list): A Python list containing additional information returned by a solver.

Return type

dict

Optimal QAOA Angles

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

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