Abstract
Post-quantum migration requires a service mesh to choose cryptographic profiles as endpoint capabilities, policies, threats, and evidence freshness change. Static mesh settings and policy-as-code enforce a posture once it is chosen, but neither makes that choice for each service edge. We present QuantumTrustKG , a provenance-aware, graph-backed control-plane framework for edge-specific selection. For each communication edge, its Quantum Trust Protocol Orchestration ( QTPO ) procedure removes profiles that fail a capability, policy, threat, or freshness gate, ranks the rest by cost, and blocks promotion if none is admissible. We mechanize the control-plane guarantees in Coq/Rocq and implement QTPO as a Kubernetes/Istio controller. In a controlled comparison on 200-service meshes, QTPO records no unsafe promotions and 96.5% declared-label policy compliance , while service-level and opportunistic baselines promote unsafely on 3.4–13.7% of edges. On sampled production service topologies of up to 2000 services, the service-level crypto-agility and per-endpoint baselines record 37–60% and QTPO stays at zero. The compliance metric reads the same declared labels that drive the controller. It therefore evaluates control-plane decisions, with wire-level cryptographic negotiation outside its scope. Keywords: Service orchestration, Microservices, Knowledge graphs, Service mesh, Post-quantum cryptography, Crypto-agility