Same QAOA limitations as MaxCut. Classical scheduling algorithms are highly optimized for industrial use. No proven quantum advantage for combinatorial optimization at any depth.

Problem 12 · Quantum-Assisted Combinatorial Optimization

Overview

Scheduling, routing, and resource allocation problems are notoriously difficult to solve optimally. Quantum algorithms such as the Quantum Approximate Optimization Algorithm (QAOA) promise improvements by exploring large solution spaces with quantum interference. This scaffold supplies a reproducible classical baseline using greedy weighted tardiness minimization for multi-machine scheduling and prepares a Q# project where future QAOA and amplitude-encoded heuristics can be explored.

Directory Layout

12_quantum_optimization/
├── estimates/                      # JSON artifacts from classical / quantum workflows
├── instances/                      # Scheduling instances (small/medium/large)
├── plots/                          # Generated figures from analyze.py
├── python/
│   ├── classical_baseline.py       # Greedy weighted tardiness scheduler
│   └── analyze.py                  # Visualization of tardiness, utilization, and makespan
└── qsharp/
    ├── qsharp.json            # Modern QDK project file
    └── Program.qs                  # Placeholder quantum workflow

Quick Start

cd problems/12_quantum_optimization

# Classical baseline (writes estimates/classical_baseline.json)
python python/classical_baseline.py

# Visualize tardiness and utilization profiles
python python/analyze.py

# Quantum placeholder
 python -c "import qsharp; qsharp.init(project_root='qsharp'); print('Build OK')"
 python tooling/run_all_qsharp.py  # runs via qsharp Python package

Next Quantum Milestones

1. Cost Hamiltonian Encoding – Map weighted tardiness and machine constraints into qubit operators.

2. Mixer Design – Implement QAOA mixers that respect machine allocation constraints.

3. Hybrid Optimization Loop – Couple Q# circuits with classical optimizers for parameter tuning.

4. Resource Estimation – Benchmark qubit counts and circuit depth for realistic scheduling workloads.

This scaffold keeps the classical scheduling baseline reproducible while we iterate toward quantum-enabled combinatorial optimization strategies. 🧮⚛️

Objective Maturity Gate

• **Current gate**: **Stage B complete** (classical baseline and Q# scaffold/build path are in place).
• **Next gate target**: **Stage C** (hardware-aware validation with uncertainty-bounded comparisons).

Stage C exit criteria for this problem:

• Execute at least one non-placeholder quantum workflow path tied to the problem objective.
• Report uncertainty-bounded comparisons between classical and quantum outputs on `small` and `medium` instances.
• Document transpilation/connectivity and backend assumptions used for reported quantum runs.
• Add calibration/noise-sensitivity evidence for the reported quantum metrics.

DiVincenzo Readiness (Stage C/D Overlay)

| Criterion | Status | Evidence / Notes |

|---|---|---|

| Scalable qubit system | partial | Problem-scoped instance baselines are in place; full hardware-scale projections are tracked as Stage C work. |

| Initialization | partial | Input/state initialization path is defined for current workflows, with backend-ready loading fidelity still to be hardened. |

| Coherence vs gate time | not-yet | Backend-calibrated coherence-vs-depth evidence is pending and required for Stage C/D promotion. |

| Universal gate set | partial | Q# scaffold/build path exists; gate-basis decomposition and transpilation evidence remain Stage C tasks. |

| Qubit-specific measurement | partial | Measurement outputs are defined for current validation flows; hardware readout characterization is pending. |

Advantage Claim Contract

• **Claim category (current)**: `theoretical`.
• **Problem class and regime**: Problem-specific challenge instances defined in this directory.
• **Fair baseline**: Problem-local classical baseline in `python/` outputs.
• **Quantum resource scaling claim**: Expected asymptotic advantage depends on algorithm family and implementation assumptions; no hardware-demonstrated speedup claim yet.
• **Data-loading and I/O assumptions**: Must be documented alongside future advantage claims.
• **Noise/error model assumptions**: Backend-specific model and calibration assumptions to be added at Stage C.
• **Confidence/uncertainty method**: To be reported using shot-based confidence intervals or equivalent statistical bounds.
• **Residual risks**: Oracle/state-preparation/transpilation overhead may dominate for near-term instance sizes.