ProblemInstance

class iqm.applications.applications.ProblemInstance

Bases: ABC

The abstract base class for defining problem instances.

Currently, only problems with binary variables are supported. Any possible candidate solution is therefore represented by a bitstring (a string of 1’s and 0’s).

The abstract methods dim() and quality() are meant to be overridden by children classes, depending on how the dimension of the problem and the quality of the solution are understood.

The upper/lower bound, average/best quality attributes start as None. The first time one of them is called, it calls the method initialize_properties(), which calculates all of them by brute-forcing over all bitstrings representing solution candidates.

Attributes

average_quality	The average quality value over all possible bitstrings.
best_quality	The best quality value over all possible bitstrings.
dim	The dimension of the problem (e.g., the number of nodes in a problem graph).
lower_bound	The lowest quality value among all possible bitstrings.
upper_bound	The highest quality value among all possible bitstrings.

Methods

average_quality_counts(counts)	Accepts a dictionary and returns the average quality of the keys weighted by their values.
average_quality_renormalized(counts)	Accepts a dictionary and returns the renormalized quality of the keys weighted by their values.
cvar(counts[, quantile])	Calculates the Conditional Value at Risk (CVaR) of the given dictionary of counts at the given quantile.
fix_variables(variables)	Fixes (assigns) some of the problem variables.
initialize_properties([max_size])	The initialization method for upper/lower bound of the cost function and its average/best value.
local_bitflip_bitstring(bit_str)	Post-processing which takes a bitstring and replaces it with its lowest-energy unit Hamming distance neighbor.
local_bitflip_postprocessing(counts)	Postprocessing method for checking a unit Hamming distance neighborhood of the dictionary of counts.
percentile_counts(counts, quantile[, ...])	A method that selects only the best / worst quantile of given counts, measured by quality().
quality(bit_str)	Accepts a bitstring and returns its quality / energy (the smaller the better).
quality_renormalized(bit_str)	Accepts a bitstring and returns renormalized quality of that bitstring.
restore_fixed_variables(counts)	Postprocessing method for restoring fixed variables to the measurement bitstrings.

abstract property dim: int

The dimension of the problem (e.g., the number of nodes in a problem graph).

abstract quality(bit_str)

Accepts a bitstring and returns its quality / energy (the smaller the better).

Parameters:

bit_str (str) – The bitstring representing a solution candidate.

Return type:

float

fix_variables(variables)

Fixes (assigns) some of the problem variables.

Parameters:

variables (list[Hashable] | dict[Hashable, int]) – Either a list of variables (which get all fixed to the value 1) or a dictionary with keys equal to the variables to fix and whose values are equal to the values to fix them to (either 1 or 0).

Return type:

None

initialize_properties(max_size=30)

The initialization method for upper/lower bound of the cost function and its average/best value.

The quantities are calculated by brute force (scaling exponentially). By default, using this with problem sizes larger than max_size (default 30) will raise ValueError. This can be bypassed by making max_size larger or setting it to None.

Parameters:

max_size (int | None) – The maximum size of problems for which the properties may be calculated.

Raises:

ValueError – If initialize_properties() was called on a ProblemInstance object with dimension larger than max_size.

Return type:

None

property upper_bound: float

The highest quality value among all possible bitstrings.

Can be calculated together with other bounds using the brute-force initialize_properties(). Shouldn’t be modified by a user.

property lower_bound: float

The lowest quality value among all possible bitstrings.

Can be calculated together with other bounds using the brute-force initialize_properties(). Shouldn’t be modified by a user.

property average_quality: float

The average quality value over all possible bitstrings.

Can be calculated together with bounds using the brute-force initialize_properties(). Shouldn’t be modified by a user. Meant to be used in comparison with QAOA results to see how much (if at all) the optimization improves over uniformly random guessing.

property best_quality: float

The best quality value over all possible bitstrings.

For minimization problems, this is equal to lower_bound. Like similar properties, it can be calculated using the brute-force initialize_properties(). Shouldn’t be modified by a user. Meant to be used in comparison with QAOA results to see how close the optimization gets to the ideal best solution.

quality_renormalized(bit_str)

Accepts a bitstring and returns renormalized quality of that bitstring.

The quality is renormalized using best_quality and average_quality.

• A value of 1 corresponds to the best solution.

• A value of 0 corresponds to average quality.

• A value above/under 0 corresponds to better/worse than average quality.

Parameters:

bit_str (str) – The bitstring representing a solution.

Returns:

