QAOA is a heuristic. GW achieves 0.878-approximation in polynomial time. No constant-depth QAOA is known to surpass this. Advantage would require super-polynomial circuit depth, which eliminates the speed benefit.

• No proven quantum advantage for MaxCut QAOA at any constant depth
• Classical GW algorithm achieves 0.878-approximation in polynomial time
• Instance is trivially small (n=3) — advantage claims meaningless at this scale
• 131k physical qubits for a 3-vertex graph; scaling to practical graphs unknown

No proven quantum advantage for QAOA on MaxCut. The Goemans-Williamson algorithm achieves 0.878-approximation in polynomial time. QAOA at constant depth can be classically simulated. Higher-depth QAOA may offer advantage but this is unproven.

05. QAOA for Max-Cut

This problem prepares the groundwork for implementing the Quantum Approximate Optimization Algorithm on weighted Max-Cut instances. The current milestone provides deterministic classical baselines, representative graph instances, and a working depth-1 QAOA circuit with a coarse parameter sweep.

Roadmap

• [x] Scaffold directory structure, utilities, and helper scripts
• [x] Provide classical brute-force baseline with summary statistics
• [x] Add parameterized graph instances (small/medium/large)
• [x] Generate diagnostic plots for cut values
• [x] Implement depth-1 QAOA circuit with coarse parameter sweep
• [x] Generalize QAOA optimizer to support depth >= 1 via coordinate search
• [x] Add depth sweep evidence artifacts (`depth_sweep_.{json,md}` + plot)
• [x] Generalize QAOA driver to consume YAML instances dynamically
• [x] Add uncertainty-bounded multi-trial QAOA reporting to `estimates/`
• [x] Route optimized parameters into the resource estimator profiles
• [ ] Add Microsoft Quantum Stack execution path and portability layer (Azure Quantum first, hardware-agnostic adapters next)

Quickstart

cd problems/05_qaoa_maxcut
make classical      # Exhaustive search baseline for each YAML graph instance
make analyze        # Generate plots summarizing best cut values
make build          # Build the Q# project (uses modern QDK  qsharp Python package)
make run            # Run depth-configurable QAOA with multi-trial uncertainty summary + JSON output
make run-all        # Run depth-configurable QAOA for small/medium/large and write quantum artifacts
make depth-sweep INSTANCE=small DEPTHS=1,2,3 TRIALS=6  # Generate depth-vs-quality evidence artifacts
make noise-sweep INSTANCE=small DEPTH=3 NOISE_LEVELS=0.00,0.01,0.02,0.05,0.10  # Generate readout-noise sensitivity artifacts
make azure-manifest INSTANCE=small DEPTH=3 TARGET_ID=microsoft.estimator  # Build Azure Quantum execution contract manifest
make azure-runbook INSTANCE=small DEPTH=3 TARGET_ID=microsoft.estimator  # Print end-to-end Azure auth/run checklist
cp .env.azure.example .env.azure.local  # Manual step: fill Azure workspace/auth values before cloud operations
make validate-azure-env  # Enforce manual env file is present and placeholders are replaced
make validate-azure-cli  # Validate az CLI login, quantum extension, and workspace access
make validate-azure-manifest INSTANCE=small DEPTH=3  # Validate Azure manifest + referenced evidence artifacts
make azure-submit INSTANCE=small DEPTH=3 AZURE_MANUAL_JOB_ID=<azure_job_id>  # Record real Azure submission metadata
make azure-submit-auto INSTANCE=small DEPTH=3 TARGET_ID=microsoft.estimator AZURE_JOB_INPUT_FILE=<path/to/program.qir>  # Dry-run preview of az quantum submit command
make azure-submit-auto INSTANCE=small DEPTH=3 TARGET_ID=microsoft.estimator AZURE_JOB_INPUT_FILE=<path/to/program.qir> AZURE_SUBMIT_EXECUTE=1  # Execute az quantum submit and auto-stamp manifest
make azure-smoke INSTANCE=small DEPTH=3 TARGET_ID=microsoft.estimator AZURE_JOB_INPUT_FILE=<path/to/program.qir>  # One-command preflight + manifest + dry-run submit
make azure-smoke INSTANCE=small DEPTH=3 TARGET_ID=microsoft.estimator AZURE_JOB_INPUT_FILE=<path/to/program.qir> AZURE_SUBMIT_EXECUTE=1 AZURE_SMOKE_COLLECT=1  # Execute submit and fetch current Azure status
make azure-smoke-report INSTANCE=small DEPTH=3  # Rebuild Azure smoke JSON/MD evidence from current manifest
make azure-collect INSTANCE=small DEPTH=3 AZURE_RESULT_STATUS=succeeded  # Record Azure result status
make azure-collect-auto INSTANCE=small DEPTH=3  # Query Azure CLI for live status and update manifest
make validate-assumptions  # Validate backend/transpilation/connectivity assumptions evidence
make validate-quality  # Validate depth/noise quality thresholds for Stage C evidence
make estimate       # Build estimator params from latest quantum artifact and run estimator automation
make estimate-all   # Build estimator params, run estimator automation for small/medium/large, prune stale artifacts, and refresh markdown summary
make estimate ESTIMATE_MOCK=0  # Optional: run estimator automation without mock mode
make evidence       # One-shot refresh: classical baseline + quantum runs + plots + estimator summaries

