Optimization

Quadratic Unconstrained Binary Optimization (QUBO) problems

QUBO problems are among the most widely used framework for solving classical optimization problems on quantum computers, and they are also one of the most interesting optimization challenges. These problems are generally NP-hard, requiring the identification of a binary vector \(\boldsymbol{x} \in \left\{0, 1\right\}^{n}\) that minimizes the following quadratic cost function:

\[\begin{equation} f\left(\boldsymbol{x}\right) = \boldsymbol{x}^T \ \mathcal{Q} \ \boldsymbol{x} = \sum\limits_{j=1}^n \sum\limits_{j^{\prime}=j}^n \mathcal{Q}_{jj^{\prime}} \ x_j \ x_{j}^{\prime} \end{equation}\]

where \(n\) is the number of optimization binary variables involved in the problem.

A QUBO problem is fully defined by its QUBO matrix \(\mathcal{Q}\), a square symmetric matrix. The diagonal elements, \(\mathcal{Q}_{jj}\), represent the self-interaction (or local bias) of each binary variable \(x_j\), while the off-diagonal ones describe the pair-interactions between different binaries. As the QUBO matrix is symmetric, we can limit the computations to its upper triangular part, as defined by the equation above.

Tensor-network based QUBO solver

The approach implemented in this submodule is based on the ground-state search algorithm from qtealeaves and involves the following steps:

• The defined QUBO problem, represented by the \(\mathcal{Q}\) matrix, is mapped to an equivalent ground-state search problem of the following spin glass Hamiltonian:

  \[\begin{equation} \mathcal{H} = \sum\limits_{j=1}^n h_j \sigma_j + \sum\limits_{j=1}^n \sum\limits_{j^{\prime}=j+1}^n \mathcal{J}_{jj^{\prime}} \sigma_j \sigma_{j^{\prime}} \end{equation}\]

  where the spin glass couplings can be obtained from the QUBO matrix elements. This mapping is achieved through the following linear invertible transformation:

  \[\begin{equation} \sigma_j = 2 x_j - 1 \end{equation}\]

  which maps each QUBO binary variable \(x_j \in \left\{0, 1\right\}\) into a spin-\(1\mathbin{/}2\) variable \(\sigma_j \in \left\{-1, +1\right\}\).

• After constructing the Hamiltonian and representing it as a tensor network operator, the qtealeaves QUBO solver applies the ground-state search algorithm to find the ground state. Once the ground state is found, the mapping is reversed to reconstruct the solution bitstring, and the cost function value is calculated for the optimized bitstring.

Several exact solvers are also implemented to benchmark the tensor network solution for small instances.

The available tensor-network representation for the QUBO ground-state wavefunction are Matrix Product States (MPSs) and Tree Tensor Networks (TTNs) from qtealeaves.emulator.

Various options for the ground-state search are available through the convergence parameters object from qtealeaves.

This submodule contains both exact and tensor-network based solvers for a generic QUBO problem in a standard format.

Exact solvers are limited to small problem sizes due to exponential computational complexity, whereas tensor network–based methods can handle larger and more complex QUBO matrices, making them suitable for more demanding optimization tasks.

class qtealeaves.optimization.qubo_solver.QUBOConvergenceParameters(max_bond_dimension: int = 8, min_bond_dimension: int | None = None, cut_ratio: float | None = 1e-09, trunc_method: str = 'R', max_iter: int = 20, abs_deviation: float = 4e-12, rel_deviation: float = 1e-12, n_points_conv_check: int = 6, arnoldi_maxiter: int = 32, ini_bond_dimension: int | None = None, psi0: str = 'random', psi0_noise: float = 1e-07, random_sweeps: bool = False, enable_spacelink_expansion: bool = False, transverse_field_ratio: float | None = None, randomseed: list[int] = <factory>, data_type: str | list[str] = 'Z', tn_ansatz: str = 'TTN', mpo_mode: int = -1, use_spinglass_sparse_mpo: bool = False, linalg_backend_library: str = 'numpy', device: str = 'cpu', tn_io_tag: str | None = None, base_log_dir: str | Path = PosixPath('QUBO_RESULTS'), log_dir: str | Path = PosixPath('qtealeaves'), tn_input_folder: str = 'inputs', tn_output_folder: str = 'outputs', tn_states_folder: str = 'states')

Convergence parameters for the tensor-network based QUBO solver.

Attributes

Same as the base class qtealeaves.convergence_parameters.TNConvergenceParameters.

Attributes (ground-state search)

max_bond_dimensionint, optional

