Triangle Quantum Computing Seminar Series: Quantum Computing with Hamming Rooms in Hilbert Space: Kernelizing Constrained Quantum Optimization for Exponential Feasible-Sampling Enhancement over Standard QAOA

Abstract: Near-term quantum optimization workflows ultimately output samples, so for globally constrained problems the operational bottleneck is often feasibility: does a shallow circuit place non-negligible probability mass on the valid manifold at realistic shot budgets? This talk introduces a kernelization viewpoint based on "Hamming rooms in Hilbert space": symmetry-restricted subspaces where constraint geometry is made explicit in the encoding, initial state, and mixer. I will show why standard QAOA with an X-mixer and diagonal local phase separator can exhibit exponentially suppressed feasible sampling on permutation-style constraints, even after parameter tuning, and why this suppression persists across a wide low-depth regime. I will then present a constructive route to exponential feasible-sampling enhancement using constraint-preserving encoded kernels with number-conserving mixing that keeps dynamics inside the intended symmetry class. I will close with practical diagnostics for symmetry-matched null models and a benchmarking checklist for validating the intended behavior in numerical studies and on compiled executions. --- Co-hosted by the Duke Quantum Center, the NC State Quantum Initiative, and the UNC Kenan-Flagler's Rethinc. Labs.