If make is unavailable on Windows PowerShell, run the equivalent sequence directly:

python -c "import qsharp; qsharp.init(project_root='qsharp'); print('Build OK')"
python python/classical_baseline.py
python -c "import qsharp; qsharp.init(project_root='qsharp'); print(qsharp.run('Main.RunQaoaAnalysis([[0.0,1.0,1.0],[1.0,0.0,1.0],[1.0,1.0,0.0]], 1, 50, 100)', shots=1))"
python python/analyze.py
python python/compare.py
python python/prepare_estimator_params.py --instance small --depth 1
python ../../tooling/estimator/run_estimation.py --all --problem 05_qaoa_maxcut --params-file estimates/estimator_params_small_d1.json --targets surface_code_generic_v1,qubit_gate_ns_e3 --mock --summary-path ../../tooling/estimator/output/qaoa_summary_small.json

Windows helper script (recommended in PowerShell):

.\tooling\windows\qaoa-maxcut.ps1 -Action run -Instance small
.\tooling\windows\qaoa-maxcut.ps1 -Action run-all
.\tooling\windows\qaoa-maxcut.ps1 -Action depth-sweep -Instance small -Depths 1,2,3
.\tooling\windows\qaoa-maxcut.ps1 -Action noise-sweep -Instance small -Depth 3 -NoiseLevels 0.00,0.01,0.02,0.05,0.10
.\tooling\windows\qaoa-maxcut.ps1 -Action azure-runbook -Instance small -Depth 3
.\tooling\windows\qaoa-maxcut.ps1 -Action validate-azure-env -AzureEnvFile .env.azure.local
.\tooling\windows\qaoa-maxcut.ps1 -Action validate-azure-cli -AzureEnvFile .env.azure.local
.\tooling\windows\qaoa-maxcut.ps1 -Action azure-manifest -Instance small -Depth 3 -TargetId microsoft.estimator
.\tooling\windows\qaoa-maxcut.ps1 -Action azure-submit -Instance small -Depth 3 -AzureEnvFile .env.azure.local -AzureManualJobId <azure_job_id>
.\tooling\windows\qaoa-maxcut.ps1 -Action azure-submit-auto -Instance small -Depth 3 -TargetId microsoft.estimator -AzureEnvFile .env.azure.local -AzureJobInputFile <path\to\program.qir>
.\tooling\windows\qaoa-maxcut.ps1 -Action azure-submit-auto -Instance small -Depth 3 -TargetId microsoft.estimator -AzureEnvFile .env.azure.local -AzureJobInputFile <path\to\program.qir> -AzureSubmitExecute
.\tooling\windows\qaoa-maxcut.ps1 -Action azure-smoke -Instance small -Depth 3 -TargetId microsoft.estimator -AzureEnvFile .env.azure.local -AzureJobInputFile <path\to\program.qir>
.\tooling\windows\qaoa-maxcut.ps1 -Action azure-smoke -Instance small -Depth 3 -TargetId microsoft.estimator -AzureEnvFile .env.azure.local -AzureJobInputFile <path\to\program.qir> -AzureSubmitExecute -AzureSmokeCollect
.\tooling\windows\qaoa-maxcut.ps1 -Action azure-smoke-report -Instance small -Depth 3
.\tooling\windows\qaoa-maxcut.ps1 -Action azure-collect -Instance small -Depth 3 -AzureEnvFile .env.azure.local -AzureResultStatus succeeded
.\tooling\windows\qaoa-maxcut.ps1 -Action azure-collect-auto -Instance small -Depth 3 -AzureEnvFile .env.azure.local
.\tooling\windows\qaoa-maxcut.ps1 -Action estimate -Instance small
.\tooling\windows\qaoa-maxcut.ps1 -Action estimate-all
.\tooling\windows\qaoa-maxcut.ps1 -Action estimate -Instance small -LiveEstimate
.\tooling\windows\qaoa-maxcut.ps1 -Action evidence
.\tooling\windows\qaoa-maxcut.ps1 -Action evidence -Quick

