QAOA Achieves 0.9443 Approximation Ratio with Efficient Parameter Transfer Optimisation

Researchers are tackling a key challenge in quantum computing , improving the efficiency of the Quantum Approximate Optimisation Algorithm (QAOA) for complex problems. Shubham Patel and Utkarsh Mishra, both from the Department of Physics & Astrophysics at the University of Delhi, alongside their colleagues, demonstrate a novel approach combining efficient parameter transfer initialization with targeted single-layer regularized optimisation. Their work, focused on the MaxCut problem across various graph types, achieves near-optimal performance , 98.88% of full optimisation , with a significant eightfold speedup in unweighted graphs. This is particularly significant as it suggests a pathway to overcome limitations in QAOA’s performance on certain problem instances, potentially unlocking its wider application in combinatorial optimisation.

The study investigated the MaxCut problem across three distinct graph families, 3-regular, Erdős, Rényi, and Barabási, Albert, employing a QAOA ansatz with a unique initialization strategy followed by focused optimization of a single layer. This innovative method yielded mean approximation ratios of 0.9443 for targeted-single-layer optimization, closely approaching the 0.9551 achieved through full optimization, representing 98.88 percent optimal performance and an 8.06-fold computational speedup in unweighted graphs.

The team achieved this breakthrough by leveraging parameter transfer, a technique borrowed from deep learning, where optimized parameters from simpler graph instances are used to initialize more complex ones. Parameters from 8-node donor graphs were optimized using a TQA initialization and Adagrad optimizer, then transferred to acceptor graphs with up to 24 nodes. This transfer was coupled with targeted-single-layer optimization, focusing computational resources on refining only the most impactful layer of the QAOA circuit. Experiments revealed that, in 8.92 percent of test cases, this targeted approach actually outperformed full optimization, suggesting that the complex parameter landscapes of these problems can trap conventional optimization algorithms in suboptimal local minima.

To further enhance consistency, the researchers implemented ridge (L2) regularization, effectively smoothing the solution landscape and enabling the optimizer to identify better parameters. This regularization reduced the number of instances where targeted-single-layer optimization was outperformed by full optimization from 8.92 percent to 3.81 percent. The work establishes that this combination of efficient parameter initialization and targeted optimization significantly improves QAOA’s efficiency with minimal compromise to solution quality. This advancement opens avenues for tackling larger and more complex optimization problems that are currently intractable for classical computers, potentially impacting fields like logistics, finance, and materials science.

Furthermore, the study highlights the potential of QAOA to move beyond theoretical promise and deliver practical computational advantages. By reducing the computational burden associated with parameter optimization, this research paves the way for implementing QAOA on near-term quantum devices with limited qubit counts and coherence times. The team’s approach not only improves performance in unweighted graphs but also demonstrates promising results for certain weighted graph families, such as weighted 3-regular graphs, indicating its adaptability to diverse problem structures. The research team engineered a parameter transfer approach, initializing QAOA with parameters derived from smaller graphs before employing targeted single-layer optimization. This innovative method achieved mean approximation ratios of 0.9443 for targeted-single layer optimization, closely approaching the 0.9551 achieved by full optimization, representing 98.88 percent optimal performance with an 8.06-fold computational speedup in unweighted graphs. To initialize donor graphs, the study pioneered the use of Trotterized Quantum Annealing (TQA), a protocol that provides QAOA parameters in discrete time steps, circumventing the issue of suboptimal solutions.

The TQA process defines parameters γi = i p∆t and βi = 1 −i p ∆t, where ‘i’ ranges from 0 to p-1, creating linearly increasing γi and decreasing βi values with increasing circuit depth ‘p’, mirroring the controlled parameter tuning of quantum annealing. Researchers then leveraged recent findings demonstrating that optimized parameters cluster for similar problem instances, enabling the transfer of optimized parameters from simpler graphs to initialize more complex ones. Analysis of parameter landscapes for 10n-u3R and 16n-u3R graphs revealed comparable structures in the (γ, β) plane, validating the feasibility of parameter transfer. The team further developed selective optimization, identifying the most effective single layer (pk) within a QAOA ansatz for acceptor graphs with nodes ranging from 8 to 24.

Experiments employed 50 graphs of each node count, individually optimizing each layer to determine the layer yielding the highest approximation ratio (rs). To address inconsistencies where full optimization occasionally became trapped in suboptimal local minima, the study implemented ridge (L2) regularization. This technique smoothed the solution landscape, enabling the optimizer to locate better parameters during full optimization and reducing inconsistent test cases from 8.92 percent to 3.81 percent0.9443, representing 98.88 percent of optimal performance and a 8.06-fold computational speedup for unweighted graphs. However, performance decreased for larger nodes in weighted graph families, although the method proved effective for weighted 3-regular graphs.

In nearly nine percent of cases, targeted single-layer optimisation surpassed full optimisation, suggesting full optimisation can become trapped in suboptimal local minima. To address this, L2 ridge regularisation was implemented to smooth the solution landscape, reducing inconsistent results from 8.92 percent to 3.81 percent. This work establishes that efficient parameter initialisation and targeted single-layer optimisation can enhance QAOA efficiency with minimal.