  Combinatorial problems are formulated to find optimal designs within a fixed
set of constraints. They are commonly found across diverse engineering and
scientific domains. Understanding how to best use quantum computers for
combinatorial optimization is to date an open problem. Here we propose new
methods for producing approximate solutions for the maximum cut problem and its
weighted version, which are based on relaxations to local quantum Hamiltonians.
These relaxations are defined through commutative maps, which in turn are
constructed borrowing ideas from quantum random access codes. We establish
relations between the spectra of the relaxed Hamiltonians and optimal cuts of
the original problems, via two quantum rounding protocols. The first one is
based on projections to random magic states. It produces average cuts that
approximate the optimal one by a factor of least 0.555 or 0.625, depending on
the relaxation chosen, if given access to a quantum state with energy between
the optimal classical cut and the maximal relaxed energy. The second rounding
protocol is deterministic and it is based on estimation of Pauli observables.
The proposed quantum relaxations inherit memory compression from quantum random
access codes, which allowed us to test the performances of the methods
presented for 3-regular random graphs and a design problem motivated by
industry for sizes up to 40 nodes, on superconducting quantum processors.
