Grover quadratic speedup is provably optimal but only halves the effective key length. NIST already recommends doubling key sizes (AES-256 instead of AES-128) to counter Grover. The practical threat to modern cryptography is from Shor (factoring) not Grover (search).

• Quadratic speedup only — doubles effective key length, does not break modern crypto
• Oracle implementation cost for real AES/SHA may be prohibitive (millions of T-gates)
• 33k physical qubits for 3-qubit toy instance; O(thousands of logical qubits) for AES-128
• Grover speedup is already factored into post-quantum key length recommendations (NIST)

Grover's quadratic speedup is provably optimal but only halves effective key length. NIST already recommends doubled key sizes (AES-256). The practical threat is from Shor, not Grover.

Problem 10 · Post-Quantum Cryptography Security Analysis

Overview

Post-quantum cryptography (PQC) must withstand both classical and quantum attacks. Modern lattice schemes trade performance against resistance to advanced BKZ reduction and Grover-amplified sieving. This problem installs a classical baseline that estimates the cost of state-of-the-art attacks against NIST-style parameter sets while providing a Q# scaffold for experimenting with amplitude-amplified sieving primitives and hybrid search routines.

Directory Layout

10_post_quantum_cryptography/
├── estimates/                      # JSON artifacts from classical / quantum workflows
├── instances/                      # Representative NIST parameter sets
├── plots/                          # Generated figures from analyze.py
├── python/
│   ├── classical_baseline.py       # Cost estimation for classical / quantum lattice attacks
│   └── analyze.py                  # Visualization of security margins
└── qsharp/
    ├── qsharp.json            # Modern QDK project file
    └── Program.qs                  # Placeholder quantum workflow

Quick Start

cd problems/10_post_quantum_cryptography

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

# Visualize cost curves and security margins
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. Amplitude Amplification Kernel – Prototype Grover-style boosts for nearest vector search cost models.

2. Hybrid BKZ Simulation – Integrate amplitude amplification with classical pruning heuristics in Q#.

3. Adaptive Parameter Study – Sweep lattice dimensions / modulus sizes to locate safe PQC parameters.

4. Resource Estimation – Quantify logical qubits and T-count for practical quantum sieving on targeted dimensions.

This scaffold keeps classical estimators reproducible while we prototype quantum-enhanced attack analyses. 🔐⚛️

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.