TSPProblem

class TSPProblem(cost_matrix, *, start_city=0, encoding='one_hot', constraint_penalty=4.0, objective_weight=1.0)

Bases: _RoutingProblemBase

Traveling Salesman Problem for QAOA.

Supports two encodings:

• "one_hot" — assignment-matrix encoding with W-state initialisation and an XY mixer that preserves the one-hot constraint per time slot. Qubit count: (n-1)².

• "binary" — log-encoded slot bits (CE-QAOA binary) with Hadamard initialisation and a transverse-field mixer. Qubit count: (n-1) · ⌈log₂(n)⌉ before quadratization.

Parameters:

• cost_matrix (ndarray[tuple[Any, ...], dtype[floating]]) – Symmetric distance/cost matrix of shape (n, n).

• start_city (int) – Index of the fixed start city. Defaults to 0.

• encoding (Literal['one_hot', 'binary']) – "one_hot" or "binary". Defaults to "one_hot".

• constraint_penalty (float) – Constraint penalty strength. Defaults to 4.0.

• objective_weight (float) – Objective weight. Defaults to 1.0.

Attributes Summary

binary_config
decode_fn	Map a measurement bitstring to a domain-level solution.
encoding
feasible_dimension	Size of the feasible subspace, equal to (n-1)!.
recommended_initial_state	Recommended initial quantum state for this problem.

Methods Summary

compute_energy(bitstring)	Evaluate the objective energy for a bitstring.
is_feasible(bitstring)	Check whether a bitstring represents a feasible solution.
repair_infeasible_bitstring(bitstring)	Repair an infeasible bitstring into a feasible one.

Attributes Documentation

binary_config

decode_fn

encoding

feasible_dimension

Size of the feasible subspace, equal to (n-1)!.

recommended_initial_state

Methods Documentation

compute_energy(bitstring)

Evaluate the objective energy for a bitstring.

Defaults to None (unknown).

Return type:

float | None

is_feasible(bitstring)

Check whether a bitstring represents a feasible solution.

Defaults to True (unconstrained).

Return type:

bool

repair_infeasible_bitstring(bitstring)

Repair an infeasible bitstring into a feasible one.

Returns:

• repaired_bitstring: The feasible bitstring after repair.

• decoded: Domain-level solution (e.g. tour list, routes), or None if unavailable.

• energy: Objective value of the repaired solution, or None if unknown.

Return type:

tuple[str, Any, float]

The default implementation returns the bitstring unchanged.