# This code is part of a Qiskit project.
#
# (C) Copyright IBM 2019, 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.
"""Quadratic expression interface."""
from __future__ import annotations
from collections import defaultdict
from typing import Any
import numpy as np
from numpy import ndarray
from scipy.sparse import coo_matrix, dok_matrix, spmatrix, tril, triu
from ..exceptions import QiskitOptimizationError
from ..infinity import INFINITY
from .linear_expression import ExpressionBounds
from .quadratic_program_element import QuadraticProgramElement
[docs]
class QuadraticExpression(QuadraticProgramElement):
"""Representation of a quadratic expression by its coefficients."""
def __init__(
self,
quadratic_program: Any,
coefficients: (
ndarray | spmatrix | list[list[float]] | dict[tuple[int | str, int | str], float]
),
) -> None:
"""Creates a new quadratic expression.
The quadratic expression can be defined via an array, a list, a sparse matrix, or a
dictionary that uses variable names or indices as keys and stores the values internally as a
dok_matrix. We stores values in a compressed way, i.e., values at symmetric positions are
summed up in the upper triangle. For example, {(0, 1): 1, (1, 0): 2} -> {(0, 1): 3}.
Args:
quadratic_program: The parent QuadraticProgram.
coefficients: The (sparse) representation of the coefficients.
"""
super().__init__(quadratic_program)
self.coefficients = coefficients
def __getitem__(self, key: tuple[int | str, int | str]) -> float:
"""Returns the coefficient where i, j can be a variable names or indices.
Args:
key: The tuple of indices or names of the variables corresponding to the coefficient.
Returns:
The coefficient corresponding to the addressed variables.
"""
i, j = key
if isinstance(i, str):
i = self.quadratic_program.variables_index[i]
if isinstance(j, str):
j = self.quadratic_program.variables_index[j]
return self.coefficients[min(i, j), max(i, j)]
def __setitem__(self, key: tuple[int | str, int | str], value: float) -> None:
"""Sets the coefficient where i, j can be a variable names or indices.
Args:
key: The tuple of indices or names of the variables corresponding to the coefficient.
value: The coefficient corresponding to the addressed variables.
"""
i, j = key
if isinstance(i, str):
i = self.quadratic_program.variables_index[i]
if isinstance(j, str):
j = self.quadratic_program.variables_index[j]
self.coefficients[min(i, j), max(i, j)] = value
def _coeffs_to_dok_matrix(
self,
coefficients: (
ndarray | spmatrix | list[list[float]] | dict[tuple[int | str, int | str], float]
),
) -> dok_matrix:
"""Maps given coefficients to a dok_matrix.
Args:
coefficients: The coefficients to be mapped.
Returns:
The given coefficients as a dok_matrix
Raises:
QiskitOptimizationError: if coefficients are given in unsupported format.
"""
if isinstance(coefficients, (list, ndarray, spmatrix)):
return self._triangle_matrix(dok_matrix(coefficients))
elif isinstance(coefficients, dict):
coeffs: dict[tuple[int, int], float] = defaultdict(float)
for (i, j), value in coefficients.items():
if value == 0:
continue
if isinstance(i, str):
i = self.quadratic_program.variables_index[i]
if isinstance(j, str):
j = self.quadratic_program.variables_index[j]
if i > j:
i, j = j, i
coeffs[i, j] += value
n = self.quadratic_program.get_num_vars()
if coeffs:
rows, cols, values = zip(*((i, j, v) for (i, j), v in coeffs.items()))
ret = dok_matrix(coo_matrix((values, (rows, cols)), shape=(n, n)).todok())
else:
ret = dok_matrix((n, n))
return ret
else:
raise QiskitOptimizationError(f"Unsupported format for coefficients: {coefficients}")
@staticmethod
def _triangle_matrix(mat: dok_matrix) -> dok_matrix:
lower = tril(mat, -1, format="dok")
# `todok` is necessary because subtraction results in other format
return (mat + lower.transpose() - lower).todok()
@staticmethod
def _symmetric_matrix(mat: dok_matrix) -> dok_matrix:
upper = triu(mat, 1, format="dok") / 2
# `todok` is necessary because subtraction results in other format
return (mat + upper.transpose() - upper).todok()
@property
def coefficients(self) -> dok_matrix:
"""Returns the coefficients of the quadratic expression.
Returns:
The coefficients of the quadratic expression.
"""
return self._coefficients
@coefficients.setter
def coefficients(
self,
coefficients: (
ndarray | spmatrix | list[list[float]] | dict[tuple[int | str, int | str], float]
),
) -> None:
"""Sets the coefficients of the quadratic expression.
Args:
coefficients: The coefficients of the quadratic expression.
"""
self._coefficients = self._coeffs_to_dok_matrix(coefficients)
[docs]
def to_array(self, symmetric: bool = False) -> ndarray:
"""Returns the coefficients of the quadratic expression as array.
Args:
symmetric: Determines whether the output is in a symmetric form or not.
Returns:
An array with the coefficients corresponding to the quadratic expression.
"""
coeffs = self._symmetric_matrix(self._coefficients) if symmetric else self._coefficients
return coeffs.toarray()
[docs]
def to_dict(
self, symmetric: bool = False, use_name: bool = False
) -> dict[tuple[int, int] | tuple[str, str], float]:
"""Returns the coefficients of the quadratic expression as dictionary, either using tuples
of variable names or indices as keys.
Args:
symmetric: Determines whether the output is in a symmetric form or not.
use_name: Determines whether to use index or names to refer to variables.
Returns:
An dictionary with the coefficients corresponding to the quadratic expression.
"""
coeffs = self._symmetric_matrix(self._coefficients) if symmetric else self._coefficients
if use_name:
return {
(
self.quadratic_program.variables[i].name,
self.quadratic_program.variables[j].name,
): v
for (i, j), v in coeffs.items()
}
else:
return {(int(i), int(j)): v for (i, j), v in coeffs.items()}
[docs]
def evaluate(self, x: ndarray | list | dict[int | str, float]) -> float:
"""Evaluate the quadratic expression for given variables: x * Q * x.
Args:
x: The values of the variables to be evaluated.
Returns:
The value of the quadratic expression given the variable values.
"""
x = self._cast_as_array(x)
# compute x * Q * x for the quadratic expression
val = x @ self.coefficients @ x
# return the result
return val
[docs]
def evaluate_gradient(self, x: ndarray | list | dict[int | str, float]) -> ndarray:
"""Evaluate the gradient of the quadratic expression for given variables.
Args:
x: The values of the variables to be evaluated.
Returns:
The value of the gradient quadratic expression given the variable values.
"""
x = self._cast_as_array(x)
# compute (Q' + Q) * x for the quadratic expression
val = (self.coefficients.transpose() + self.coefficients) @ x
# return the result
return val
def _cast_as_array(self, x: ndarray | list | dict[int | str, float]) -> dok_matrix | np.ndarray:
"""Converts input to an array if it is a dictionary or list."""
if isinstance(x, dict):
x_aux = np.zeros(self.quadratic_program.get_num_vars())
for i, v in x.items():
if isinstance(i, str):
i = self.quadratic_program.variables_index[i]
x_aux[i] = v
x = x_aux
if isinstance(x, list):
x = np.array(x)
return x
@property
def bounds(self) -> ExpressionBounds:
"""Returns the lower bound and the upper bound of the quadratic expression
Returns:
The lower bound and the upper bound of the quadratic expression
Raises:
QiskitOptimizationError: if the quadratic expression contains any unbounded variable
"""
l_b = u_b = 0.0
for (ind1, ind2), coeff in self.to_dict().items():
x = self.quadratic_program.get_variable(ind1)
if x.lowerbound == -INFINITY or x.upperbound == INFINITY:
raise QiskitOptimizationError(
f"Quadratic expression contains an unbounded variable: {x.name}"
)
y = self.quadratic_program.get_variable(ind2)
if y.lowerbound == -INFINITY or y.upperbound == INFINITY:
raise QiskitOptimizationError(
f"Quadratic expression contains an unbounded variable: {y.name}"
)
lst = []
if ind1 == ind2:
if x.lowerbound * x.upperbound <= 0.0:
# lower bound and upper bound have different signs
lst.append(0.0)
lst.extend([x.lowerbound**2, x.upperbound**2])
else:
lst.extend(
[
x.lowerbound * y.lowerbound,
x.lowerbound * y.upperbound,
x.upperbound * y.lowerbound,
x.upperbound * y.upperbound,
]
)
lst2 = [coeff * val for val in lst]
l_b += min(lst2)
u_b += max(lst2)
return ExpressionBounds(lowerbound=l_b, upperbound=u_b)
def __repr__(self):
# pylint: disable=cyclic-import
from ..translators.prettyprint import DEFAULT_TRUNCATE, expr2str
return f"<{self.__class__.__name__}: {expr2str(quadratic=self, truncate=DEFAULT_TRUNCATE)}>"
def __str__(self):
# pylint: disable=cyclic-import
from ..translators.prettyprint import expr2str
return f"{expr2str(quadratic=self)}"