The renormalized quality of the solution as a float.

Return type:

float

average_quality_counts(counts)

Accepts a dictionary and returns the average quality of the keys weighted by their values.

The input dictionary has the format of “counts” from a qiskit experiment. The keys are bitstrings (representing possible solutions) and the values are their respective counts, i.e., the number of times that the particular string was sampled from a QAOA run. The quality is calculated by quality().

Parameters:

counts (dict[str, int]) – A dictionary whose keys are solution bitstrings and whose values are the respective counts.

Returns:

Average quality of the bitstrings, weighted by their counts.

Raises:

ValueError – If the number of measurements in counts is 0 (e.g., if it’s an empty dictionary).

Return type:

float

average_quality_renormalized(counts)

Accepts a dictionary and returns the renormalized quality of the keys weighted by their values.

Calculates the average weighted quality using average_quality_counts() and renormalizes it using best_quality and average_quality.

• A value of 1 corresponds to the best solution.

• A value of 0 corresponds to average quality.

• A value above/under 0 corresponds to better/worse than average quality.

Parameters:

counts (dict[str, int]) – A dictionary whose keys are solution bitstrings and whose values are the respective counts.

Returns:

Average quality of the bitstrings, weighted by their counts and renormalized.

Return type:

float

restore_fixed_variables(counts)

Postprocessing method for restoring fixed variables to the measurement bitstrings.

When variables are fixed, the number of variables of the (remaining) problem is reduced. When the problem is solved (e.g., by a quantum computer), the solutions doesn’t include the fixed variables. This method takes a dictionary of solutions (e.g., the counts from a quantum computer) and modifies the keys (bitstrings) by inserting the fixed variables where they belong.

Parameters:

counts (dict[str, int]) – A dictionary whose keys are bitstrings (solutions) and whose values are integers (their respective frequencies)

Returns:

The input dictionary corrected by inserting the fixed variables into the keys, where they belong.

Return type:

dict[str, int]

local_bitflip_bitstring(bit_str)

Post-processing which takes a bitstring and replaces it with its lowest-energy unit Hamming distance neighbor.

Takes the solution bitstring and then iteratively swaps each bit in it. The function returns the lowest-energy bitstring from all of these bitstrings (including the original bitstring).

Parameters:

bit_str (str) – The bitstring to be replaced by its lowest-energy unit Hamming distance neighbor.

Returns:

The replaced bitstring.

Return type:

str

local_bitflip_postprocessing(counts)

Postprocessing method for checking a unit Hamming distance neighborhood of the dictionary of counts.

When implemented naively, the time complexity of this scales cubically \(\mathcal{O}(n^3)\) in the number of variables (linear from iterating over them and quadratic from calculating the energy), but some computation might be saved in the calculation of the energy because it’s repeatedly calculated for very similar bitstrings.

Parameters:

counts (dict[str, int]) – A dictionary whose keys are bitstrings (solutions) and whose values are integers (their respective frequencies)

Returns:

The input dictionary modified by replacing each bitstring by its lowest-energy neigbor.

Return type:

dict[str, int]

percentile_counts(counts, quantile, best_percentile=True)

A method that selects only the best / worst quantile of given counts, measured by quality().

The quantile is weighted by the frequencies (counts) of the bitstrings. If multiple bitstrings around the quantile have the same quality, the order is selected arbitrarily (or rather, based on how the built-in sorted function sorts them). If a bitstring has counts that cross the quantile, its counts in the output are adjusted to match the quantile exactly (at least rounded to the nearest integer).

Parameters:

• counts (dict[str, int]) – The input dictionary of counts.

• quantile (float) – The quantile of counts to be selected.

• best_percentile (bool) – Boolean saying whether the “best” (lowest quality) or the “worst” (highest) bitstrings should be selected.

Returns:

A dictionary of counts, with only the best / worse bitstrings selected.

Raises:

ValueError – If the quantile is not between 0 and 1 (included).

Return type:

dict[str, int]

cvar(counts, quantile=0.05)

Calculates the Conditional Value at Risk (CVaR) of the given dictionary of counts at the given quantile.

The CVaR is the average of the worst-case quantile of the data. In the case of training QAOA, it’s often used to calculate the average of the best quantile of samples.

Parameters:

• counts (dict[str, int]) – The given dictionary of counts.

• quantile (float) – The given quantile. Since it’s common to calculate the CVaR at 5%, that’s the default value for this variable

Returns:

The CVaR of the counts.

Return type:

float