  Quantum optimization methods use a continuous degree-of-freedom of quantum
states to heuristically solve combinatorial problems, such as the MAX-CUT
problem, which can be attributed to various NP-hard combinatorial problems.
This paper shows that some existing quantum optimization methods can be unified
into a solver that finds the binary solution that is most likely measured from
the optimal quantum state. Combining this finding with the concept of quantum
random access codes (QRACs) for encoding bits into quantum states on fewer
qubits, we propose an efficient recursive quantum relaxation method called
recursive quantum random access optimization (RQRAO) for MAX-CUT. Experiments
on standard benchmark graphs with several hundred nodes in the MAX-CUT problem,
conducted in a fully classical manner using a tensor network technique, show
that RQRAO outperforms the Goemans--Williamson method and is comparable to
state-of-the-art classical solvers. The codes will be made available soon.
