Hard problems as bitstrings

Subset sums, tours, satisfiability, one pattern

The Problem

What this chapter makes explicit

Subset sums, travelling tours, and logical clauses look unrelated on a slide deck. They share a computational skeleton: choose an assignment of zeros and ones, evaluate a cost or constraint violation, reject infeasible strings, and compare against classical search or integer programming.

Quantum heuristics enter only after that skeleton exists. If stakeholders cannot explain what each bit means operationally, no device—classical or quantum—can rescue the project.

Concrete questions before any circuit diagram

Which bits encode a feasible decision versus an auxiliary slack variable?
What single scalar summarises quality for feasible assignments?
Which classical solver or enumerator defines the baseline on the same encoding?

The Challenge

Sampling is not optimisation

The Challenge

Where teams get surprised

Heuristic samplers—quantum or classical—may concentrate probability on good bitstrings without placing most mass on the global optimum. That behaviour is not automatically a bug; it is a reason to report full histograms or energy bands instead of a single headline draw.

Another common gap is forgetting feasibility: a low-energy string under a relaxed penalty model can still decode to an illegal business decision. Classical verification after readout is part of the algorithm, not an embarrassment.

Keep the evaluation honest

Feasibility: illegal tours or clauses receive explicit penalties, not silent failures.

Baseline: the same QUBO or score is evaluated classically on identical data.

Readout: measurement shots are budgeted and randomness is reported.

The Solution

Encode, score, sample, verify

The Solution

Pipeline narrative

The same four-stage pipeline is visualised for portfolio-style problems and for routing: variables → Hamiltonian or pseudo-Boolean cost → sampler that shapes a distribution → classical decoder that checks constraints and business logic.

The diagram below is intentionally generic. Treat it as the contract between domain experts and algorithm engineers: every arrow must have an owner and a test.

Encode → cost → sample → readout and classical check

Implementation

Feasibility-aware evaluation pattern

Implementation

The companion workshop walks subset sum, TSP, and 3SAT with small visual sanity checks. The code sketch below shows the shape of a feasibility-aware evaluator: decode bits, reject violations, then score only legal candidates.

Pair with a classical brute check on tiny n before trusting any sampler.

Feasible tour length (conceptual)

import math

def tour_length(bits, dist, n_cities):
    # bits encode a permutation or one-hot layout depending on your QUBO
    path = decode_tour(bits, n_cities)
    if not is_valid_permutation(path):
        return math.inf
    return sum(dist[path[i]][path[i + 1]] for i in range(n_cities))

Example: cities as nodes; the polyline is one candidate tour (closed loop).

Companion code on GitHub

Summary

Numbers that travelled from the older evidence pack

Summary

Portfolio sampler versus exact QUBO sweep

When the same five-asset toy QUBO is scored with a variational QAOA-style loop versus an exhaustive classical sweep, one recorded pair of costs is about −3.62 (variational) versus −9.40 (best feasible classical). The gap illustrates sampler bias, not a universal law.

How to reuse the figure

The landscape plot below is still useful as a teaching artefact: it shows how often sampled energies land near good portfolios. Use it to discuss exploration versus exploitation, not as a competitive benchmark without hardware context.

Sampled energies across portfolio bitstrings

Continue this saga

Next chapter: Circuits, gradients, and variational templates.