This practical quantum optimisation problem formulation checklist helps business analysts and developers decide whether a scheduling, routing or assignment problem is suitable for a quantum workflow, then encode it in a way that can be tested, compared and maintained. Use it before selecting a solver, building a QUBO, or sending a model to a quantum or hybrid platform.
Overview
Quantum optimisation is not a shortcut around problem definition. The quality of the result depends first on whether the business problem has been translated into precise variables, objectives and constraints. A solver can search the model that you provide, but it cannot correct an ambiguous objective, an infeasible set of rules or a penalty that overwhelms the business priorities.
Many scheduling, routing and assignment problems can be represented using binary variables and a quadratic unconstrained binary optimisation (QUBO) model. A QUBO typically minimises an expression such as xTQx, where each binary variable is either zero or one. Constraints are incorporated into the objective by adding penalty terms. Other workflows preserve constraints in a higher-level model and convert them for a selected solver. The right approach depends on the SDK, solver and model features available at the time of implementation.
Before formulation, ask four screening questions:
- Is the decision discrete? Quantum optimisation models are often a natural fit for yes/no choices, selections, assignments and ordering decisions. Continuous or highly nonlinear components may need discretisation, decomposition or a classical subproblem.
- Can the objective be measured? You need a numerical way to compare candidate solutions, such as cost, distance, lateness, utilisation or service quality.
- Can the constraints be stated precisely? “Create a sensible rota” is not yet a mathematical model. “Each shift receives exactly one qualified worker” is closer to an implementable constraint.
- Is there a credible classical baseline? A quantum experiment should be compared with a suitable classical heuristic, exact solver, constraint solver or current operational process.
If the answer to one of these questions is no, improve the problem definition before choosing QAOA, an annealing workflow, a hybrid solver or another quantum optimisation method. For background on model representations, see QUBO vs Ising Models for Quantum Optimisation.
Checklist by scenario
1. Scheduling and rostering
Typical decision: whether a person, machine, vehicle or job is assigned to a time slot, location or resource.
Define variables: use a binary variable such as x[w,s], where the value is one if worker w is assigned to shift s. Add dimensions only when they represent a real decision. Unnecessary variables increase the model size without improving the schedule.
Define the objective: combine measurable goals, for example preference violations, overtime, uncovered demand, travel time or imbalance between workers. Keep each component visible rather than hiding all priorities in one unexplained score.
Separate hard and soft constraints:
- Hard: a shift must have the required number of workers; a worker cannot be in two places at once; an unqualified worker cannot perform a restricted task.
- Soft: a worker preference is missed; consecutive shifts are undesirable; workload is uneven.
For an exactly-one assignment, a common penalty is A(Σwx[w,s] - 1)2. Expand and combine this with the business objective only after checking that the penalty is large enough to discourage uncovered or multiply covered shifts, but not so large that all meaningful trade-offs disappear.
2. Routing and sequencing
Typical decision: which location follows another, or which vehicle serves which customer in which position.
Define variables: an edge-based formulation might use x[i,j] to indicate that a route travels directly from location i to location j. A position-based formulation might use y[i,p] to indicate that location i occupies route position p. Choose one formulation deliberately; mixing representations without a clear purpose creates redundant or conflicting decisions.
Define the objective: distance, travel time, fuel proxy, toll cost or a weighted combination can be represented as coefficients on selected edges. If the operational objective includes service windows, capacity or multiple vehicles, state how each is represented before building the model.
Check route validity: each customer should be visited as required, each route position should have at most one customer, and disconnected subtours should be prevented or detected. Capacity and time-window rules may require additional variables, penalty terms or a decomposition strategy. A compact model is not useful if it regularly returns an invalid route.
3. Assignment and matching
Typical decision: assign people to tasks, products to facilities, jobs to machines or applicants to available places.
Define variables: let x[i,j] equal one when item i is assigned to option j. Record unavailable pairs explicitly by removing them or assigning a sufficiently restrictive rule in the modelling layer.
Define the objective: use a cost, score or loss for every permitted pairing. For example, the coefficient might represent processing time, skill mismatch, distance or expected penalty. Make the direction clear: are you minimising cost or maximising value? If the solver minimises, convert maximisation into an equivalent minimisation expression.
Encode coverage: “each item receives exactly one option” can be represented by an exactly-one penalty for each item. “Each option has a capacity” needs an inequality or a slack-variable formulation. If the platform does not support that constraint directly, confirm how its modelling interface converts it and test the conversion on small cases.
Reusable formulation template
- Decision: What does one variable mean? Write its index set and domain.
- Objective: What is minimised or maximised? List every term, unit and business owner.
- Hard constraints: Which rules may never be broken?
- Soft constraints: Which rules may be traded off, and what is each violation worth?
- Penalty plan: Which constraints become penalties, and how will their weights be selected?
- Scaling: What are the coefficient ranges after conversion? Are units and magnitudes comparable?
- Feasibility test: Can you construct at least one valid solution independently of the solver?
- Baseline: Which classical method will be used, with what time limit, data and acceptance criteria?
- Validation: How will feasibility, objective value, runtime, repeatability and operational usefulness be measured?
What to double-check
Penalty selection
A penalty should make an invalid solution less attractive than a valid alternative, but “make it very large” is not a reliable method. Estimate the largest improvement the business objective could gain from violating the constraint, then choose a penalty that clearly outweighs that improvement. Test several nearby values rather than trusting one setting.
For soft constraints, the weight should reflect a documented business preference, not merely a number that produces a convenient output. Keep hard-constraint penalties distinct from preference weights so stakeholders can understand the trade-offs.
Coefficient scaling and model conversion
Travel distances, monetary costs, lateness and preference scores may use very different units. Convert them deliberately and record the transformation. Excessively different coefficient magnitudes can make the most important terms dominate the search, while very small terms may have little practical effect. After conversion between constrained, QUBO and Ising forms, inspect the coefficients and verify that the energy ordering still reflects the original objective.
Feasible-solution checks
Write a small validator that accepts a candidate solution and reports every violated rule. Use it on a hand-built feasible solution, randomly generated solutions and solver outputs. Test edge cases: no available worker, insufficient vehicle capacity, duplicate assignments, an empty route, conflicting time windows and a problem with only one valid solution.
Do not infer feasibility from a low objective value alone. A solution can look numerically attractive while violating a constraint that was omitted, mis-indexed or assigned an inadequate penalty.
Solver and SDK limitations
Before implementation, confirm the selected tool’s supported variable types, constraint forms, coefficient ranges, problem-size limits, embedding or compilation requirements, result format and reproducibility controls. Interfaces and capabilities can change between releases. Treat documentation and small end-to-end tests as part of model validation, not as an afterthought.
For a workflow comparison, consult the Quantum SDK Compatibility Matrix. For execution metadata, seeds and backend details, use the Quantum Experiment Reproducibility Checklist.
Common mistakes
- Starting with the algorithm: Selecting QAOA or another method before defining the decision variables reverses the correct order. Formulate and benchmark first.
- Encoding every rule as a hard constraint: Some operational rules are preferences. Making them hard can make the model infeasible or hide valuable trade-offs.
- Using one arbitrary penalty: A penalty copied from another problem has no guaranteed meaning in a new scale, unit system or formulation.
- Ignoring infeasibility: If demand exceeds capacity, the model needs a controlled relaxation, such as unmet-demand variables with an explicit cost. Otherwise the solver may return no useful answer or exploit an unintended workaround.
- Forgetting the business objective: Minimising distance may produce a route that is operationally unacceptable if service windows or vehicle capacity are absent.
- Comparing unlike baselines: Compare equivalent constraints, data, time limits and solution-quality measures. A quantum result should not be judged against a poorly configured classical method.
- Reporting only the best sample: Record the distribution of returned solutions, feasibility rate, objective values and execution conditions. Repeated runs may produce different samples.
- Expanding the model too early: Begin with a reduced, auditable instance. Add vehicles, shifts, objectives and exceptions one at a time so each change can be validated.
For a wider evaluation process, the guidance on benchmarking quantum algorithms against classical methods provides a useful companion checklist.
When to revisit
Use this checklist at the start of every new optimisation project and before each major planning cycle. Revisit the formulation when demand, staffing, vehicle capacity, service rules, costs or business priorities change. A model that was feasible last quarter may become infeasible when any of those inputs move.
Review the implementation whenever the SDK, solver, backend or modelling interface changes. Confirm supported constraints, conversion behaviour, coefficient limits, result fields and reproducibility settings with a small regression suite. Refresh the suite at least twice a year as a maintenance practice, and sooner after a major platform release.
A practical review sequence is:
- Copy the current formulation template into the project record.
- List every variable, objective term, hard constraint and soft constraint.
- Generate one known feasible solution and run the validator.
- Test penalty values and inspect invalid as well as valid outputs.
- Run the same instances with an appropriate classical baseline.
- Record model version, data snapshot, SDK version, solver settings, seeds and backend metadata.
- Obtain operational sign-off before treating a mathematical improvement as a business improvement.
The outcome should be a traceable model, not simply a solver submission. When the formulation is explicit, you can decide objectively whether a quantum, hybrid or classical approach is the best current tool—and return to the same checklist when the problem or platform changes.