Optimization Problems¶
ParityOS has dedicated classes for formulating (discrete) binary optimization problems that can be solved on quantum computers using variational algorithms such as QAOA or VQE. Cost functions are assumed to be functions that map a set of classical binary values to a real number:
with \(x_i \in \{0, 1\}\) and \(a, b_i, c_{ij}, \ldots \in \mathbb{R}\).
The cost function is represented by a (classical) Hamiltonian in the Pauli Z basis, where every classical binary variable is appropriately replaced by a Pauli Z operator. A possible encoding scheme is e.g.:
where \(\bar{Z}_i = (1 - Z_i) / 2\) and \(Z_i\) the Pauli Z operator acting on qubit \(i\). The eigenstates of \(H\) are all computational basis states \(|x_0 \ldots x_N\rangle\) and the solution to the optimization problem is the eigenstate with the smallest eigenvalue. Its corresponding bitstring \(x^*_0, \ldots, x^*_N\) is the solution to the classical discrete optimization problem. Other encoding schemes are also possible, but the Hamiltonian must contain only Pauli Z operators.
Constraints¶
Optimization problems can be constrained or unconstrained, with different kinds of constraint types. Since the binary optimization variables are encoded as Pauli Z operators, constraints must also be formulated entirely in terms of Pauli Z operators.
ParityOS offers an abstract Constraint base class with the abstract method is_satisfied that takes a PauliBasisState in the Pauli Z basis and returns whether this state fulfills the constraint.
ParityOS also offers two concrete built-in implementations:
ProductConstraint: A constraint on the parity of a product of Pauli Z operators.SumConstraint: A constraint on the value of a polynomial of Pauli Z operators, which can be an equality or an inequality.
Note
There are no inequality product constraints: a product of Pauli Z operators can only take the values +1 and -1, which is fully described by the parity of a ProductConstraint.
Product Constraints¶
The class ProductConstraint describes constraints on the parity of the qubits of a PauliBasisState. The constraint is defined by:
operator_product: AOperatorProductofZoperators.parity: AParity, which may beeven(+1in spin value) orodd(-1in spin value).
For a state to fulfill a product constraint, the constraint qubits must all be contained in the state and their parity must be the same as the constraint’s parity.
Sum Constraints¶
The class SumConstraint describes constraints on sums of weighted parities of the qubits of a PauliBasisState. The constraint is defined by:
operator_polynomial: AnOperatorPolynomialof Pauli Z operators.sense: AnConstraintSense, which may be<ConstraintSense.EQUAL>(==, the default),<ConstraintSense.LESS_EQUAL>(<=) or<ConstraintSense.GREATER_EQUAL>(>=).
For a state to fulfill a sum constraint, its expectation value for the polynomial must be equal to, less than or equal to, or greater than or equal to the constraint’s value, depending on the sense. Strict inequalities are not supported.
Note
Inequality sum constraints can not be encoded by a ParityMapping yet: ParityMapping.encode_problem raises a ParityOSNotSupportedError for them.
Problem Representation¶
Finally, the class ProblemRepresentation represents an optimization problem as a combined representation of
A problem Hamiltonian
A set of product constraints
A set of sum constraints, which may be equalities or inequalities
If both constraint sets are empty, the problem is unconstrained.
Note
The ParityOS services do not support inequality sum constraints yet. Passing a problem with inequality sum constraints as service input raises a ParityOSNotSupportedError.
Many services like the Layout Service or the Twine QAOA Service take ProblemRepresentation instances as job input or return them in their job results.
Example¶
from parityos.bits import get_q
from parityos.operators.elementary_operator import Z
from parityos.optimization.constraint import ConstraintSense, ProductConstraint, SumConstraint
from parityos.optimization.problem_representation import ProblemRepresentation
from parityos.utils.misc_utils import Parity
# Create 5 logical qubits with ids [0, 1, 2, 3, 4]
qubits = [get_q(i) for i in range(5)]
# Create 5 logical Pauli-Z Operators
z = [Z(get_q(i)) for i in range(5)]
# The interaction hamiltonian defining the optimization problems
hamiltonian = (
-2 * z[0] * z[1]
- 3 * z[0] * z[4]
+ z[1] * z[3]
+ 2 * z[3] * z[4]
- 3 * z[0] * z[1] * z[2]
+ 1.5 * z[2] * z[3] * z[4]
)
# Explicit product constraints
product_constraints = [
ProductConstraint(z[0] * z[1] * z[3]), # Even parity
ProductConstraint(z[1] * z[2] * z[4], Parity.odd),
]
# Sum constraints: an equality (the default sense) and two inequalities
sum_constraints = [
SumConstraint(z[0] + 2 * z[2] - z[4], 1),
SumConstraint(z[1] + z[3] + z[4], 1, ConstraintSense.LESS_EQUAL),
SumConstraint(z[0] - z[2], 0, ConstraintSense.GREATER_EQUAL),
]
# The complete problem with interaction hamiltonian and explicit constraints
problem = ProblemRepresentation(
hamiltonian,
product_constraints=product_constraints,
sum_constraints=sum_constraints,
)
assert problem.qubits == set(qubits)