Skip to content

Quantum Annealing Problem Generation Specification

Updated: 2026-08-28

Purpose

This specification defines the shared preprocessing layer that turns routing, allocation, collision avoidance, and temporary restrictions for road, low-altitude, high-altitude, and generic domains into solver-ready QUBO data.

The implementation lives in EvoSpikeNet-Core/evospikenet/optimization/. Applications provide domain data; shared QUBO construction, temporary constraints, and solver input formatting remain in Core.

Architecture

flowchart LR
    Source[Road / airspace / operations data] --> Adapter[Domain adapter]
    Adapter --> Problem[OptimizationProblem]
    Restrictions[Temporary restrictions] --> Dynamic[DynamicConstraint]
    Problem --> Builder[QuboProblemBuilder]
    Dynamic --> Builder
    Builder --> Qubo[QuboProblem]
    Qubo --> Solver[D-Wave / OpenJij / Fixstars / Qiskit / SA]
    Solver --> Verify[Application safety validation]

RoadNetworkBuilder obtains directed road links from a cached NetworkX graph or optional OSMnx. OptimizationProblem holds discrete candidates, conflicts, required selections, and temporary restrictions. QuboProblemBuilder produces the problem["qubo"] solver contract as either a dense matrix or a sparse non-zero coefficient dictionary. The application remains responsible for regulation and safety validation before applying a solution.

Road Network Generation

OSM extraction is optional:

pip install 'evospikenet[road]'

Use RoadLocation for an origin, destination, or waypoint. RoadNetworkBuilder.from_osm() downloads a drive graph, snaps each requested location to a road node, and creates every reachable directed pair. It retains directionality because \(d(i,j)\) may differ from \(d(j,i)\) due to one-way roads. Unreachable links are excluded rather than represented as an artificial distance.

The implementation accepts OSMnx 1.x and 2.x bounding-box APIs and supports the OSMnx MultiDiGraph road format. Offline tests use from_graph() with a supplied NetworkX graph and therefore make no network requests.

QUBO and Temporary Restrictions

Candidate cost is represented by \(C_{base} = \sum_i cost_i x_i\). Conflicting route, corridor, or time-slot pairs receive \(P_{conflict}=\lambda_c x_i x_j\). Exactly-one selection groups receive \(P_{exactly-one}=\lambda_g(\sum_{i \in G}x_i-1)^2\).

DynamicConstraint supports active time windows and two behaviors:

  • hard: add a prohibitive penalty and reject the candidate during solution validation.
  • soft: add a tunable operational risk or detour cost.

Restrictions can select candidates by explicit ID or by attributes such as road class, corridor, altitude layer, or assigned resource.

Scope Boundary

QUBO representation and scaling

QuboProblemBuilder.build() accepts representation="dense" or representation="sparse". The default is dense for compatibility. Sparse output uses {(row, column): coefficient} and omits zero coefficients; QuboProblem.to_dense() and to_sparse() provide explicit conversion at integration boundaries.

Large problems should be generated as sparse dictionaries and passed directly to D-Wave, OpenJij, and Amplify-style plugins that support dictionary QUBOs. Qiskit-style dense backends materialize a dense matrix only at their boundary. If every vehicle has exactly one safe candidate, an exact direct assignment can avoid solver search, but it must still pass HPDBN and safety validation. Conflict construction must also be indexed by shared vehicle, time slot, or overlapping trajectory rather than comparing every candidate pair.

The initial shared builder compiles candidate selection, conflict avoidance, exactly-one selection, and dynamic restrictions. Full vehicle-routing constraints such as tour continuity, depot return, subtour elimination, capacity, and time windows require a road-specific encoder after candidate reduction. Do not encode an entire city road graph directly into QUBO; reduce it to operational candidate routes first.

All QUBO output is compatible with dwave, openjij, fixstars_amplify, qiskit, and classical fallback backends. See HPDBN External Optimization for the asynchronous execution and safety contract.