Solving hard optimization problems is one of the most promising application domains for quantum computers due to the ubiquity of such problems in industry and the availability of broadly applicable theoretical quantum speedups. However, the ability of near-term quantum computers to tackle industrial-scale optimization problems is limited by their size and the overheads of quantum error correction. Quantum Random Access Optimization (QRAO) has been proposed to reduce the space requirements of quantum optimization. However, to date QRAO has only been implemented using variational algorithms, which suffer from the need to train instance-specific variational parameters, making them difficult to scale. We propose and benchmark a non-variational approach to QRAO based on the Quantum Alternating Operator Ansatz (QAOA) for the MaxCut problem. We show that instance-independent "fixed" parameters achieve good performance, removing the need for variational parameter optimization. Additionally, we evaluate different design choices, such as various mixers, initial states, and QRAO-specific implementations of the QAOA cost operator, and identify a strategy that performs well in practice. Our results pave the way for the practical execution of QRAO on early fault-tolerant quantum computers.
He et al. (Sat,) studied this question.