Optimisation-Free Recursive QAOA for the Binary Paint Shop Problem

Abstract

The Quantum Approximate Optimisation 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 optimisation of variational parameters. The Recursive-QAOA (RQAOA) introduced by Bravyi et al. Phys. Rev. Lett. (2020), addresses the first limitation while also reducing circuit size, and parameter transfer techniques can be used to effectively bypass the optimisation loop. In this work, we combine these two ideas to develop an optimisation-free RQAOA and evaluate its performance on the Binary Paint Shop Problem (BPSP) -- an optimisation problem found in manufacturing where a sequence of cars must be painted under constraints while minimising the number of colour 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 optimisation, we use reverse causal cones (RCC) 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 optimisation without the overhead of the classical optimisation loop and its challenges with barren plateaus.