Deadline aware hybrid optimization for ISP traffic engineering

Abstract

A routing optimizer can return a good configuration after the conditions that justified it have disappeared. This paper formulates a finite-horizon decision problem in which an ISP chooses a traffic subset, solver and computation budget according to the benefit remaining after computation and deployment.

Quantum annealing or a gate-based optimizer may generate candidates. A classical acceptance layer checks capacity, transition safety, freshness and whether the change is worth applying. The paper gives conditional mathematical guarantees and a small, reproducible reference implementation. It reports no quantum hardware results or real ISP measurements.

The research question

The original question was whether quantum computing could help identify efficient routing patterns across a network. Superposition does not let us observe every possible route at once: measurement returns samples, and obtaining useful samples requires an algorithm and repeated execution.

The more practical question is whether a hybrid controller can choose what to optimize, which solver to use and how long to wait while an answer is still useful. This is control-plane optimization of classical IP traffic. TCP remains responsible for transport reliability and congestion control.

What the paper proves

• A deadline break-even condition under a constant-gain model.
• An exact worst-case link-load envelope for a specified asynchronous fluid transition model.
• Capacity safety for concurrent, disjoint jobs with explicit reservations.
• A sufficient QUBO penalty that makes every global minimum feasible and surrogate-optimal, provided a feasible allocation exists.
• An expected-improvement certificate for a frozen finite menu of policies evaluated on independent, representative validation scenarios.

These are conditional proofs. A feasible final allocation can still overload a link during installation, so the paper includes a counterexample and a safe staged alternative within its model. Packet-level behavior, traffic bursts and inconsistent forwarding updates require additional analysis.

Qubits and scaling

One example encoding has 100 aggregate demands, four candidate paths per demand and 50 links with 100 units of residual capacity. It uses 750 binary variables. A direct QAOA representation would need 750 data qubits before implementation overhead. This is not a reliable physical-qubit estimate or a minimum requirement.

Physical resources depend on the circuit, connectivity, precision, error correction and target failure probability. Scaling the architecture relies on classical traffic aggregation, candidate-path generation, bounded subproblems and coordinated capacity reservations. Decomposition can sacrifice global solution quality; more qubits do not remove that trade-off.

Existing work and proposed contribution

Quantum routing, QUBO formulations, demand decomposition, congestion-free network updates and solver selection already have related work. The paper compares these areas and discusses a published routing patent application. It does not claim priority over them.

The narrower hypothesis is that choosing the traffic subset, solver and budget together, using the useful time remaining after deployment, can improve operational outcomes. This still needs testing against strong classical alternatives with equal accounting for all costs.

Reproducibility and limits

The repository contains the manuscript, LaTeX source, generated examples, review notes and 16 passing tests. The tests include exhaustive checks on 64 seeded small routing instances. They are finite regression evidence, not proof-assistant verification or evidence of quantum advantage.

The preprint has not been peer reviewed. It does not establish quantum speedup, production reliability or universal improvement. The research direction was proposed by León Acosta; the exposition and reference code were developed with assistance from OpenAI ChatGPT/Codex.

Read and cite

Acosta, León. Deadline aware hybrid optimization for ISP traffic engineering: conditional guarantees and a reproducible reference model. Research preprint, version 0.1, 11 October 2026.

Download the 10-page paper · Reproduce the results · Research roadmap