Decoder-Consistent Hamiltonians for POVM-Based Quantum Relaxations

Abstract

In compression-based quantum relaxations such as quantum random access optimization (QRAO), a quantum state is optimized on a reduced number of qubits and then decoded into a classical solution on which the objective function is evaluated. The Hermitian operator whose expectation value is optimized should therefore be consistent with the expected objective value after decoding. For a fixed single-shot POVM decoder, we define the decoder-consistent Hamiltonian as the pullback of the classical objective observable through the decoder. Its expectation value exactly equals the expected post-decoding objective value for every quantum state. We further show that any Hermitian operator inducing the same ordering over the full quantum state space must be a positive affine transformation of the decoder-consistent Hamiltonian. Using a Boolean Fourier expansion, the decoder-consistent Hamiltonian decomposes into pullbacks of individual Fourier components. This provides a common framework for comparing direct encoding, simultaneous-decoding POVMs for QRAC blocks, and the effective POVM induced by the magic rounding of Teramoto et al. in terms of which components they preserve and at what rates. For standard magic-state rounding in coloring-based QRAO for MaxCut, the framework recovers the known positive affine relation between the relaxed-Hamiltonian expectation and the expected rounded cut value. For the simultaneous-decoding POVMs analyzed here, we further show that the analogous relation generally fails for mixed-degree QUBO objectives because one- and two-body components are attenuated at different rates. We also present a systematic construction of POVM decoder blocks from prescribed Fourier components and derive corresponding lower bounds on the expected post-decoding objective value under explicit conditions.