  QRAO (Quantum Random Access Optimization) is a relaxation algorithm that
reduces the number of qubits required to solve a problem by encoding multiple
variables per qubit using QRAC (Quantum Random Access Code). Reducing the
number of qubits is a common way of dealing with the impact of noise on a
quantum algorithm. Our interest lies in the impact of noise on the quality of
the binary solution of QRAO, which is unknown. We demonstrate that the mean
approximation ratio of the (3, 1)-QRAC Hamiltonian, i.e., the Hamiltonian
utilizing the encoding of 3 bits into 1 qubit by QRAC, is less affected by
noise compared to the Ising Hamiltonian used in quantum annealer and QAOA
(Quantum Approximate Optimization Algorithm). Based on this observation, we
discuss a plausible mechanism behind the robustness of QRAO under depolarizing
noise. Finally, we assess the number of shots required to estimate the values
of binary variables correctly under depolarizing noise and show that the (3,
1)-QRAC Hamiltonian requires less shots to achieve the same accuracy compared
to the Ising Hamiltonian.
