Optimization-free recursive Quantum Approximate Optimization Algorithm for the binary paint shop problem

The Quantum Approximate Optimization Algorithm (QAOA) is a leading candidate for near-term quantum advantage, yet its practical impact is hindered by limited performance on symmetric local Hamiltonians and the costly optimization of variational parameters. The recursive-QAOA (RQAOA) introduced by Bravyi [] addresses the first limitation while also reducing circuit size, and parameter transfer techniques can be used to bypass the optimization loop effectively. In this work, we combine these two ideas to develop an optimization-free RQAOA and evaluate its performance on the binary paint shop problem (BPSP)—an optimization problem found in manufacturing where a sequence of cars must be painted under constraints while minimizing the number of color changes. The BPSP can be formulated as an Ising ground state problem with a symmetric local Hamiltonian in the form of MAX-CUT and properties well suited for the application of QAOA parameter transfer. We benchmark QAOA and RQAOA with parameter transfer against classical solvers and heuristics, and investigate their resilience to suboptimal parameters. For circuit optimization, we use reverse-causal cones and introduce a method of trimming outer two-qubit gates. To estimate the classical resources needed to simulate these quantum algorithms, we compute entanglement entropy and bond dimensions using matrix product state methods. We also compare circuit sizes and measurement counts across implementations. Our results show that RQAOA is inherently robust to parameter deviations, maintaining near-optimal solutions without noticeable degradation under parameter transfer while substantially reducing quantum resource requirements compared to QAOA. This highlights a viable route toward scalable quantum optimization without the overhead of the classical optimization loop and its challenges with barren plateaus.