mqt.problemsolver.qubo_tools.qubo_generator

Provides a base class for QUBO generators that can be extended for different problem classes.

Module Contents

class SlackChainAssignment

Stores assignment information for a chain of variables in a QUBO formulation.

chains: list[list[str]]

slack_dict: dict[str, tuple[str, str]]

indices: dict[str, int]

add_slack_variable(new_slack: str, replace_1: str, replace_2: str) → None

Adds a new auxiliary variable to the assignment, replacing the two given existing variables.

Parameters:

• new_slack – The new auxiliary variable.

• replace_1 – The first variable to be replaced.

• replace_2 – The second variable to be replaced.

compute_indices(expr: sympy.Expr, offset: int = 0) → None

Computes the indices of all variables in the assignment based on their names and stores them as a side-effect.

Parameters:

• expr – The expression to analyze.

• offset – The starting offset. Defaults to 0.

class QuboGenerator(objective_function: sympy.Expr | None)

A base class for QUBO generators that can be extended for different problem classes.

Collects constraints and penalties and provides methods for constructing the QUBO representation of a problem.

objective_function

The objective function of the problem.

penalties

The constraints and corresponding penalties.

objective_function: sympy.Expr | None

penalties: list[tuple[sympy.Expr, float | None]]

expansion_cache: sympy.Expr | None = None

auxiliary_cache: dict[sympy.Expr, sympy.Expr]

disable_caching: bool = False

add_penalty(penalty_function: sympy.Expr, lam: float | None = None) → None

Adds a cost function for a constraint to the problem instance.

A penalty factor can be specified to scale the penalty function. Otherwise, a fitting penalty factor will be estimated automatically.

Parameters:

• penalty_function – A cost function that represents a constraint.

• lam – The penalty scaling factor. Defaults to None.

construct() → sympy.Expr

Constructs a mathematical representation of the QUBO formulation.

This representation is in its simplest form, including sum and product terms.

Returns:

The mathematical representation of the QUBO formulation.

construct_expansion(include_slack_information: bool = False, for_embedding: bool = False) → sympy.Expr | tuple[sympy.Expr, SlackChainAssignment]

Constructs a mathematical representation of the QUBO formulation and expands it.

This will expand sum and product terms into full sums and products of each of their elements. The final result will be a sum of terms where each term is a product of variables and scalars.

Parameters:

• include_slack_information – Whether to include information about slack variables in the result. Defaults to False.

• for_embedding – Whether to prepare the QUBO for embedding on a quantum device. Defaults to False.

Returns:

A mathematical representation of the QUBO formulation in expanded form.

Raises:

TypeError – If the constructed QUBO formulation is not a sympy expression.

expand_higher_order_terms(expression: sympy.Expr, assignment: SlackChainAssignment, chain_index: int = 1) → sympy.Expr

Expands higher order terms in a cost function to reduce the order.

Parameters:

• expression – The expression to transform.

• assignment – The assignment to store information about the slack variables.

• chain_index – The index of the current chain of auxiliary variables. Defaults to 1.

Returns:

The transformed expression.

expand_higher_order_terms_greedy_minimization(expression: sympy.Expr, assignment: SlackChainAssignment) → sympy.Expr

Reduce the order of higher order terms in a cost function by employing greedy variable minimization.

Generally, attempts to keep the number of auxiliary variables low by selecting the most frequently occurring products of variables to replace first.

Parameters:

• expression – The expression to transform.

• assignment – The assignment to store information about the slack variables.

Returns:

The transformed expression.

construct_qubo_matrix(for_embedding: bool = False) → numpy.typing.NDArray[int_ | numpy.float64]

Constructs the matrix representation of the QUBO problem.

This is achieved by first creating the expanded QUBO formula, and then taking the coefficients of each term.

Returns:

The matrix representation of the QUBO problem.

get_cost(assignment: list[int], for_embedding: bool = False) → float

Given an assignment, computes the total cost value of the corresponding cost function evaluation.

The assignment is given as a binary list, and can either contain assignments for just encoding variables or encoding + auxiliary variables. In the former case, the auxiliary values are computed automatically.

Parameters:

• assignment – The assignment for each variable (either 0 or 1).

• for_embedding – Whether to prepare the QUBO for embedding on a quantum device. Defaults to False.

Returns:

The cost value for the assignment.

count_required_variables(for_embedding: bool = False) → int

Returns the total number of variables required to represent the QUBO problem.

Parameters:

for_embedding – Whether to prepare the QUBO for embedding on a quantum device. Defaults to False.

Returns:

The number of required variables.

get_encoding_variable_count() → int

Returns the number of non-auxiliary binary variables required to represent the QUBO problem.

Returns:

The number of required binary variables.

get_variable_index(variable: sympy.Expr) → int

For a given variable, returns its index in the QUBO matrix.

Parameters:

variable – The variable to investigate.

Returns:

The index of the variable.

decode_bit_array(_array: list[int]) → Any

Given an assignment, decodes it into a meaningful result. May be extended by subclasses.

Parameters:

_array – The binary assignment.

Returns:

The decoded result.

construct_qaoa_circuit(n_qubits: int = -1, do_reuse: bool = False, include_barriers: bool = False) → qiskit.QuantumCircuit

Constructs a QAOA circuit for the QUBO problem.

Parameters:

• n_qubits – If given, sets the number of qubits for the full circuit.

• do_reuse – Attempt to reuse qubits to limit the number of variables. Defaults to False.

• include_barriers – Whether to include barriers in the circuit. Defaults to False.

Returns:

The constructed QAOA circuit.

construct_interaction_graph(offset: int = 0, for_embedding: bool = False) → list[tuple[int, int]]

Constructs the interaction graph of the QUBO problem.

Returns:

The interaction graph of the QUBO problem.

construct_embedded_qaoa_circuit(device: Calibration) → qiskit.QuantumCircuit

Constructs a QAOA circuit for the QUBO problem that is embedded on the given device.

Parameters:

device – The device to embed the QAOA circuit on.

Returns:

The constructed QAOA circuit.