Maximum bond dimension of the tensor network during the ground-state search. The maximum value of the bond dimension is upper bounded by \(2^{n \\mathbin{//} 2}\), where \(n\) is the number of spins in the spin glass system. Default to 8.

min_bond_dimensionint, optional

Minimum bond dimension of the tensor network during the ground-state search. (Suggested for simulation which use single tensor updates) Default to None, which means, it is set to the same value of the maximum bond dimension. This default behavior is specific to the solving of classical optimization problems.

cut_ratiofloat, optional

Control which singular values are truncated during splitting tensors. Either relative values or truncated norm can be considered. This fine tuning can be set via trunc_method. Default to 1e-9

trunc_methodstr, optional

Method use to truncate the singular values. Available:

• R: use cut_ratio Cut ratio \(\\epsilon\) after which the singular values are neglected, i.e. if \(\\lambda_1\) is the bigger singular values then after an SVD we neglect all the singular values such that \(\\lambda_i/\\lambda_1\\leq\\epsilon\).

• N: use maximum norm Maximum value of the norm neglected for the singular values during the trunctation.

Default to ‘R’.

max_iterint, optional

The maximum number of sweeps for the ground-state search. After max_iter the ground-state search ends. Default to 20 sweeps.

abs_deviationfloat, optional

Exit criterion for the ground-state search. If the energy of the current sweep has an absolute per-sweep deviation from the previous sweeps below this threshold, the tensor network optimization ends. Default to 4e-12.

rel_deviationfloat, optional

Exit criterion for ground-state search. If the energy of the current sweep has a relative per-sweep deviation from the previous sweeps below this threshold, the tensor network optimization ends. Default to 1e-12.

n_points_conv_checkint, optional

The number of sweeps used when checking convergence for the ground state search. Exit criteria are not checked until this many sweeps have been performed. Default to 6.

random_sweepsbool, optional

If True, perform random sweeps to optimize the tensors. It could help in escaping local minima for classical combinatorial optimization problems. Default to False.

enable_spacelink_expansionbool, optional

Mode used for sweeping along the tensors during the optimization. If False, standard sweeps without space link expansion are performed to obtain the ground state; if True, the first half of the sweeps use space link expansion, while in the second half the space link expansion is disabled. Note that this second option could automatically change some other convergence parameters, for example the n_points_conv_check for consistency. In that case a warning to the user will be thrown. Default to False.

arnoldi_maxiterint, optional

Maximum number of Lanczos vectors to be used in the eigensolver. Default to 32.

psi0str, optional

The initial tensor network state from which to start the ground-state search for the spin glass Hamiltonian representing the QUBO problem. The available options are:

• random: the initial state of the tensors is initialized randomly;

• driver_product_state: the tensors are initialized in the product state

  \[\begin{split}\\left\\vert{+}\\right\\rangle^{n}\end{split}\]

  with

  \[\begin{split}\\left\\vert{+}\\right\\rangle = \\dfrac{1}{\\sqrt{2}} \\left(\\left\\vert{0}\\right\\rangle + \\left\\vert{1}\\right\\rangle\\right)\end{split}\]

  i.e., in the ground state of the driver Hamiltonian

  \[\begin{split}\\mathcal{H}_{\\scriptscriptstyle driver} = \\sum\\limits_{j=1}^n \\sigma_j^x .\end{split}\]

  Within this option, the product state is exactly constructed with the given initial bond dimension \(\\chi =\) ini_bond_dimension;

Default to ‘random’.

ini_bond_dimensionint, optional

The bond dimension used to construct the initial tensor-network state. Using subspace expansion the bond dimension can grow. Default to None, i.e., the initial bond dimension is initialized to max_bond_dimension.

psi0_noisefloat, optional

Numerical noise to construct the exact initial product state with a given bond dimension. More details can be found in the opt_tooling submodule. Default to 1e-7.

transverse_field_ratiofloat, optional

The ratio of the magnitude of the strength of the classical longitudinal terms (Z-Pauli) to the quantum off-diagonal transverse field terms (X-Pauli) to be added. This ratio controls the magnitude of the transverse field perturbation relative to the classical Hamiltonian, whose ground state must be determined. See the function generate_perturbation_transverse_fields() in the opt_tooling submodule. Default to None, i.e., no transverse fields will be added to the classical Hamiltonian.

randomseedlist[int], optional

Random seeds for reprodubibility and solution diversity. As for qtealeaves compatibility, it has to be a list of 4 integers. Default to [1907, 79, 17, 299].

Attributes (ansatz)

data_typestr | list[str], optional

Data type of the tensors in the chosen ansatz. Available options are

• “Z”: double precision complex (.complex128)

• “C”: single precision complex (.complex64)

• “D”: double precision real (.float64)

• “S”: single precision real (.float32)

• [“DT”, “DT”, …, “DT”]: allows selecting a specific data type for each sweep, where “DT” is a character in {“Z”, “C”, “D”, “S”}.

Default to Z.

tn_ansatzstr, optional

Ansatz to be used for approximating the wave function of the mapped MP4EO Hamiltonian. Available topologies are TTN for Tree Tensor Networks and MPS for Matrix Product States. Default to TTN.

mpo_modeint, optional

MPO representation inside the tensor network simulation. Other options are:

• 0 –> TPO via iTPO

• 1 –> iTPO

• 3 –> iTPO with compression

• 10 –> sparse MPO

• 11 –> indexed sparse MPO

Default to -1, which enables an auto-selection..

use_spinglass_sparse_mpobool, optional

Use a sparse MPO for spin-glass systems. It can be used only with mpo_mode = 10, 11. Default to False.

linalg_backend_librarystr, optional

Library to handle linear algebra operations at the level of the tensors. Available libraries are:

• numpy, both on CPU and GPU;

• pytorch (pass torch), both on CPU and GPU;

Note that qredtea is required for non-trivial backend. Default to ‘numpy’.

devicestr, optional

Device where to run the optimization. Available options are cpu to run the ground-state search on the CPUs, and gpu to run the ground-state search on the GPUs. Also the mix device cgpu is available. Default to cpu.

Attributes (logging)

base_log_dirstr | Path, optional

Base directory for saving log files associated with the QUBOSolver. Default to QUBO_RESULTS.

log_dirstr | Path, optional

Sub-directory in base_log_dir for saving log files associated with qtealeaves I/O processes. Default to qtealeaves.

tn_io_tagstr, optional

Extra common tag to be added at the end of simulation log folders in order to distinguish different simulations. Default to None.

_tn_io_tag_historyList[str]

A list to store tensor-network log-file I/O tag history.

tn_input_folderstr, optional

Name of the folder where to save the input data and parameters for the tensor network ground-state search. If the folder does not exist, it will be automatically created. Default to tn_inputs.

tn_input_filepathstr | Path

Path to the folder for tensor-network input files and logs.

tn_output_folderstr, optional

Name of the folder where to save the output data and log files for the tensor network ground-state search. If the folder does not exist, it will be automatically created. Default to tn_outputs.

tn_output_filepathstr | Path

Path to the folder for tensor-network output files and logs.

tn_states_folderstr, optional

Name of the folder where to save the tensor network states produced. If the folder does not exist, it will be automatically created. Default to tn_states.

tn_state_filestr | Path

Full path to the file where the optimized tensor network state will be stored after optimization.

tn_states_filepathstr | Path

Path to the folder for tensor-network state files and logs.

tn_state_filenamestr

The name of the file where the optimized tensor network state will be stored after optimization.

tn_initial_state_filenamestr

The name of the file where the initial tensor network state will be stored before optimization.

tn_initial_state_filestr | Path

Full path to the file where the initial tensor network state will be stored before optimization.

Notes

An instance of this class must be created and passed to the QUBO solver whenever the QUBO problem is to be solved using tensor networks.

property bond_dim: int

Read-only access to the bond dimension.

property min_bond_dim: int

Read-only access to the minimum bond dimension.

print_details() → None

Prints details about convergence parameters for tensor-network based simulations.

Arguments

None

Returns

None

reset_tn_io_tag() → None

Resets tn_io_tag to its original value (first value in history), and updates folder paths accordingly.

Arguments

None

Returns

None

revert_to_previous_tn_io_tag() → None

Reverts tn_io_tag to its previous value stored in the history stack, and updates folder paths accordingly.

Arguments

None

Returns

None

Raises

ValueError

If there is no previous tag to revert to.

update_tn_io_tag(new_info: str) → None

Updates tn_io_tag with new_info, keeps track of the history and updates I/O folder paths dynamically.

Arguments

new_infostr

The new information to append at the end of tn_io_tag.

Returns

None

class qtealeaves.optimization.qubo_solver.QUBOSolver(qubo_matrix: npt.NDArray[np.floating] | None = None, qubo_offset: float | None = 0.0, qubo_variable_labeling: dict[str, int] | None = None)

Solver for a generic QUBO problem

\[\min_{x \in \{0, 1\}^n} f(\boldsymbol{x})\]

\[f(\boldsymbol{x}) = \boldsymbol{x}^T \mathcal{Q} \boldsymbol{x}\]

where \(\boldsymbol{x}\) is the \(n\)-dimensional binary vector describing the binary configuration of the QUBO decision variables. The QUBO problem is uniquely described by the QUBO matrix \(\mathcal{Q}\), which must be a symmetric or upper triangular real matrix.

This QUBO solver implements different methods to obtain a solution:

• brute-force obtains the exact solution (global optimum) but it’s limited by the number of binaries (\(n \leq 30\));

• exact ground-state search maps the QUBO problem into an equivalent spin glass Hamiltonian and encodes the QUBO solution into the ground state of this Hamiltonian. The ground state is exactly reconstructed by allocating the full Hamiltonian matrix and sorting its diagonal. This method obtains the exact solution (global optimum), but it’s limited by the number of binaries (\(n \leq 30\), depending on the available RAM);

• tensor-network ground-state search also maps the QUBO problem into a corresponding ground-state search of a spin glass Hamiltonian, but the solution is found by applying tensor-network optimization using tools from qtealeaves. This solver is not limited by the number of binaries but by the amount of entanglement needed for the computation.

Parameters

qubo_matrixnumpy.ndarray[float]

The input QUBO problem represented by its QUBO matrix. The input matrix must be either a symmetric or an upper triangular 2D numpy array of real numbers. Only the upper triangular part of the input matrix will be considered, i.e., if \(Q_{ij}\) are the matrix elements of the input QUBO problem, only those for \(i \leq j\) will be used by the solver.

qubo_offsetfloat, optional

The QUBO problem energy cost offset. Ignored during the optimization. Default to 0.0.

qubo_variable_labelingdict[str, int], optional

Labeling scheme from the original problem variable names to the index assign in the QUBO problem reformulation. Keys are variable names, values are the corresponding indices within the one-dimensional embedding. Default to None, i.e., a trivial labeling scheme where the \(j\)-th decision variable takes QUBO index \(j\).

Attributes

qubo_matrixnumpy.ndarray[float]

The QUBO matrix that defines the input QUBO problem.

n_binaries int

Number of decision variables in the QUBO problem.

n_interactionsint

Number of two-body couplings between pairs of decision variables.

spinglass_couplingsdict[str, float | numpy.ndarray[float]]

Dictionary that contains the Hamiltonian couplings of mapped 1-dimensional spin glass model corresponding to the input QUBO problem.

costlist[float]

QUBO cost function values related to the obtained solution space after optimization.

solutionlist[numpy.ndarray[int]]

Solution space obtained through the QUBO solver.

_variables_to_qubo_index_mapdict[str, int]

Map from the original problem variable names to the index assign in the QUBO problem reformulation. Keys are variable names, values are the corresponding indices within the one-dimensional embedding. If empty, the trivial mapping has been considered, i.e., variable \(j\) has index \(j\) in the embedded 1D chain.

statusstr

Status of the solver.

runtimesdict[str, float]

Dictionary that contains runtime information for the profiling of the solver algorithm.

Notes

A very important note for users: if the QUBO matrix describing the problem passed to this class is symmetric, the solver automatically considers only its upper triangular part, automatically doubling the remaining off-diagonal elements, while leaving the diagonal elements unchanged. If instead the matrix is already upper triangular, the solver assumes that the off-diagonal elements have already been multiplied by 2.

The definition of the QUBO problem cost function is thus as follows:

\[f(\boldsymbol{x}) = \sum_{j \leq k} \mathcal{Q}_{jk} x_{j} x_{k}\]

property best_config: numpy.typing.NDArray.<class 'numpy.integer'>

Returns the optimal QUBO problem solution found by the solver.

property best_cost: float

Returns the optimal QUBO cost value found by the solver.

evaluate(binary_configuration: numpy.typing.NDArray.<class 'numpy.integer'>) → float

Evaluates the QUBO cost function for a given binaries configuration. The QUBO cost function is defined as

\[f_{\mathrm{\scriptscriptstyle QUBO}} = \sum_{j < j' = 1}^n Q_{j j'} x_j x_{j'} + \sum_{j=1}^n Q_{jj} x_j\]

where \(n\) is the number of binary decision variables in the QUBO problem and \(\mathcal{Q}\) is the QUBO matrix.

Arguments

binary_configurationnumpy.ndarray[int]

The \(n\)-dimensional bitstring representing the values of the QUBO problem decision variables.

Returns

costfloat

The value of the QUBO cost function evaluated on the given binaries configuration binary_configuration.

Raises

QUBOSolverError

If the input configuration does not match the problem dimension or contains invalid values.

prettyprint() → None

Pretty prints method to visualize the QUBO matrix to standard output.

Arguments

None

Returns

None

classmethod read(filename: str | Path) → Self

Initializes the QUBO problem from an input file.

Arguments

filenamestr | pathlib.Path

The full path to the file containing the QUBO problem as a matrix in a given (allowed) format. A check on file’s extension is performed before reading.

Returns

objqtealeaves.optimization.QUBOSolver

An instance of QUBOSolver initialized with the read QUBO matrix.

Notes

Important note for the users regarding LP file: this method allows you to read QUBO problems from standard LP files, such as those generated by classical solvers like CPLEX. If you don’t trust the input file or the correctness of the QUBO obtained this way, we recommend providing the QUBO matrix directly through the object constructor or via the set_qubo_problem() method.

save_to_file(filename: str | Path, qubo_format: str | None = 'lp') → None

Saves the QUBO problem to a log file in a given qubo_format.

Arguments

filenamestr | pathlib.Path

Full path to the output log file. If the correct extension ``qubo_format``is not provided, it will be added automatically.

qubo_formatstr, optional

The (allowed) extension of the output log file. Currently available extensions are ‘lp’ (suggested), ‘json’ and ‘text’. Default to ‘lp’.

Returns

None

set_qubo_problem(qubo_matrix: numpy.typing.NDArray.<class 'numpy.floating'>, qubo_offset: float | None = 0.0, qubo_variable_labeling: dict[str, int] | None=None) → None

Sets or updates the QUBO matrix, with validation and internal preprocessing.

Arguments

qubo_matrixnumpy.ndarray[float]

The QUBO matrix to be solved.

qubo_offsetfloat, optional

The QUBO problem energy cost offset. Ignored during the optimization. Default to 0.0.

qubo_variable_labelingdict[str, int], optional

Labeling scheme from the original problem variable names to the index assign in the QUBO problem reformulation. Keys are variable names, values are the corresponding indices within the one-dimensional embedding. Default to None, i.e., a trivial labeling scheme where the \(j\)-th decision variable takes QUBO index \(j\).

Returns

None

property solution_space_dim: int

Returns the dimension of the solution space of all possible QUBO decision-variable configurations.

solve(solver: str | None = 'tensor-network', n_solutions: int | None = 1, **kwargs) → None

Solves the QUBO problem using a specific solver.

Arguments

solverstr, optional

Method to solve the QUBO problem. Options are ‘tensor-network’, ‘exact’ and ‘brute-force’. Default to ‘tensor-network’.

n_solutionsint, optional

Number of optimal/near-optimal solutions to compute with the given solver. Default to 1, i.e., the solver searches only for the optimal QUBO solution.

**kwargs

Additional optional arguments, depending on the chosen solver. List of optional arguments can be found in the Details section.

Returns

None

Raises

ValueError

If n_solutions is not a positive integer.

NotImplementedError

If solver is not recognized.

QUBOSetUpError

If tensor-network solver is selected but missing required parameters.

Details

Additional arguments can be passed to this method, depending on the chosen solver. List of available optional arguments:

• renormalize_couplingsbool (quantum-inspired only)

  Whether to renormalize the spin glass Hamiltonian couplings within \(\left[-1, 1\right]\). Default to True.

• tn_conv_paramsQUBOConvergenceParameter (tensor-network only)

  The convergence parameters for the QUBO solver simulation based on tensor-network methods. It contains the main parameters for the ansatz, the ground-state search and the backend at the tensor level. It is required to run the tensor-network solver.

property variables_to_qubo_index_map: dict[str, int]

Returns the mapping between orginal problem variables and QUBO indices.

Optimization tooling

This submodule implements tools and support methods for the QUBO solver class.

The documentation below reports the list of utility functions for the sake of completeness.

class qtealeaves.optimization.opt_tooling.get_exact_spectrum(ham_matrix: Any, number_of_eigenstates: int | None = 1, full_spectrum: bool | None = False)

Computes exact eigenstates and eigenvalues of a many-body classical Hamiltonian.

Arguments

ham_matrixscipy.sparse.csr_matrix | numpy.ndarray

The matrix representing the Hamiltonian operator.

number_of_eigenstatesint, optional

The number of eigenstates to be computed. Default to 1, i.e., only the ground state.

full_spectrumbool, optional

If True, computes the full Hamiltonian spectrum, ignoring number_of_eigenstates. Default to False.

Returns

spectrumlist[list[float, numpy.ndarray]]

The target number of eigenstates and associated exact energies in the Hamiltonian spectrum. The output is a list of exact [energy, eigenstate] sorted in ascending order w.r.t. the energy values.

Notes

The diagonalization implemented here is straightforward (a.k.a., sorting), as it directly follows from the classical nature of the mapped spin glass QUBO Hamiltonian, which is diagonal in the computational basis.