Noise Robustness of Quantum Relaxation for Combinatorial Optimization

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.