quast_decisiontree.utils.functions

quast_decisiontree.utils.functions

utility functions

logger module-attribute

logger = logging.getLogger('dt_logger')

bitstring_to_list

bitstring_to_list(bitstring)

converts a binary bitstring to a list of 0's and 1's Reverses order.

Source code in src/quast_decisiontree/utils/functions.py

def bitstring_to_list(bitstring: str) -> list:
    """converts a binary bitstring to a list of 0's and 1's
    Reverses order.
    """
    return [int(x) for x in bitstring[::-1]]

eager_import

eager_import(module_dict, package)

performs eager import of all names in the module_dict from the given modules

Module names are assumed to be relative.

Parameters:

Name	Type	Description	Default
module_dict	Mapping	A dictionary with keys corresponding to relative module names, and the values being a list of attributes to be imported from those modules.	required
package	str	Base package where to load from.	required

Returns:

Name	Type	Description
dict	dict	a dictionary of the imported objects

Source code in src/quast_decisiontree/utils/functions.py

def eager_import(module_dict: Mapping, package: str) -> dict:
    """performs eager import of all names in the module_dict from the given modules

    Module names are assumed to be relative.

    Args:
        module_dict (Mapping): A dictionary with keys corresponding to relative module names, and
            the values being a list of attributes to be imported from those modules.
        package (str): Base package where to load from.

    Returns:
        dict: a dictionary of the imported objects
    """
    out = dict()

    for mod, names in module_dict.items():
        module = importlib.import_module(f".{mod}", package=package)
        for name in names:
            out[name] = getattr(module, name)

    return out

to_dict

to_dict(eigenstate)

Converts an eigenstate given as a list or dictionary into a dictionary suited for JSON serialization.

The input is never mutated; a new dictionary is returned.

Parameters:

Name	Type	Description	Default
eigenstate	Union[Mapping, Sequence]	Either a list with amplitudes in lexicographic order or a dictionary of (bitstring, amplitude) pairs.	required

Raises:

Type	Description
ValueError	If the given eigenstate is a list whose length isn't a power of 2.

Returns:

Name	Type	Description
dict	dict	A dict with entries (bitstring, value) where value will either be a real number (amplitude) or a tuple of real numbers (real, imag) representing a complex number.

Source code in src/quast_decisiontree/utils/functions.py

def to_dict(eigenstate: Mapping | Sequence) -> dict:
    """Converts an eigenstate given as a list or dictionary into a dictionary suited for JSON
    serialization.

    The input is never mutated; a new dictionary is returned.

    Args:
        eigenstate (Union[Mapping, Sequence]): Either a list with amplitudes in lexicographic
            order or a dictionary of (bitstring, amplitude) pairs.

    Raises:
        ValueError: If the given eigenstate is a list whose length isn't a power of 2.

    Returns:
        dict: A dict with entries (bitstring, value) where value will either be a real
            number (amplitude) or a tuple of real numbers (real, imag) representing a
            complex number.
    """
    if not isinstance(eigenstate, Mapping):
        if not isinstance(eigenstate, list):
            eigenstate = eigenstate.tolist()
        num_qubits = math.log2(len(eigenstate))
        if not num_qubits.is_integer():
            raise ValueError(
                "Cannot interpret the given amplitudes as qubit state, "
                "their count is no power of 2."
            )
        num_qubits = int(num_qubits)

        keys = [f"{number:0{num_qubits}b}" for number in range(2**num_qubits)]
        eigendict = dict(zip(keys, eigenstate, strict=False))
    else:
        eigendict = dict(eigenstate)

    for key, value in eigendict.items():
        if isinstance(value, complex):
            eigendict[key] = (value.real, value.imag)

    return eigendict

list_to_dict

list_to_dict(perhaps_a_dict)

converts a list to a dictionary by using the indices as keys

Parameters: perhaps_a_dict - list or dict. If dict, function will return the input. If list, input will be converted to a dict

Returns a dictionary equivalent to the input list or equal to the input dictionary.

Source code in src/quast_decisiontree/utils/functions.py

def list_to_dict(perhaps_a_dict: Mapping | Sequence) -> dict:
    """converts a list to a dictionary by using the indices as keys

    Parameters:
    perhaps_a_dict - list or dict. If dict, function will return the input. If list, input will
    be converted to a dict

    Returns a dictionary equivalent to the input list or equal to the input dictionary.
    """
    if isinstance(perhaps_a_dict, Mapping):
        return perhaps_a_dict
    return dict(enumerate(perhaps_a_dict))

load_results

load_results(filename)

loads results from the specified path to a list of dictionaries

Source code in src/quast_decisiontree/utils/functions.py

