Source code for qiskit_optimization.algorithms.recursive_minimum_eigen_optimizer

# This code is part of a Qiskit project.
#
# (C) Copyright IBM 2020, 2025.
#
# This code is licensed under the Apache License, Version 2.0. You may
# obtain a copy of this license in the LICENSE.txt file in the root directory
# of this source tree or at http://www.apache.org/licenses/LICENSE-2.0.
#
# Any modifications or derivative works of this code must retain this
# copyright notice, and modified files need to carry a notice indicating
# that they have been altered from the originals.

"""A recursive minimal eigen optimizer in Qiskit optimization module."""
from __future__ import annotations

from copy import deepcopy
from enum import Enum
from typing import cast

import numpy as np

from ..converters.quadratic_program_to_qubo import QuadraticProgramConverter, QuadraticProgramToQubo
from ..exceptions import QiskitOptimizationError
from ..minimum_eigensolvers import NumPyMinimumEigensolver
from ..problems import Variable
from ..problems.quadratic_program import QuadraticProgram
from ..utils.validation import validate_min
from .minimum_eigen_optimizer import MinimumEigenOptimizationResult, MinimumEigenOptimizer
from .optimization_algorithm import (
    OptimizationAlgorithm,
    OptimizationResult,
    OptimizationResultStatus,
)


