Twine QAOA Service¶
In this tutorial we will demonstrate how to solve an optimization problem on quantum devices with the help of the ParityOS TwineQAOAService. We will cover the entire workflow; first the problem is reformulated by encoding it as the ground state of a Spin-Hamiltonian. By using the Parity Twine compilation the logical problem is mapped to a physical device where the respective quantum optimization algorithms can be run. From the output we then map back to the logical qubit configuration corresponding to the solution.
Problem Formulation¶
We will consider an instance of the MaxCut problem which has many important applications, e.g. in circuit design. We are given a graph \(G(V,E)\) with the nodes \(V\) and the edges \(E\) and the goal is to split the nodes into two sets such that as many edges as possible are cut (edges are cut if they connect nodes from different sets). Since it is NP-hard to even approximate the solution to this problem to arbitrary precision, it may be advantageous to solve it with the help of heuristic quantum algorithms. Our graph with 5 nodes and 6 edges connecting them looks as follows: 
We now construct a Hamiltonian for solving the MaxCut problem on this graph so that the solution is encoded in the ground state. We assign a spin variable (qubit) \( s_i, i=1, ..., 5 \) to every node which takes the value +1 if the node belongs to the first set and -1 if it belongs to the second set. Since we want the solution to maximize the number of cut edges we use terms \( H_e \) that give a reward of -1 if the edge e is cut and a penalty +1 if not. This is achieved by simply adding a term \(H_e = s_i s_j\) for every edge \(e=(i, j)\) and thus \( H = \sum_{e \in E} H_e\) which we use to create a ProblemRepresentation instance of the following format
from parityos.bits import get_q
from parityos.operators import Z
from parityos.optimization.problem_representation import ProblemRepresentation
logical_qubits = [get_q(i) for i in range(5)]
# Represent classical binary variables as Pauli Z operators
z = [Z(q) for q in logical_qubits]
# The interaction hamiltonian defining the optimization problems
hamiltonian = (
1 / 2 * z[0] * z[2]
+ 1 / 2 * z[0] * z[4]
+ 1 / 2 * z[1] * z[2]
+ 1 / 2 * z[1] * z[3]
+ 1 / 2 * z[1] * z[4]
+ 1 / 2 * z[2] * z[3]
)
problem = ProblemRepresentation(hamiltonian)
Here each cut edge contributes a negative factor -1/2, while a connected edge contributes a positive factor 1/2 to the overall energy of the problem Hamiltonian.
Parity Twine Compilation¶
Next we use the Parity Twine compilation to map the logical problem onto a physical device. We first set up a device where our problem fits. In this case we choose a 2x3 rectangular device with nearest neighbor interactions
from parityos.devices.device_connectivity import get_rectangular_nearest_neighbor_connectivity
from parityos.devices.device_model import uniform_noiseless_device_from_connectivity
from parityos.operators import CX, RZ, SX, X
# Create a 2 x 3 rectangular nearest neighbor connectivity graph
nearest_neighbor_connectivity = get_rectangular_nearest_neighbor_connectivity(2, 3)
# Create a homogeneous, noiseless device from the connectivity graph with native universal gate set
device_model = uniform_noiseless_device_from_connectivity(
nearest_neighbor_connectivity, [CX, SX, X, RZ]
)
Then we set up a connection to the ParityOS cloud service using your username (password will be prompted or can be supplied via environment variables)
from parityos.services.authentication import InteractiveAuth
from parityos.services.client import HTTPClient
client = HTTPClient(InteractiveAuth("my_parityos_username")) # handles authentication
The Twine compilation is invoked by instantiating the corresponding service, running it by passing the problem and device (and choosing 2 QAOA rounds) and extracting the parametrized QAOA circuit and the relabeling map that maps from the qubits on the physical device to the logical qubits of the problem
from parityos.services.service import TwineQAOAInput, TwineQAOAService
twine_qaoa_service = TwineQAOAService(client)
# Use one of the presets included in your license for `configuration`
result = twine_qaoa_service.run(
TwineQAOAInput(problem=problem, device=device_model, number_of_rounds=2),
configuration="twine-trial",
)
param_circuit = result.parameterized_circuit
physical_to_logical_qubit = result.relabeling_map
In order to run this circuit we first export it to Qiskit format using the parityos-qiskit package (other backends are also available)
from parityos_qiskit.exporters.circuit import export_circuit
qiskit_circuit = export_circuit(param_circuit).circuit
qiskit_circuit.measure_all()
Classical Optimization¶
Next we set up the classical optimization for which it is convenient to first define a helper function to compute the expectation value that is to be optimized from the counts, (i.e. the output of our simulated circuit). Note that counts: dict[str, int] returned from the qiskit circuit simulator is a dictionary mapping each measurement bitstring (qubit assignments) to how many times it was measured in the simulation. The energy expectation value is computed from translating the counts to a logical quantum state, under which the problem Hamiltonian is evaluated.
For this, the Twine compilation also gives us a mapping from physical circuit qubits to logical problem circuits. With this we can construct logical qubit states for each bitstring in the counts. However, the compilation can also add ancilla qubits to the circuit, which have no logical counterpart. Their measurement values can be disregarded for energy evaluation.
Let’s create a function that converts the bare qiskit counts for all physical indices in the circuit to a PauliBasisStateCounts instance, holding counts for each corresponding logical basis state.
from collections.abc import Iterable
from parityos.bits import Qubit
from parityos.operators.pauli_basis import ZBasis
from parityos.states.pauli_state import PauliBasisStateCounts
# indices of physical qubits in the circuit that have a logical counterpart.
qubit_indices = [
idx
for idx, physical_qubit in enumerate(param_circuit.ordered_qubits)
if physical_qubit in physical_to_logical_qubit
]
def physical_to_logical_state_counts(
bitstring_count_pairs: Iterable[tuple[str, int]],
) -> PauliBasisStateCounts[Qubit[int], ZBasis]:
return PauliBasisStateCounts(
{
# only select the bits for the physical qubits that have a logical counterpart
"".join([bitstring[idx] for idx in qubit_indices]): count
for bitstring, count in bitstring_count_pairs
}
)
We can then define the helper function for the expectation value as:
from parityos.evaluators.pauli_evaluator import (
AverageProblemEvaluator,
PauliOperatorEvaluator,
SingleProblemEvaluator,
SoftConstraintEvaluator,
)
evaluator = SingleProblemEvaluator(
operator_evaluator=PauliOperatorEvaluator(),
# violated constraints get an energy penalty of 1
constraint_evaluator=SoftConstraintEvaluator(1),
)
# computes the average of all basis state energies, weighted by their counts
avg_evaluator = AverageProblemEvaluator(evaluator)
def cost_expectation(counts: dict[str, int]) -> float:
logical_state_counts = physical_to_logical_state_counts(counts.items())
return avg_evaluator.evaluate_problem(logical_state_counts, problem)
Now we are able to execute the parametrized circuit with a simulator from Qiskit. For this we will construct a function that can be passed to a classical optimizer:
from qiskit.primitives import StatevectorSampler
def simulate_circuit(parameters):
job = StatevectorSampler().run([(qiskit_circuit, parameters)], shots=512)
counts: dict[str, int] = job.result()[0].data.meas.get_counts()
return cost_expectation(counts)
Starting the optimization multiple times from random initial values for the QAOA parameters improves the performance, where we also set up the parameter bounds for the optimization of the angles.
import math
import numpy as np
parameter_bounds = {param: [-math.pi, math.pi] for param in qiskit_circuit.parameters}
n_starting_points = 5
initial_parameters = [
[np.random.uniform(bound[0], bound[1]) for bound in parameter_bounds.values()]
for _ in range(n_starting_points)
]
With these initial values the classical optimization is invoked with:
from scipy.optimize import minimize
def optimize_parameters(initial_parameters: list[float]) -> tuple[float, list[float]]:
optimization_result = minimize(
simulate_circuit,
x0=initial_parameters,
bounds=[parameter_bounds[param] for param in qiskit_circuit.parameters],
method="Nelder-Mead",
)
return optimization_result.fun, optimization_result.x
optimal_cost = float("inf")
optimal_parameters = initial_parameters[0]
for iteration, initial_parameters_candidate in enumerate(initial_parameters):
# call classical optimization method
cost, parameters = optimize_parameters(initial_parameters_candidate)
print(f"iteration {iteration}: {cost}")
if cost < optimal_cost:
# update parameters when associated cost is lower than previous best
optimal_cost = cost
optimal_parameters = parameters
Here we employ the Nelder-Mead optimizer from scipy, but other methods may also be used.
Solutions of the QAOA algorithm and decoding¶
So far we obtained the optimized parameters for our QAOA circuit. We now run it one more time with these parameters:
# assign optimized parameters to circuit
optimal_qaoa_circuit = qiskit_circuit.assign_parameters(optimal_parameters)
job = StatevectorSampler().run([optimal_qaoa_circuit])
counts: dict[str, int] = job.result()[0].data.meas.get_counts()
We select a number of physical bitstrings which were the most frequent outcomes of the circuit and convert them to logical states:
from operator import itemgetter
n_best_solutions = 5
best_bitstring_count_pairs = sorted(counts.items(), key=itemgetter(1))[n_best_solutions:]
best_logical_states = physical_to_logical_state_counts(best_bitstring_count_pairs)
Finally, the candidate solutions are evaluated on the logical Hamiltonian and we pick the best solution:
evaluator = SingleProblemEvaluator(
operator_evaluator=PauliOperatorEvaluator(),
constraint_evaluator=SoftConstraintEvaluator(1),
)
optimal_cost = float("inf")
logical_solution = next(iter(best_logical_states.state_to_count))
for logical_state in best_logical_states.state_to_count:
cost = evaluator.evaluate_problem(logical_state, problem)
if cost < optimal_cost:
logical_solution = logical_state
optimal_cost = cost
logical_solution.reorder(logical_qubits)
print(f"solution: {logical_solution} with cost {optimal_cost}")
# solution: |00111⟩ with cost -2.0
From the solution we can readily read off which nodes (represented by qubits) of the graph belong to which subset of the partition, e.g.

where red edge labels indicate a cut edge and blue labels indicate an uncut edge. This problem instance is degenerate, meaning that there is more than one optimal solution. Therefore, and due to the probabilistic nature of the quantum algorithm running the code you might get a different result.