Inventing what's next in combinatorial optimization

AE Quantum · Hybrid Quantum Optimization Research Platform

Download paper

Mike Swain presents a three-layer hybrid architecture for NP-hard combinatorial problems — NISQ QAOA sampling, structure-aware classical refinement, and SMT/Z3 formal verification — so routing, scheduling, and allocation decisions are both higher quality and machine-checkable.

10.5281/zenodo.22765909Mike SwainOpti Mesh 1.0
Pipeline layers
3
QAOA · Refine · Verify
Hardware study
4 / 8
Qubit laboratory runs · 1024 shots
Refinement lift
+15.33 pp
Raw 8.98% → refined 24.32%
Verification
Z3
SMT formal feasibility gate

Our work

Hybrid Quantum Optimization: Combinatorial Optimization Problem

Research Paper
Mike Swain · Æ Hive · AE Database & Quantum R&D Center

Combinatorial optimization — routing, scheduling, resource allocation, and network design — is often NP-hard. This whitepaper describes a general hybrid architecture in which a NISQ device generates candidates via QAOA, a classical refinement stage repairs and improves those candidates, and a formal verification layer establishes logical guarantees over hard constraints. Metrics track raw versus refined optimality ratio. The intent is expository: core computational concept, independently of any particular product or deployment.

LatestQAOAQUBOZ3

Three-layer stack — sample, refine, verify

Figure 1
Independent stages with a bitstring interface contract
Architecture

Raw vs refined sample distribution — optimality lift

Results
Classical greedy refinement recovers quality lost to NISQ noise
Benchmark
Open access archive on ZenodoRead more research on our hub

Results & figures

Table 1. Three-layer hybrid architecture
LayerFunctionRepresentative techniqueOutput
Quantum samplingBiased proposal over exponential search spaceQAOA (or related variational / annealing samplers)Raw bitstrings · P_raw
Classical refinementImprove and repair samples cheaplyGreedy bit-flip · configuration recovery · diversity passRefined bitstrings · P_ref
Formal verificationMachine-checkable hard constraintsSMT solving (Z3) with counterexamplesCertified feasible · or concrete counterexample
Table 2. Optimality ratio metrics
MetricDefinitionLaboratory snapshot
R_rawBest raw quantum sample / reference8.98%
R_refBest refined sample / reference24.32%
ΔR_ref − R_raw (percentage points)+15.33 pp
Table 3. Hardware study configuration
ItemValue
AlgorithmQAOA (gate-model variational)
Qubit counts4 and 8
Circuit depth p1 (shallow NISQ regime)
Shots1024
EncodingQUBO / Ising Hamiltonian
Three-layer hybrid quantum-classical optimization architecture
Figure 1. Three-layer architecture — quantum sampling (QAOA), classical refinement, and formal verification (SMT/Z3) with a representation-agnostic bitstring interface.
4-qubit QAOA circuit at depth p equals 1
Figure 2. 4-qubit QAOA circuit (p=1) — Hadamard preparation, alternating cost and mixing unitaries, computational-basis measurement.
Sample distribution raw versus refined optimality
Figure 3. Sample distribution — 8-qubit laboratory histogram comparing raw quantum samples with greedily refined candidates (8.98% → 24.32%, Δ +15.33 pp).
QPU run sample distribution from hardware study
Figure 4. Hardware QPU distribution — measured bitstring frequencies from the laboratory quantum run used in the Hybrid Quantum Optimization study.
Exported QPU circuit diagram from hardware backend
Figure 5. QPU circuit export — gate-model circuit submitted for the hardware-scale sampling experiment.
End-to-end hybrid optimization pipeline diagram
Figure 6. End-to-end pipeline — from combinatorial problem encoding through QAOA sampling, classical refinement, and formal verification.

Open access · Hybrid Quantum Optimization

Mike Swain· Æ Hive · doi:10.5281/zenodo.22765909 · AE Database & Quantum R&D Center · Combinatorial Optimization Problem

Download full report

Tools + Code

Research Paper

Hybrid Quantum Optimization — QAOA sampling, classical refinement, and SMT/Z3 verification for combinatorial problems.

View project →

Opti Mesh 1.0

Live laboratory console — overview, z3 proofs, AIS fleet, and QPU optimality via /api/optimesh.

View project →

Three-Layer Architecture

Quantum sampling → classical refinement → formal verification as independent, swappable stages.

View project →

QAOA Circuit

4-qubit p=1 QAOA circuit used in the laboratory hardware study (1024 shots).

View project →

Sample Distribution

Raw vs refined optimality — laboratory histogram showing classical refinement lift.

View project →

Pipeline Diagram

End-to-end hybrid quantum-classical optimization flow with verification gate.

View project →