def load_results(filename: str) -> list:
    """loads results from the specified path to a list of dictionaries"""
    with open(filename, encoding="UTF-8") as file:
        result_dict = json.load(file)

    return list(result_dict.values())

get_most_likely_states

get_most_likely_states(state_dict, num_states=1)

fetches and returns the num_states most likely states from a dictionary of the form bitstring: value

Parameters: state_dict dictionary comprised of bitstrings as keys and probability values as values num_states the number of most likely states to fetch

Returns a dict with the most likely states in the same dict form

Source code in src/quast_decisiontree/utils/functions.py

def get_most_likely_states(state_dict: Mapping, num_states: int = 1) -> dict:
    """fetches and returns the num_states most likely states from a dictionary of the form
    bitstring: value

    Parameters:
    state_dict      dictionary comprised of bitstrings as keys and probability values as values
    num_states      the number of most likely states to fetch

    Returns a dict with the most likely states in the same dict form
    """
    if num_states > len(state_dict):
        num_states = len(state_dict)

    return dict(
        sorted(state_dict.items(), key=lambda x: np.abs(x[1]) ** 2, reverse=True)[:num_states]
    )

to_iterable

to_iterable(perhaps_a_list)

returns the argument if it is iterable and not a string (since we assume we don't want to naively iterate over strings) and a list with the argument otherwise

Source code in src/quast_decisiontree/utils/functions.py

def to_iterable(perhaps_a_list: Any) -> Iterable:
    """returns the argument if it is iterable and not a string (since we assume we don't want to
    naively iterate over strings) and a list with the argument otherwise
    """
    if isinstance(perhaps_a_list, Iterable) and not isinstance(perhaps_a_list, str):
        return perhaps_a_list
    return [perhaps_a_list]

get_minimal_difference

get_minimal_difference(values, zero_threshold=1e-08)

Determines the minimum nonzero distance between the two closest elements in an array, treating differences below zero_threshold as zero.

Parameters:

Name	Type	Description	Default
values	Sequence	The array containing the elements to compare.	required
zero_threshold	float	The threshold below which two elements of the array will be considered as equal. Defaults to 1e-8.	1e-08

Returns:

Name	Type	Description
float	float	The minimum nonzero distance between elements in the array.

Source code in src/quast_decisiontree/utils/functions.py

def get_minimal_difference(values: Sequence, zero_threshold: float = 1e-8) -> float:
    """Determines the minimum nonzero distance between the two closest elements in an array,
    treating differences below zero_threshold as zero.

    Args:
        values (Sequence): The array containing the elements to compare.
        zero_threshold (float, optional): The threshold below which two elements of the array
            will be considered as equal. Defaults to 1e-8.

    Returns:
        float: The minimum nonzero distance between elements in the array.
    """
    values = np.array(values)
    if not np.any(np.iscomplex(values)):
        sorted_array = np.sort(values.flatten())
        min_diff = math.inf
        for pair in np.lib.stride_tricks.sliding_window_view(sorted_array, 2):
            current_diff = np.abs(pair[1] - pair[0])
            if zero_threshold < current_diff < min_diff:
                min_diff = current_diff
        return min_diff

    min_diff = math.inf
    for pair in combinations(values.flatten(), 2):
        current_diff = np.abs(pair[1] - pair[0])
        if zero_threshold < current_diff < min_diff:
            min_diff = current_diff
    return min_diff

qubo_tensor_to_matrix

qubo_tensor_to_matrix(qubo_tensor)

Reshapes a qubo tensor (an object characterized by more than 2 indices allowing for binary variables addressed by multiple indices) into a simple QUBO matrix by serializing the binary variables.

Parameters:

Name	Type	Description	Default
qubo_tensor	ndarray	The input tensor. It needs to have an even number of indices, and the shape needs to be of form (x_1, ... ,x_n, x_1, ..., x_n)	required

Raises:

Type	Description
ValueError	If the qubo tensor has an invalid shape.

Returns:

Type	Description
ndarray	np.ndarray: The qubo matrix with serialized indices.

Source code in src/quast_decisiontree/utils/functions.py

def qubo_tensor_to_matrix(qubo_tensor: np.ndarray) -> np.ndarray:
    """Reshapes a qubo tensor (an object characterized by more than 2 indices
    allowing for binary variables addressed by multiple indices) into
    a simple QUBO matrix by serializing the binary variables.

    Args:
        qubo_tensor (np.ndarray): The input tensor. It needs to have an even number of indices,
            and the shape needs to be of form (x_1, ... ,x_n, x_1, ..., x_n)

    Raises:
        ValueError: If the qubo tensor has an invalid shape.

    Returns:
        np.ndarray: The qubo matrix with serialized indices.
    """
    s = np.shape(qubo_tensor)
    s1 = s[: int(len(s) / 2)]
    s2 = s[int(len(s) / 2) :]

    if s1 != s2:
        raise ValueError(
            "Invalid tensor shape. Either there is an odd number of indices,"
            " or some axis doesn't have the correct length"
        )

    num_vars = np.prod(s1)

    return qubo_tensor.reshape((num_vars,) * 2)

is_qubo_matrix

is_qubo_matrix(opt_problem)

checks if the input opt_problem is a qubo matrix (that is, can be cast to a numpy array, is quadratic and 2D)

Source code in src/quast_decisiontree/utils/functions.py

def is_qubo_matrix(opt_problem: Any) -> bool:
    """checks if the input opt_problem is a qubo matrix (that is, can be cast
    to a numpy array, is quadratic and 2D)
    """
    try:
        array_form = np.array(opt_problem)
    except (ValueError, TypeError):
        return False

    sh = np.shape(array_form)
    return len(sh) == 2 and sh[0] == sh[1]

get_ising_offset

get_ising_offset(qubo_matrix)

Computes the Ising offset of a QUBO matrix (or flattened tensor).

The offset is given by 1/4 * (sum_of_all_elements + sum_of_diagonal).

Parameters:

Name	Type	Description	Default
qubo_matrix	ndarray	A QUBO matrix or tensor. If a tensor (ndim > 2), it will be flattened to a matrix first.	required

Returns:

Type	Description
float	The Ising offset.

Source code in src/quast_decisiontree/utils/functions.py

def get_ising_offset(qubo_matrix: np.ndarray) -> float:
    """Computes the Ising offset of a QUBO matrix (or flattened tensor).

    The offset is given by 1/4 * (sum_of_all_elements + sum_of_diagonal).

    Args:
        qubo_matrix: A QUBO matrix or tensor. If a tensor (ndim > 2), it will
            be flattened to a matrix first.

    Returns:
        The Ising offset.
    """
    if len(np.shape(qubo_matrix)) > 2:
        qubo_matrix = qubo_tensor_to_matrix(qubo_matrix)
    return (np.sum(qubo_matrix) + np.sum(np.diag(qubo_matrix))) / 4

get_qubo_value

get_qubo_value(qubo_matrix, sample)

Calculates the value a sample generates with the given QUBO formulation

Parameters qubo_matrix the matrix of the qubo formulation sample bitstring with the same amounts of bits as the length of the dimensions of the qubo matrix

Returns qubo_value Value the sample generates

Source code in src/quast_decisiontree/utils/functions.py

def get_qubo_value(qubo_matrix: np.ndarray, sample: str) -> float:
    """Calculates the value a sample generates with the given QUBO formulation

    Parameters
    qubo_matrix         the matrix of the qubo formulation
    sample              bitstring with the same amounts of bits as the length of the dimensions
                        of the qubo matrix

    Returns
    qubo_value          Value the sample generates
    """
    if len(sample) != qubo_matrix.shape[0] or len(sample) != qubo_matrix.shape[1]:
        raise ValueError("Invalid combination of qubo matrix and sample. Inspect shapes!")
    vector = np.fromiter((int(bit) for bit in sample), dtype=float, count=len(sample))
    return float(vector @ qubo_matrix @ vector)

get_qaoa_scaling_factor

get_qaoa_scaling_factor(
    qubo_matrix,
    *,
    mixer_spectral_width=None,
    mixer_spacing=None,
    strategy="eigenvalue_spacing",
)

Attempts to find the scaling factor according to the specified strategy.

Returns 1 if the strategy fails due to the matrix having only one (distinct) eigenvalue.

Parameters: qubo_matrix - the qubo matrix representing the problem Hamiltonian mixer_spectral_width - the spectral width of the mixer. If None, defaults to 2*num_nodes mixer_spacing - the minimal spacing between eigenvalues of the mixer. Defaults to 2. strategy - "spectral_width", "eigenvalue_spacing", or "ground_state_gap"

Returns a scaling factor according to the specified strategy.

Source code in src/quast_decisiontree/utils/functions.py

def get_qaoa_scaling_factor(
    qubo_matrix: np.ndarray,
    *,
    mixer_spectral_width: float | None = None,
    mixer_spacing: float | None = None,
    strategy: str = "eigenvalue_spacing",
) -> float:
    """Attempts to find the scaling factor according to the specified strategy.

    Returns 1 if the strategy fails due to the matrix having only one (distinct)
    eigenvalue.

    Parameters:
    qubo_matrix -           the qubo matrix representing the problem Hamiltonian
    mixer_spectral_width -  the spectral width of the mixer. If None, defaults to 2*num_nodes
    mixer_spacing -         the minimal spacing between eigenvalues of the mixer. Defaults to 2.
    strategy -              "spectral_width", "eigenvalue_spacing", or "ground_state_gap"

    Returns a scaling factor according to the specified strategy.
    """
    supported_strategies = ["eigenvalue_spacing", "spectral_width", "ground_state_gap"]
    strategy = strategy.lower()
    if strategy not in supported_strategies:
        raise ValueError(f"Strategy {strategy} not supported. Choose from {supported_strategies}.")

    qubo_matrix = (qubo_matrix + qubo_matrix.T) / 2
    val = np.real(np.linalg.eigvalsh(qubo_matrix))

    if strategy == "spectral_width":
        if mixer_spectral_width is None:
            mixer_spectral_width = 2 * np.shape(qubo_matrix)[0]

        width = np.max(val) - np.min(val)
        if width == 0:
            logger.warning("Spectral width is zero, returning scaling factor 1")
            return 1

        return mixer_spectral_width / width

    if strategy == "eigenvalue_spacing":
        if mixer_spacing is None:
            mixer_spacing = 2

        problem_spacing = get_minimal_difference(val)
        if problem_spacing == math.inf:
            logger.warning("All eigenvalues are equal, returning scaling factor 1.")
            return 1
        return mixer_spacing / problem_spacing

    # strategy == "ground_state_gap"
    if mixer_spacing is None:
        mixer_spacing = 2

    val = np.sort(val)
    tol = 1e-8
    smallest_val = val[0]
    for other_val in val[1:]:
        if other_val - smallest_val > tol:
            return mixer_spacing / (other_val - smallest_val)

    logger.warning("No gap found above ground state, returning scaling factor 1.")
    return 1

find_qubo_penalty

find_qubo_penalty(
    problem_instance,
    initial_penalty=0,
    penalty_step=1,
    safety_margin=2,
    scaling_factor=1,
    num_reads=1,
    mode="QUBO_condensed",
    strategy="tabu",
)

Attempts to find a good penalty value by classically solving the problem such that the solution is feasible, then adding a safety margin to it.

Parameters: problem_instance The instance of an optimization problem initial_penalty Starting value for the penalty penalty_step how much to increase the penalty at each loop safety_margin safety_margin*penalty_step will be added at the end scaling_factor the scaling factor of the cost function num_reads number of reads the tabu search algorithm uses mode Mode to be used by the formulate_problem function strategy "tabu", "brute_force", or "max_cost"

Returns the penalty value determined by the selected strategy.

Source code in src/quast_decisiontree/utils/functions.py

def find_qubo_penalty(
    problem_instance: "OptimizationProblem",  # noqa: F821
    initial_penalty: float = 0,
    penalty_step: float = 1,
    safety_margin: float = 2,
    scaling_factor: float = 1,
    num_reads: int = 1,
    mode: str = "QUBO_condensed",
    strategy: str = "tabu",
) -> float:
    """Attempts to find a good penalty value by classically solving the problem such that the
    solution is feasible, then adding a safety margin to it.

    Parameters:
    problem_instance        The instance of an optimization problem
    initial_penalty         Starting value for the penalty
    penalty_step            how much to increase the penalty at each loop
    safety_margin           safety_margin*penalty_step will be added at the end
    scaling_factor          the scaling factor of the cost function
    num_reads               number of reads the tabu search algorithm uses
    mode                    Mode to be used by the formulate_problem function
    strategy                "tabu", "brute_force", or "max_cost"

    Returns the penalty value determined by the selected strategy.
    """
    supported_strategies = ["tabu", "brute_force", "max_cost"]
    strategy = strategy.lower()
    if strategy not in supported_strategies:
        raise ValueError(f"Strategy {strategy} not supported. Choose from {supported_strategies}.")

    if strategy == "tabu":
        smp = TabuSampler()

        solution = None
        penalty = initial_penalty
        while not problem_instance.is_feasible(solution):
            penalty += penalty_step
            _offset, qubo_tensor = problem_instance.formulate_problem(
                mode=mode, penalty_factor=penalty, scaling_factor=scaling_factor
            )
            qubo_matrix = qubo_tensor_to_matrix(qubo_tensor)
            solution = get_bitstring_from_tabu_result(
                smp.sample_qubo(qubo_matrix, num_reads=num_reads)
            )

        return penalty + safety_margin * penalty_step

    if strategy == "brute_force":
        # Modelled after https://doi.org/10.1007/s11128-022-03766-5
        offset, qubo_tensor = problem_instance.formulate_problem(
            mode=mode, penalty_factor=initial_penalty, scaling_factor=scaling_factor
        )
        qubo_matrix = qubo_tensor_to_matrix(qubo_tensor)

        offset_pen1, qubo_tensor_pen1 = problem_instance.formulate_problem(
            mode=mode, penalty_factor=1, scaling_factor=scaling_factor
        )
        qubo_matrix_pen1 = qubo_tensor_to_matrix(qubo_tensor_pen1)

        offset_pen0, qubo_tensor_pen0 = problem_instance.formulate_problem(
            mode=mode, penalty_factor=0, scaling_factor=scaling_factor
        )
        qubo_matrix_pen0 = qubo_tensor_to_matrix(qubo_tensor_pen0)

        n_bits = qubo_matrix.shape[0]
        costs = np.zeros(2**n_bits)
        cost_penalties = np.zeros(2**n_bits)

        vec_feasible = np.full((2**n_bits), False)
        cost_opt = float("inf")
        for i_state in range(2**n_bits):
            b_str = format(i_state, f"0{n_bits}b")
            costs[i_state] = get_qubo_value(qubo_matrix, b_str) + offset
            if problem_instance.is_feasible(b_str):
                vec_feasible[i_state] = True
                if costs[i_state] < cost_opt:
                    cost_opt = costs[i_state]

            cost_penalties[i_state] = (get_qubo_value(qubo_matrix_pen1, b_str) + offset_pen1) - (
                get_qubo_value(qubo_matrix_pen0, b_str) + offset_pen0
            )

        if cost_opt == float("inf"):
            raise ValueError("QUBO formulation does not have a feasible minimum.")

        cost_mean_feasible = costs[vec_feasible].mean()

        infeasible_idx = np.where(~vec_feasible)[0]
        idx_min_infeasible = infeasible_idx[np.argmin(costs[infeasible_idx])]
        cost_min_infeasible = costs[idx_min_infeasible]
        delta_P = 0

        while cost_min_infeasible < (0.5 * (cost_mean_feasible + cost_opt)):
            delta_P += (
                0.5 * (cost_mean_feasible + cost_opt) - cost_min_infeasible
            ) / cost_penalties[idx_min_infeasible]

            offset, qubo_tensor = problem_instance.formulate_problem(
                mode=mode, penalty_factor=initial_penalty + delta_P, scaling_factor=scaling_factor
            )
            qubo_matrix = qubo_tensor_to_matrix(qubo_tensor)

            for i_state in infeasible_idx:
                b_str = format(i_state, f"0{n_bits}b")
                costs[i_state] = get_qubo_value(qubo_matrix, b_str) + offset

            idx_min_infeasible = infeasible_idx[np.argmin(costs[infeasible_idx])]
            cost_min_infeasible = costs[idx_min_infeasible]

        return initial_penalty + delta_P

    # strategy == "max_cost"
    # Modelled after https://arxiv.org/pdf/1911.05296v1.pdf
    offset, qubo_tensor = problem_instance.formulate_problem(
        mode=mode, penalty_factor=0, scaling_factor=scaling_factor
    )
    qubo_matrix = qubo_tensor_to_matrix(qubo_tensor)

    n_bits = qubo_matrix.shape[0]
    max_cost = float("-inf")

    for i_state in range(2**n_bits):
        b_str = format(i_state, f"0{n_bits}b")
        cost = get_qubo_value(qubo_matrix, b_str) + offset
        if cost > max_cost:
            max_cost = cost

    return max_cost

build_varname

build_varname(indices, basename='x')

returns a string of the form x_i_j for the specified set of indices

Source code in src/quast_decisiontree/utils/functions.py

def build_varname(indices: Sequence, basename: str = "x") -> str:
    """returns a string of the form x_i_j for the specified set of indices"""
    return "".join([basename] + [f"_{i}" for i in indices])

build_indices_from_varname

build_indices_from_varname(varname)

returns the indices from a string varname (inverse to build_varname) as a tuple

Source code in src/quast_decisiontree/utils/functions.py

def build_indices_from_varname(varname: str) -> tuple[int, ...]:
    """returns the indices from a string varname (inverse to build_varname) as a tuple"""
    return tuple(np.array(varname.split("_"))[1:].astype(int))

orthonormalize

orthonormalize(matrix)

returns an orthonormalized version of the matrix with row vectors (!) normalized and orthogonalized by Gram-Schmidt

Source code in src/quast_decisiontree/utils/functions.py

def orthonormalize(matrix: np.ndarray) -> np.ndarray:
    """returns an orthonormalized version of the matrix with row vectors (!) normalized
    and orthogonalized by Gram-Schmidt
    """
    matrix = np.array(matrix)
    orthonormal_matrix = []
    for row_vector in matrix:
        for other_row in orthonormal_matrix:
            row_vector = row_vector - np.dot(row_vector, other_row) * other_row
        if np.linalg.norm(row_vector) < 1e-12:
            raise ValueError("The provided basis matrix isn't full rank.")
        row_vector = row_vector / np.linalg.norm(row_vector)
        orthonormal_matrix.append(row_vector)
    return np.array(orthonormal_matrix)

to_rgb

to_rgb(color)

returns a string with the rgb format that can be used to specify color in plotly

Source code in src/quast_decisiontree/utils/functions.py

def to_rgb(color: Sequence) -> str:
    """returns a string with the rgb format that can be used to specify color in plotly"""
    return (
        "rgb("
        + str(round(color[0] * 255))
        + ","
        + str(round(color[1] * 255))
        + ","
        + str(round(color[2] * 255))
        + ")"
    )

binary_to_ising

binary_to_ising(vector)

converts a binary vector to an Ising vector

Source code in src/quast_decisiontree/utils/functions.py

def binary_to_ising(vector: Sequence) -> list:
    """converts a binary vector to an Ising vector"""
    out = []
    for elem in vector:
        if elem == 0:
            out.append(-1)
        elif elem == 1:
            out.append(1)
        else:
            raise ValueError(f"Input vector {vector} isn't binary.")
    return out

ising_to_binary

ising_to_binary(vector)

converts an Ising vector to a binary vector.

Source code in src/quast_decisiontree/utils/functions.py

def ising_to_binary(vector: Sequence) -> list:
    """converts an Ising vector to a binary vector."""
    out = []
    for elem in vector:
        if elem == -1:
            out.append(0)
        elif elem == 1:
            out.append(1)
        else:
            raise ValueError(f"Input vector {vector} isn't Ising.")
    return out

optimality_ratio

optimality_ratio(result, optimality_test, feasibility_test)

computes the optimality ratio (optimal occurrence over feasible occurrence)

Returns 0 (the worst possible ratio) if no feasible state is present.

Arguments: result: A dictionary with an "eigenstate" item as {bitstring: value} feasibility_test: function(bitstring) -> bool optimality_test: function(bitstring) -> bool

Source code in src/quast_decisiontree/utils/functions.py

def optimality_ratio(
    result: Mapping, optimality_test: Callable, feasibility_test: Callable
) -> float:
    """computes the optimality ratio (optimal occurrence over feasible occurrence)

    Returns 0 (the worst possible ratio) if no feasible state is present.

    Arguments:
    result: A dictionary with an "eigenstate" item as {bitstring: value}
    feasibility_test: function(bitstring) -> bool
    optimality_test: function(bitstring) -> bool
    """
    try:
        eigenstate = result["eigenstate"]
    except (TypeError, AttributeError):
        try:
            eigenstate = result.eigenstate
        except AttributeError as e:
            raise AttributeError(
                "Result neither has an element or attribute called 'eigenstate'."
            ) from e
    numerator = 0
    denominator = 0

    if math.isclose(sum(abs(x) ** 2 for x in eigenstate.values()), 1):
        for res_string, amplitude in eigenstate.items():
            if feasibility_test(res_string):
                denominator += abs(amplitude) ** 2
                if optimality_test(res_string):
                    numerator += abs(amplitude) ** 2
    else:
        for res_string, occurrence in eigenstate.items():
            if occurrence < 0:
                raise ValueError(
                    "Negative probability or shot count encountered. "
                    "If results should be amplitudes, they aren't normalized"
                )
            if feasibility_test(res_string):
                denominator += occurrence
                if optimality_test(res_string):
                    numerator += occurrence

    if denominator == 0:
        return 0
    return numerator / denominator

one_hot_to_integer

one_hot_to_integer(bitstring, _num_nodes=None)

converts a one-hot encoded bitstring to a list of integers.

Attention: Returned integers are 1-based to facilitate transforming to reduced qubo indices for TSP (which prepends a zero)

Source code in src/quast_decisiontree/utils/functions.py

def one_hot_to_integer(bitstring: str, _num_nodes: int | None = None) -> list:
    """converts a one-hot encoded bitstring to a list of integers.

    Attention: Returned integers are 1-based to facilitate transforming
    to reduced qubo indices for TSP (which prepends a zero)
    """
    if len(bitstring) > 1:
        bitstring = "".join([str(i) for i in bitstring])
    if not math.sqrt(len(bitstring)).is_integer():
        raise ValueError(f"Length of {bitstring} isn't a square.")

    num_nodes = int(np.sqrt(len(bitstring)))
    var_matrix = np.array(list(bitstring)).reshape(num_nodes, -1).astype(float)

    ones = np.ones(num_nodes)
    row_sums = var_matrix.dot(ones)
    if not np.array_equal(row_sums, ones):
        raise InvalidOneHotBitstring(f"{bitstring} does not represent a feasible solution.")

    integer_sequence = [int(np.argmax(row)) + 1 for row in var_matrix]
    return integer_sequence

binary_to_integer

binary_to_integer(bitstring, num_nodes)

converts a binary encoded bitstring to a list of integers.

Attention: Returned integers are 1-based.

Source code in src/quast_decisiontree/utils/functions.py

def binary_to_integer(bitstring: str, num_nodes: int) -> list:
    """converts a binary encoded bitstring to a list of integers.

    Attention: Returned integers are 1-based.
    """
    if len(bitstring) > 1:
        bitstring = "".join([str(i) for i in bitstring])
    path = np.reshape(
        np.array(list(bitstring)).astype(str), (num_nodes, len(bin(num_nodes - 1)[2:]))
    )[:, ::-1]
    binary_list = np.apply_along_axis("".join, 1, path).tolist()
    return [int(binary, 2) + 1 for binary in binary_list]

edge_to_integer

edge_to_integer(bitstring, _num_nodes=None)

Converts a bitstring which marks all occurring edges to an integer array of visited nodes in respective order. The first city is set to zero.

Source code in src/quast_decisiontree/utils/functions.py

def edge_to_integer(bitstring: str, _num_nodes: int | None = None):
    """Converts a bitstring which marks all occurring edges to an integer array of visited
    nodes in respective order. The first city is set to zero.
    """
    x = np.array(list(bitstring)).astype(float)
    num_nodes = len(np.nonzero(x)[0])
    all_edges = np.array(list(combinations(range(num_nodes), 2)))
    occ_edges = all_edges[np.nonzero(x)[0], :]

    integer_list = np.zeros(num_nodes, dtype=int)
    row_idx = 0
    for k in range(1, num_nodes):
        row = occ_edges[row_idx]
        integer_list[k] = row[row != integer_list[k - 1]][0]
        occ_edges = np.delete(occ_edges, row_idx, axis=0)
        row_idx = np.where(occ_edges == integer_list[k])[0]
    return list(integer_list)

integer_to_one_hot

integer_to_one_hot(integer_list)

converts an integer list to a one-hot encoded binary array

Source code in src/quast_decisiontree/utils/functions.py

def integer_to_one_hot(integer_list: Sequence) -> np.ndarray:
    """converts an integer list to a one-hot encoded binary array"""
    if min(integer_list) != 0:
        integer_list = [i - 1 for i in integer_list]
    num_integer_vars = len(integer_list)
    outlist = np.zeros((num_integer_vars, num_integer_vars))
    for time, city in enumerate(integer_list):
        outlist[city][time] = 1
    outlist = np.reshape(outlist.T, (num_integer_vars**2))
    return outlist.astype(int)

integer_to_binary

integer_to_binary(integer_list)

Converts a path in the form of a list of integers into a binary encoding

Source code in src/quast_decisiontree/utils/functions.py

def integer_to_binary(integer_list: Sequence) -> np.ndarray:
    """Converts a path in the form of a list of integers into a binary encoding"""
    if min(integer_list) != 0:
        integer_list = [i - 1 for i in integer_list]
    binary_strings = [bin(i)[2:] for i in integer_list]
    max_len = max(len(s) for s in binary_strings)
    binary_matrix = [s.zfill(max_len)[::-1] for s in binary_strings]
    outlist = (
        np.asarray([int(s[i]) for i in range(max_len) for s in binary_matrix])
        .reshape(max_len, np.max(integer_list) + 1)
        .T
    )
    return outlist.astype(int).flatten()

integer_to_edge

integer_to_edge(integer_list)

Converts an integer list of visited nodes to a binary list marking edges.

Source code in src/quast_decisiontree/utils/functions.py

def integer_to_edge(integer_list: Sequence) -> np.ndarray:
    """Converts an integer list of visited nodes to a binary list marking edges."""
    num_nodes = len(integer_list)
    length = int(num_nodes * (num_nodes - 1) / 2)
    all_edges = list(combinations(range(num_nodes), 2))
    occ_edges = [
        tuple(sorted((integer_list[i], integer_list[(i + 1) % len(integer_list)])))
        for i in range(len(integer_list))
    ]

    indices = [all_edges.index(t) if t in all_edges else None for t in occ_edges]
    outlist = np.array([1 if i in indices else 0 for i in range(length)])
    return outlist.astype(int)

recursive_list_shape

recursive_list_shape(list_like)

returns a tuple describing the list shape if it is n-dimensional rectangular

Source code in src/quast_decisiontree/utils/functions.py

def recursive_list_shape(list_like: Sequence) -> list:
    """returns a tuple describing the list shape if it is n-dimensional rectangular"""
    shape = []
    depth_exhausted = False
    level_list = list_like
    while not depth_exhausted:
        try:
            shape.append(list_shape(level_list))
            if shape[-1] is False:
                return False
            level_list = level_list[0]
        except (ValueError, TypeError):
            depth_exhausted = True
    return shape

list_shape

list_shape(list_like)

Makes sure all elements of list_like have the same shape as given by the length attribute.

Returns the length of the list items if they are all equal, False otherwise.

Source code in src/quast_decisiontree/utils/functions.py

def list_shape(list_like: Sequence):
    """Makes sure all elements of list_like have the same shape as given by the length attribute.

    Returns the length of the list items if they are all equal, False otherwise.
    """
    list_iter = iter(list_like)
    correct_length = len(next(list_iter))

    try:
        if not all(len(item) == correct_length for item in list_iter):
            return False
        return correct_length
    except TypeError as exc:
        if "len()" in str(exc):
            return False
        raise

feasibility_ratio

feasibility_ratio(
    eigenstate,
    feasibility_test,
    length=None,
    encoding="one-hot",
)

Calculates the feasibility ratio of an eigenstate.

Returns 0 (the worst possible ratio) if the eigenstate carries no weight.

Parameters:

Name	Type	Description	Default
eigenstate	Mapping	The eigenstate given as a dictionary {bitstring: value}	required
feasibility_test	Callable	Function(bitstring, length, encoding) -> bool	required
length	Optional[float]	Range of integer variables (needed for binary encoding)	None
encoding	str	Encoding of the bitstring. Defaults to "one-hot".	'one-hot'

Returns:

Name	Type	Description
float	float	The feasibility ratio of the eigenstate.

Source code in src/quast_decisiontree/utils/functions.py

def feasibility_ratio(
    eigenstate: Mapping,
    feasibility_test: Callable,
    length: float | None = None,
    encoding: str = "one-hot",
) -> float:
    """Calculates the feasibility ratio of an eigenstate.

    Returns 0 (the worst possible ratio) if the eigenstate carries no weight.

    Args:
        eigenstate (Mapping): The eigenstate given as a dictionary {bitstring: value}
        feasibility_test (Callable): Function(bitstring, length, encoding) -> bool
        length (Optional[float]): Range of integer variables (needed for binary encoding)
        encoding (str): Encoding of the bitstring. Defaults to "one-hot".

    Returns:
        float: The feasibility ratio of the eigenstate.
    """
    out_ratio = 0

    if math.isclose(sum(abs(x) ** 2 for x in eigenstate.values()), 1):
        for res_string, amplitude in eigenstate.items():
            if feasibility_test(res_string, length, encoding):
                out_ratio += abs(amplitude) ** 2
        return out_ratio

    total_sum = 0
    for res_string, occurrence in eigenstate.items():
        if occurrence < 0:
            raise ValueError(
                "Negative probability or shot count encountered. "
                "If results should be amplitudes, they aren't normalized"
            )
        total_sum += occurrence
        if feasibility_test(res_string, length, encoding):
            out_ratio += occurrence

    if total_sum == 0:
        return 0
    return out_ratio / total_sum

filter_results

filter_results(results, property_name, property_value)

filters a list of results by searching for a nested property value

Arguments: results: a list of results in dictionary form property_name: nested dict key with "." separator (e.g. "metadata.id") property_value: the value to match

Source code in src/quast_decisiontree/utils/functions.py

def filter_results(results: Sequence[Mapping], property_name: str, property_value: Any) -> list:
    """filters a list of results by searching for a nested property value

    Arguments:
    results: a list of results in dictionary form
    property_name: nested dict key with "." separator (e.g. "metadata.id")
    property_value: the value to match
    """
    keys = property_name.split(".")

    outlist = []
    for result in results:
        try:
            if reduce(operator.getitem, keys, result) == property_value:
                outlist.append(result)
        except KeyError:
            continue

    return outlist

get_bitstring_from_tabu_result

get_bitstring_from_tabu_result(tabu_result)

produces the most likely state from a tabu result as a bit string

Source code in src/quast_decisiontree/utils/functions.py

def get_bitstring_from_tabu_result(tabu_result: SampleSet) -> str:
    """produces the most likely state from a tabu result as a bit string"""
    return "".join([str(i) for i in tabu_result.first.sample.values()])

normalize_counts

normalize_counts(counts)

Normalize measurement results to probabilities (sum to 1.0).

Accepts both integer counts and probability distributions.

Source code in src/quast_decisiontree/utils/functions.py

def normalize_counts(counts: dict) -> dict:
    """Normalize measurement results to probabilities (sum to 1.0).

    Accepts both integer counts and probability distributions.
    """
    total = sum(counts.values())
    if total == 0:
        return counts
    return {k: v / total for k, v in counts.items()}