Krea University Team Proposes Transport-Augmented QAOA for MaxCut Optimisation

A new quantum algorithm tackles a key limitation in solving complex optimisation problems. Mithilesh Kumar and Yusuf Tahir at Krea University show that the Quantum Approximate Optimisation Algorithm (QAOA) encounters difficulties with instances possessing high diameter because of a locality bottleneck that restricts the circuit’s ability to efficiently explore the solution space. Their transport-augmented QAOA addresses this by strategically incorporating shortcut couplings, effectively reducing the diameter of the interaction graph and sharply enhancing performance. Benchmarks reveal this approach overcomes the size-dependency issues observed in other methods, achieving approximation ratios of up to 0.9997 on random trees and 0.9767 on bipartite graphs at shallow depths.

Shortcut connections overcome locality bottlenecks in quantum optimisation algorithms

A transport-augmented QAOA attained an approximation ratio of 0.9997 on random trees, a sharp improvement over the 0.9226 achieved with standard methods at a comparable circuit depth. Previously, QAOA performance degraded rapidly with increasing network size due to a ‘locality bottleneck’ preventing efficient exploration of the solution space on large, sparsely connected networks. This bottleneck arises because at a given circuit depth p, local observables within QAOA can only depend on a bounded neighbourhood of the circuit interaction graph. Consequently, information struggles to propagate efficiently across the network, hindering the algorithm’s ability to find optimal or near-optimal solutions. Researchers at Krea University addressed this by deliberately adding shortcut connections to the quantum network, reducing the diameter of the interaction graph and enabling the algorithm to consider more distant relationships between variables. The shortcut couplings employed are unweighted and of the (XX+YY) type, scheduled to optimise transport within the network.

Reducing the effective interaction path to one boosted the approximation ratio from 0.7378 to 0.9767 on bipartite graphs with an initial diameter of four, achieved at a circuit depth of one, with a standard deviation of 0.0251 across nine different system sizes. This improvement is significant because it demonstrates a reduction in the impact of network size on performance. The standard QAOA struggles with scaling due to the exponential increase in computational resources required to maintain accuracy as the problem size grows. The Krea University team’s approach aims to mitigate this by enabling faster information exchange, thereby reducing the need for deeper circuits and more qubits. The use of exact finite-depth support recursions allowed for a rigorous analysis of the optimal shortcut placement, ensuring that the added couplings genuinely enhance the algorithm’s performance. These results indicate a move towards size-invariance, a vital step for scaling quantum algorithms, though simulations remain limited to relatively small problem instances and do not yet demonstrate a clear advantage on real-world hardware. The Krea University team demonstrated that augmenting the quantum approximate optimisation algorithm with deliberately placed shortcut connections sharply improves its performance on complex networks. For random trees initially spanning a diameter of ten, an approximation ratio of 0.9997 was achieved at a depth of two, exhibiting a very low standard deviation of 0.0001. Further investigation will focus on extending the simulations to larger, more realistic problem instances and exploring the potential for implementation on existing quantum computing platforms. The MaxCut cost Hamiltonian remains unchanged throughout this process, ensuring the optimisation objective is preserved.

Enhanced performance on sparse networks via quantum shortcut integration

The team’s refined quantum algorithm offers a potential pathway towards solving optimisation problems on increasingly complex networks, benefiting fields ranging from logistics to materials science. Optimisation problems are ubiquitous in these domains, often involving finding the best configuration from a vast number of possibilities. For example, in logistics, this could involve optimising delivery routes to minimise cost and time. In materials science, it could involve finding the lowest energy configuration of atoms in a molecule. The ability to efficiently solve these problems using quantum algorithms could lead to significant advancements in these fields. A key unanswered question remains, however, as the current work hinges on a specific type of network: sparse, high-diameter MaxCut instances. MaxCut is a classic combinatorial optimisation problem where the goal is to partition the vertices of a graph into two sets such that the number of edges crossing the partition is maximised. The sparsity and high diameter of the networks studied are crucial characteristics that exacerbate the locality bottleneck in standard QAOA. While the approach demonstrates a clear improvement over ma-QAOA, a competing method also designed to address locality issues, it has not yet been benchmarked against the broader field of quantum and classical algorithms.

It is important to acknowledge that these gains are presently limited to specific network types. Further research is needed to determine the extent to which this approach can be generalised to other types of optimisation problems and network topologies. The Krea University team overcame a fundamental constraint in quantum optimisation algorithms by enhancing the Quantum Approximate Optimisation Algorithm. Their innovation deliberately adds connections to the computational network, termed ‘shortcut couplings’, without altering the core optimisation problem, effectively shrinking the network’s diameter and the furthest distance information needs to travel. This addresses a ‘locality bottleneck’ hindering performance on sparse, high-diameter networks, a common challenge in complex optimisation tasks, and opens avenues for future research into adaptive shortcut placement strategies. The optimisation of these shortcut couplings is a critical aspect of the algorithm’s success, and exploring different scheduling methods could further improve performance. The (XX+YY) couplings facilitate the efficient transfer of quantum information across the network, enabling the algorithm to explore a larger portion of the solution space at a given depth. This work represents a significant step towards developing more scalable and efficient quantum algorithms for solving real-world optimisation problems.

The researchers successfully improved the performance of the Quantum Approximate Optimisation Algorithm on complex networks by adding optimised connections, known as shortcut couplings, to the computational network. This enhancement reduces the effective diameter of the network, overcoming a limitation that previously hindered performance on sparse, high-diameter problems. On bipartite networks, the approximation ratio increased from 0.7378 to 0.9767 at depth one, and on random trees, it improved from 0.9226 to 0.9997 at depth two. The team intends to investigate adaptive shortcut placement strategies to further refine the algorithm’s capabilities.