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:

\[f(x_0, \ldots, x_N) = a + \sum_i b_i x_i + \sum_{ij} c_{ij} x_i x_j + \ldots\]

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.:

\[H(\bar{Z}_0, \ldots, \bar{Z}_N) = a + \sum_i b_i \bar{Z}_i + \sum_{ij} c_{ij} \bar{Z}_i \bar{Z}_j + \ldots\]

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.

Product Constraints

The class ProductConstraint describes constraints on the parity of the qubits of a PauliBasisState. The constraint is defined by

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

For a state to fulfill a sum constraint, its expectation value for the polynomial must be that same as the constraint’s value.

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

If both constraint sets are empty, the problem is unconstrained.

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 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),
]
# A sum constraint between 3 logical qubits
sum_constraint = SumConstraint(z[0] + 2 * z[2] - z[4], 1)

# The complete problem with interaction hamiltonian and explicit constraints
problem = ProblemRepresentation(
    hamiltonian,
    product_constraints=product_constraints,
    sum_constraints=sum_constraint,
)
assert problem.qubits == set(qubits)