CMD wrapper equivalent:

tooling\windows\qaoa-maxcut.cmd -Action evidence -Quick
tooling\windows\qaoa-maxcut-quick.cmd

Outputs

• `estimates/classical_baseline.json` – Maximum cut assignments and values for every graph instance
• `estimates/quantum_baseline__d.json` – Multi-trial QAOA statistics with confidence intervals
• `estimates/depth_sweep_.json` – Aggregated depth sweep metrics for the selected instance
• `estimates/depth_sweep_.md` – Markdown summary table for depth sweep results
• `estimates/noise_sweep__d.json` – Readout-noise sensitivity sweep metrics for a selected baseline depth
• `estimates/noise_sweep__d.md` – Markdown summary table for noise sweep results
• `estimates/azure_job_manifest__d.json` – Azure Quantum execution contract manifest (target, job metadata, and evidence paths)
• `estimates/azure_smoke_report__d.json` – Machine-readable Azure smoke workflow audit (preflight/manifest/submit/collect status)
• `estimates/azure_smoke_report__d.md` – Human-readable Azure smoke workflow audit summary
• `.env.azure.example` – Template for manual Azure auth/workspace configuration (copy to `.env.azure.local` and edit)
• `estimates/backend_assumptions.md` – Backend/transpilation/connectivity assumptions for reported runtime + estimator evidence
• `python/prepare_azure_job_manifest.py` – Generates Azure Quantum submission contract artifacts from current QAOA evidence
• `python/validate_azure_env.py` – Validates required manual Azure env values and blocks placeholder usage
• `python/submit_azure_job.py` – Records real Azure submission metadata in manifest after manual/cloud submit
• `python/submit_azure_job_auto.py` – Dry-run-safe Azure CLI submission helper; with `--execute`, submits and auto-stamps job metadata
• `python/write_azure_smoke_report.py` – Generates Azure smoke evidence artifacts (JSON + markdown) from manifest and workflow mode
• `python/collect_azure_job.py` – Records Azure result status in manifest for traceable job lifecycle
• `python/validate_azure_job_manifest.py` – Validates Azure job manifest schema assumptions and referenced evidence files
• `python/validate_evidence_quality.py` – Enforces depth/noise evidence quality thresholds used by CI/automation
• `estimates/evidence_quality_report.md` – Human-readable snapshot of depth/noise evidence threshold checks
• `estimates/evidence_quality_report.json` – Machine-readable snapshot of depth/noise evidence threshold checks
• `estimates/estimator_params__d.json` – Estimator-ready parameter payload derived from the latest quantum baseline
• `estimates/quantum_classical_summary.md` – Auto-generated markdown table comparing classical optimum vs quantum mean +/- CI
• `estimates/estimator_profile_summary.md` – Auto-generated table summarizing latest estimator metrics across instances and targets
• `estimates/latest__.json` – Stable latest estimator artifact for each target/instance pair (used by summary tooling)
• `python/prune_estimator_artifacts.py` – Keeps timestamped estimator artifacts bounded (`--keep-per-target`, default 3)
• `tooling/estimator/output/qaoa_summary_.json` – Combined estimator summary for QAOA targets (mock/live depending on invocation)
• `plots/best_cut_values.png` – Visual comparison of Max-Cut values across instances
• `plots/value_distribution_small.png` – Distribution of cut values for the small instance
• `plots/quantum_vs_classical_uncertainty.png` – Quantum refined expectation versus classical optimum with 95% CI bars
• `plots/qaoa_depth_sweep_.png` – Refined expectation versus depth with 95% CI bars
• `plots/qaoa_noise_sweep__d.png` – Refined cut-value sensitivity across readout-noise levels
• `qsharp/src/Main.qs` – Q# QAOA implementation, compiled on-the-fly by the modern QDK

Current Baseline

The classical baseline enumerates all bit strings to guarantee optimal Max-Cut values and logs diagnostic metrics that translate directly to QAOA objective functions. The Q# host now runs a depth-configurable QAOA coordinate-search optimizer per trial, aggregates uncertainty-bounded expectation metrics across repeated simulator trials, and writes a JSON report for reproducible comparison against the classical optimum. Future work will expand the pipeline to tighter optimizers and estimator-driven hardware profiling.

Objective Maturity Gate

