Paper 2026/332

Cost-Layer–Blind Hybrid QAOA for MAX K-CUT via Native MBQC and Selective Graph Masking

Youngkyung Lee, Electronics and Telecommunications Research Institute

Juyoung Kim, Electronics and Telecommunications Research Institute

Abstract

Delegating the Quantum Approximate Optimization Algorithm (QAOA) to an untrusted quantum cloud can leak sensitive instance structure: for graph objectives, the connectivity of the cost unitary directly reveals which edges are present. We propose a selectively blind protocol that hides only the instance-dependent cost Hamiltonian while keeping the mixer public and unmodified. Our approach combines (i) the native measurement-based implementation of the MAX $K$-CUT cost layer from Proietti \emph{et al.} (MBQC-QAOA) and (ii) selective masking techniques inspired by Selectively Blind Quantum Computation (SBQC). The client pads the private graph into a public candidate supergraph by adding dummy edges/vertices. During the measurement-based cost evolution, the server prepares a fixed public MBQC resource over the candidate edges and streams the corresponding cost ancillas to the client for measurement (measurement-only delegation). By choosing either the intended interaction angle (real edge) or the identity angle (dummy edge) \emph{locally}, the client privately prunes dummy edges while revealing no cost-layer angles to the server; one-time-padded correction bits preserve a leakage-free Pauli-frame interface to a standard gate-model mixer. We prove correctness and selective edge blindness, show that padding does not alter the QAOA optimization landscape (hence does not worsen barren plateaus), and provide proof-of-concept numerical validations for MAX-CUT ($K=2$) (exact state-vector equivalence tests and shot-based circuit emulation with feed-forward), together with an asymptotic resource analysis for general MAX $K$-CUT and an explicit dummy-vertex invariance check under full-register mixers.

@misc{cryptoeprint:2026/332,
      author = {Doyoung Chung and Youngkyung Lee and Juyoung Kim},
      title = {Cost-Layer–Blind Hybrid {QAOA} for {MAX} K-{CUT} via Native {MBQC} and Selective Graph Masking},
      howpublished = {Cryptology {ePrint} Archive, Paper 2026/332},
      year = {2026},
      url = {https://eprint.iacr.org/2026/332}
}