[docs] class IntermediateResult(Enum): """ Defines whether the intermediate results of :class:`~qiskit_optimization.algorithms.RecursiveMinimumEigenOptimizer` at each iteration should be stored and returned to the end user. """ NO_ITERATIONS = 0 """No intermediate results are stored.""" LAST_ITERATION = 1 """Only results from the last iteration are stored.""" ALL_ITERATIONS = 2 """All intermediate results are stored."""
[docs] class RecursiveMinimumEigenOptimizationResult(OptimizationResult): """Recursive Eigen Optimizer Result.""" def __init__( # pylint: disable=too-many-positional-arguments self, x: list[float] | np.ndarray, fval: float, variables: list[Variable], status: OptimizationResultStatus, replacements: dict[str, tuple[str, int]], history: tuple[list[MinimumEigenOptimizationResult], OptimizationResult], ) -> None: """ Constructs an instance of the result class. Args: x: the optimal value found in the optimization. fval: the optimal function value. variables: the list of variables of the optimization problem. status: the termination status of the optimization algorithm. replacements: a dictionary of substituted variables. Key is a variable being substituted, value is a tuple of substituting variable and a weight, either 1 or -1. history: a tuple containing intermediate results. The first element is a list of :class:`~qiskit_optimization.algorithms.MinimumEigenOptimizerResult` obtained by invoking :class:`~qiskit_optimization.algorithms.MinimumEigenOptimizer` iteratively, the second element is an instance of :class:`~qiskit_optimization.algorithm.OptimizationResult` obtained at the last step via `min_num_vars_optimizer`. """ super().__init__(x, fval, variables, status, None) self._replacements = replacements self._history = history @property def replacements(self) -> dict[str, tuple[str, int]]: """ Returns a dictionary of substituted variables. Key is a variable being substituted, value is a tuple of substituting variable and a weight, either 1 or -1.""" return self._replacements @property def history( self, ) -> tuple[list[MinimumEigenOptimizationResult], OptimizationResult]: """ Returns intermediate results. The first element is a list of :class:`~qiskit_optimization.algorithms.MinimumEigenOptimizerResult` obtained by invoking :class:`~qiskit_optimization.algorithms.MinimumEigenOptimizer` iteratively, the second element is an instance of :class:`~qiskit_optimization.algorithm.OptimizationResult` obtained at the last step via `min_num_vars_optimizer`. """ return self._history
[docs] class RecursiveMinimumEigenOptimizer(OptimizationAlgorithm): """A meta-algorithm that applies a recursive optimization. The recursive minimum eigen optimizer applies a recursive optimization on top of :class:`~qiskit_optimization.algorithms.OptimizationAlgorithm`. This optimizer can use :class:`~qiskit_optimization.algorithms.MinimumEigenOptimizer` as an optimizer that is called at each iteration. The algorithm is introduced in [1]. Examples: Outline of how to use this class: .. code-block:: python from qiskit_optimization.minimum_eigensolvers import QAOA from qiskit_optimization.problems import QuadraticProgram from qiskit_optimization.algorithms import ( MinimumEigenOptimizer, RecursiveMinimumEigenOptimizer ) problem = QuadraticProgram() # specify problem here # specify minimum eigen solver to be used, e.g., QAOA qaoa = QAOA(...) internal_optimizer = MinimumEigenOptimizer(qaoa) optimizer = RecursiveMinimumEigenOptimizer(internal_optimizer) result = optimizer.solve(problem) References: [1] Bravyi et al. (2019), Obstacles to State Preparation and Variational Optimization from Symmetry Protection. `arXiv:1910.08980 <http://arxiv.org/abs/1910.08980>`_ """ def __init__( # pylint: disable=too-many-positional-arguments self, optimizer: OptimizationAlgorithm, min_num_vars: int = 1, min_num_vars_optimizer: OptimizationAlgorithm | None = None, penalty: float | None = None, history: IntermediateResult | None = IntermediateResult.LAST_ITERATION, converters: QuadraticProgramConverter | list[QuadraticProgramConverter] | None = None, ) -> None: """Initializes the recursive minimum eigen optimizer. This initializer takes an ``OptimizationAlgorithm``, the parameters to specify until when to to apply the iterative scheme, and the optimizer to be applied once the threshold number of variables is reached. Args: optimizer: The optimizer to use in every iteration. min_num_vars: The minimum number of variables to apply the recursive scheme. If this threshold is reached, the min_num_vars_optimizer is used. min_num_vars_optimizer: This optimizer is used after the recursive scheme for the problem with the remaining variables. Default value is :class:`~qiskit_optimization.algorithms.MinimumEigenOptimizer` created on top of :class:`~qiskit_optimization.minimum_eigensolvers.NumPyMinimumEigensolver`. penalty: The factor that is used to scale the penalty terms corresponding to linear equality constraints. history: Whether the intermediate results are stored. Default value is :py:obj:`~IntermediateResult.LAST_ITERATION`. converters: The converters to use for converting a problem into a different form. By default, when None is specified, an internally created instance of :class:`~qiskit_optimization.converters.QuadraticProgramToQubo` will be used. Raises: QiskitOptimizationError: In case of invalid parameters (num_min_vars < 1). TypeError: When there one of converters is an invalid type. """ validate_min("min_num_vars", min_num_vars, 1) self._optimizer = optimizer self._min_num_vars = min_num_vars if min_num_vars_optimizer: self._min_num_vars_optimizer = min_num_vars_optimizer else: self._min_num_vars_optimizer = MinimumEigenOptimizer(NumPyMinimumEigensolver()) self._penalty = penalty self._history = history self._converters = self._prepare_converters(converters, penalty)
[docs] def get_compatibility_msg(self, problem: QuadraticProgram) -> str: """Checks whether a given problem can be solved with this optimizer. Checks whether the given problem is compatible, i.e., whether the problem can be converted to a QUBO, and otherwise, returns a message explaining the incompatibility. Args: problem: The optimization problem to check compatibility. Returns: A message describing the incompatibility. """ return QuadraticProgramToQubo.get_compatibility_msg(problem)
[docs] def solve(self, problem: QuadraticProgram) -> OptimizationResult: """Tries to solve the given problem using the recursive optimizer. Runs the optimizer to try to solve the optimization problem. Args: problem: The problem to be solved. Returns: The result of the optimizer applied to the problem. Raises: QiskitOptimizationError: Incompatible problem. QiskitOptimizationError: Infeasible due to variable substitution """ self._verify_compatibility(problem) # convert problem to QUBO, this implicitly checks if the problem is compatible problem_ = self._convert(problem, self._converters) problem_ref = deepcopy(problem_) # run recursive optimization until the resulting problem is small enough replacements: dict[str, tuple[str, int]] = {} optimization_results: list[OptimizationResult] = [] while problem_.get_num_vars() > self._min_num_vars: # solve current problem with optimizer res = self._optimizer.solve(problem_) # type: OptimizationResult if self._history == IntermediateResult.ALL_ITERATIONS: optimization_results.append(res) # analyze results to get strongest correlation correlations = res.get_correlations() i, j = self._find_strongest_correlation(correlations) x_i = problem_.variables[i].name x_j = problem_.variables[j].name if correlations[i, j] > 0: # set x_i = x_j problem_ = problem_.substitute_variables(variables={i: (j, 1)}) if problem_.status == QuadraticProgram.Status.INFEASIBLE: raise QiskitOptimizationError("Infeasible due to variable substitution") replacements[x_i] = (x_j, 1) else: # set x_i = 1 - x_j, this is done in two steps: # 1. set x_i = 1 + x_i # 2. set x_i = -x_j # 1a. get additional offset constant = problem_.objective.constant constant += problem_.objective.linear[i] constant += problem_.objective.quadratic[i, i] problem_.objective.constant = constant # 1b. get additional linear part for k in range(problem_.get_num_vars()): coeff = problem_.objective.linear[k] if k == i: coeff += 2 * problem_.objective.quadratic[i, k] else: coeff += problem_.objective.quadratic[i, k] # set new coefficient if not too small if np.abs(coeff) > 1e-10: problem_.objective.linear[k] = coeff else: problem_.objective.linear[k] = 0 # 2. replace x_i by -x_j problem_ = problem_.substitute_variables(variables={i: (j, -1)}) if problem_.status == QuadraticProgram.Status.INFEASIBLE: raise QiskitOptimizationError("Infeasible due to variable substitution") replacements[x_i] = (x_j, -1) # solve remaining problem result = self._min_num_vars_optimizer.solve(problem_) # unroll replacements var_values = {} for i, x in enumerate(problem_.variables): var_values[x.name] = result.x[i] def find_value(x, replacements, var_values): if x in var_values: # if value for variable is known, return it return var_values[x] elif x in replacements: # get replacement for variable (y, sgn) = replacements[x] # find details for replacing variable value = find_value(y, replacements, var_values) # construct, set, and return new value var_values[x] = value if sgn == 1 else 1 - value return var_values[x] else: raise QiskitOptimizationError("Invalid values!") # loop over all variables to set their values for x_i in problem_ref.variables: if x_i.name not in var_values: find_value(x_i.name, replacements, var_values) # build history before any translations are applied # min_eigen_results is an empty list if history is set to NO or LAST. history = ( optimization_results, None if self._history == IntermediateResult.NO_ITERATIONS else result, ) # construct result x_v = np.array([var_values[x_aux.name] for x_aux in problem_ref.variables]) return cast( RecursiveMinimumEigenOptimizationResult, self._interpret( x=x_v, converters=self._converters, problem=problem, result_class=RecursiveMinimumEigenOptimizationResult, replacements=replacements, history=history, ), )
@staticmethod def _find_strongest_correlation(correlations): # get absolute values and set diagonal to -1 to make sure maximum is always on off-diagonal abs_correlations = np.abs(correlations) for i in range(len(correlations)): abs_correlations[i, i] = -1 # get index of maximum (by construction on off-diagonal) m_max = np.argmax(abs_correlations.flatten()) # translate back to indices i = int(m_max // len(correlations)) j = int(m_max - i * len(correlations)) return (i, j)