• **Current gate**: **Stage C complete** (hardware-aware validation evidence with uncertainty-bounded comparisons is in place).
• **Next gate target**: **Stage D** (backend-calibrated performance hardening and stronger hardware-readiness evidence).

Microsoft-First Portability Scope

Priority order for execution backends:

1. Microsoft Quantum Stack (Q# + Azure Quantum targets) as the production path.

2. Hardware-agnostic export/adapter path for future IBM/Google/AWS backend trials.

Scope for the next implementation step (Stage C to D bridge):

1. Azure Quantum execution contract (required first)

• Define a stable job manifest for QAOA runs (`instance`, `depth`, `shots`, `trials`, `target_id`, evidence output paths).
• Add a non-placeholder submit-and-collect workflow against Azure Quantum targets (or mock-compatible shape where target access is restricted).
• Emit run metadata (`provider`, `target`, submission timestamp, job id, result status) into `estimates/` artifacts.

2. Backend adapter boundary (required for portability)

• Introduce an execution interface that separates problem orchestration from backend-specific submission details.
• Keep Q# as source of truth while allowing adapters to plug in alternate runtimes.

3. Cross-stack pilot (long-term, not blocking Microsoft priority)

• Add export hooks for OpenQASM 3 and evaluate one pilot run path for non-Microsoft stacks (IBM/Google/AWS simulators first).
• Mark cross-stack outputs as comparative evidence only until parity checks pass.

Acceptance criteria for this step:

• At least one QAOA artifact is produced via Azure Quantum submission metadata path.
• Existing `depth_sweep` and `noise_sweep` reports remain reproducible and unchanged in schema.
• Backend assumptions document explicitly distinguishes simulator evidence from cloud-target evidence.
• Portability adapters are additive and do not regress the default Q# workflow.

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.

Current progress toward Stage C (exit criteria satisfied):

• Depth-1 QAOA host now emits uncertainty-bounded trial statistics and JSON artifacts for reproducible small-instance comparisons.
• Q# optimizer now supports depth >= 1 using coordinate-search updates over beta/gamma layers.
• Depth-2 trial evidence for the small instance is available in `estimates/quantum_baseline_small_d2.json`.
• Depth sweep evidence (`d=1,2,3`) for the small instance is available in `estimates/depth_sweep_small.md`, showing improved refined mean from `1.4927` (d=1) to `1.9247` (d=3).
• Medium-instance depth sweep (`d=1,2`) is available in `estimates/depth_sweep_medium.md` (best refined mean `2.8316` at depth 2).
• Large-instance depth sweep (`d=1,2`) is available in `estimates/depth_sweep_large.md` (best refined mean `4.1578` at depth 2).
• Noise-sensitivity sweeps can now be generated via `make noise-sweep` (or `python/noise_sweep.py`) and are surfaced in the summary dashboard when present.
• Small-instance noise sweep at depth 3 is available in `estimates/noise_sweep_small_d3.md` (degrades from `2.2000` at `p=0.00` to `1.9521` at `p=0.10`).
• Medium-instance noise sweep at depth 2 is available in `estimates/noise_sweep_medium_d2.md` (degrades from `4.0000` at `p=0.00` to `3.3164` at `p=0.10`).
• Large-instance noise sweep at depth 2 is available in `estimates/noise_sweep_large_d2.md` (degrades from `7.3000` at `p=0.00` to `5.9883` at `p=0.10`).
• Medium-instance uncertainty report is now available in `estimates/quantum_baseline_medium_d1.json`.
• Large-instance uncertainty report is now available in `estimates/quantum_baseline_large_d1.json`.
• Hardware-targeted estimator routing is now wired through `python/prepare_estimator_params.py` and `tooling/estimator/run_estimation.py`.
• Azure Quantum job manifest contract generation/validation is now available via `python/prepare_azure_job_manifest.py` and `python/validate_azure_job_manifest.py`.
• Backend/transpilation/connectivity assumptions are now documented in `estimates/backend_assumptions.md` and checked via `python/validate_backend_assumptions.py`.
• Depth/noise evidence quality is now enforced via `python/validate_evidence_quality.py` (minimum points, bounded monotonicity behavior, and minimum degradation/gain thresholds).
• Quality checks now emit `estimates/evidence_quality_report.{md,json}` for reproducible CI/local audit trails.

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.

Stage D Hardening Package

• Stage D evidence file: `STAGE_D_ADVANTAGE_EVIDENCE.md`.
• This package records fairness/uncertainty evidence status and concrete promotion criteria from `theoretical` to a stronger claim category.