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: Optional[str] = None, dwave_solver_limit: Optional[str] = None, dwave_target_energy: Optional[str] = None, dwave_find_max: Optional[str] = None, dwave_reduce_intersample_correlation: Optional[str] = None, dwave_num_spin_reversal_transforms: Optional[str] = None, dwave_programming_thermalization: Optional[str] = None, dwave_reinitialize_state: Optional[str] = None, dwave_anneal_offsets: Optional[str] = None, dwave_anneal_offsets_delta: Optional[str] = None, dwave_num_reads: Optional[str] = None, dwave_max_answers: Optional[str] = None, dwave_flux_biases: Optional[str] = None, dwave_beta: Optional[str] = None, dwave_answer_mode: Optional[str] = None, dwave_auto_scale: Optional[str] = None, dwave_postprocess: Optional[str] = None, dwave_annealing_time: Optional[str] = None, dwave_anneal_schedule: Optional[str] = None, dwave_initial_state: Optional[str] = None, dwave_chains: Optional[str] = None, dwave_flux_drift_compensation: Optional[bool] = None, dwave_beta_range: Optional[str] = None, dwave_num_sweeps: Optional[str] = None, dwave_precision_ancillas: Optional[str] = None, dwave_precision_ancillas_tuples: Optional[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: Optional[list] = None, always_update_with_best: bool = True, update_q_each_block_solution: bool = True, qaoa_nmeasurement: Optional[int] = None, qaoa_optimizer: str = 'COBYLA', qaoa_beta: Optional[float] = None, qaoa_gamma: Optional[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 solverspecific 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
DWave 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 higherorder 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 3tuples 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 dwave machine using quantum annealing
”qcware/cpu”: Run on a classical computing backend using a bruteforce solver
”qcware/cpu_simulator”: Run on a classical computing simulation of a quantum computer, using QAOA
”qcware/gpu_simulator”: Run on a gpuaccelerated simulation of a quantum computer, using QAOA
constraints_linear_A (list) – The \(A\) matrix for specifying linear constraints. \(A\) should be formatted as a twodimensional Python list. Default value
[]
., defaults to []constraints_linear_b (list) – The \(b\) vector for specifying linear constraints. \(b\) should be formatted as a onedimensional 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 3100constraints_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 valueFalse
., defaults to Falseconstraints_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 twodimensional 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 onedimensional 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 twodimensional 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 onedimensional 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 valueFalse
., defaults to Falsenum_runs (int) – The number of iterations to run with the selected solver. Default value
50
., defaults to 50dwave_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) – DWave hardware system parameter. See reduce_intersample_correlation., defaults to None
dwave_num_spin_reversal_transforms (str) – DWave hardware system parameter. See num_spin_reversal_transforms. , defaults to None
dwave_programming_thermalization (str) – DWave hardware system parameter. See programming_thermalization., defaults to None
dwave_reinitialize_state (str) – DWave hardware system parameter. See reinitialize_state., defaults to None
dwave_anneal_offsets (str) – DWave 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) – DWave hardware system parameter. See num_reads., defaults to None
dwave_max_answers (str) – DWave hardware system parameter. See max_answers., defaults to None
dwave_flux_biases (str) – DWave hardware system parameter. See flux_biases., defaults to None
dwave_beta (str) – DWave hardware system parameter. See beta. , defaults to None
dwave_answer_mode (str) – DWave hardware system parameter. See answer_mode., defaults to None
dwave_auto_scale (str) – DWave hardware system parameter. See auto_scale., defaults to None
dwave_postprocess (str) – DWave hardware system parameter. See postprocess., defaults to None
dwave_annealing_time (str) – DWave hardware system parameter. See annealing_time., defaults to None
dwave_anneal_schedule (str) – DWave hardware system parameter. See anneal_schedule., defaults to None
dwave_initial_state (str) – DWave hardware system parameter. See initial_state., defaults to None
dwave_chains (str) – DWave hardware system parameter. See chains., defaults to None
dwave_flux_drift_compensation (bool) – DWave hardware system parameter. See flux_drift_compensation., defaults to None
dwave_beta_range (str) – DWave software system parameter. See beta_range., defaults to None
dwave_num_sweeps (str) – DWave 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 200use_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 higherenergy 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 1google_n_samples (int) – The number of runs corresponding to the final sampling step. Default value
1000
., defaults to 1000google_arguments_optimizer (dict) – The dictionary that contains the parameters of the bayesianoptimization 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 Truegoogle_n_samples_step_sampling (int) – The number of runs corresponding to sampling at every step of the optimization. Default value
1000
., defaults to 1000number_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 value50
., defaults to 50initial_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 asQ
../, defaults to Nonealways_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 dict, containing zero or more of the fields:
’solution’ (
dict
): A Python dictionary representing the solution vector. Ifreturn_all_solutions
isTrue
, this is a list of dicts. However, if the inputQ
is a 2D numpy array, then each :obj`solution` will be a 1D numpy array; if the inputQ
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)¶ 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