Combinatorial optimisation problems involve finding the best solution from a finite set of possible solutions, where the number of possibilities can grow exponentially with the problem size. For example, consider a graph partitioning problem like MaxCut, where the objective is to split the nodes of a graph into two groups such that the maximum number of edges have endpoints in both groups. Put simply, imagine you have dots (nodes) connected by lines (edges). Your task is to color these dots in two colours, red and blue, in a way that as many lines as possible connect a red dot to a blue dot. Even for a relatively small number of nodes, the number of ways to divide them into two groups grows exponentially. Specifically, with each additional node, the number of possible divisions doubles, making the problem increasingly difficult to solve as the size of the graph grows.
For such kind of problems, finding the perfect solution isn't always feasible, so we aim for a "good enough" solution through approximation algorithms. Yet, these algorithms come with a catch: the quicker you want an answer, the more you may have to compromise on its quality, meaning how close it is to the best possible solution. Quantum computers offer a promising alternative, harnessing quantum mechanics to potentially expedite this process significantly. With capabilities like superposition, they can simultaneously explore multiple potential solutions, and through quantum parallelism, they significantly cut down the exploration steps. Quantum entanglement further enhances their ability to process complex, intertwined data more naturally. These advantages suggest that quantum algorithms could not only find approximate solutions faster but also improve the quality of these solutions compared to classical algorithms.
The Quantum Approximate Optimization Algorithm (QAOA) is a quantum algorithm designed specifically to tackle combinatorial optimisation problems. While in theory, QAOA has the potential to surpass the performance of the best classical algorithm, its practical implementation faces significant challenges due to physical constraints like noise, limited connections between quantum bits, and errors in preparing and measuring quantum states. These issues make it challenging to build large and deep quantum circuits, which are necessary for the algorithm to work efficiently. The key question is whether QAOA can be adapted or improved to overcome these challenges while still taking full advantage of quantum computing's potential.
Researchers from the Australian Research Council's Centre of Excellence for Quantum Computation and Communication Technology (CQC2T), at the Australian National University (ANU), in collaboration with A*STAR Quantum Innovation Centre in Singapore, have developed a new quantum algorithm known as eXpressive QAOA (XQAOA). Detailed in their paper
"An Expressive Ansatz for Low-Depth Quantum Approximate Optimisation" published in IOP Quantum Science and Technology, XQAOA enhances the traditional QAOA by overparameterizing its quantum circuits. This modification increases the circuits' 'degrees of freedom,' allowing them to explore solutions more efficiently and with greater flexibility, which in turn enables XQAOA to use fewer quantum resources for effective implementation with shallower quantum circuits without sacrificing performance. In tests with the MaxCut problem, XQAOA outperformed the well-known classical Goemans-Williamson algorithm, demonstrating its superior problem-solving capabilities.
Lead author V Vijendran, an undergraduate researcher at both ANU and A*STAR, recalls studying the Goemans-Williamson algorithm in his computer science classes. This algorithm is considered a foundational achievement in approximation algorithms and complexity theory, where it was long thought nearly impossible to devise an algorithm that could outperform the Goemans-Williamson algorithm for solving the MaxCut problem. "While the Goemans-Williamson algorithm is specifically designed for the MaxCut problem, XQAOA is a versatile, problem-independent algorithm that can be applied to a wide range of combinatorial problems beyond MaxCut. If XQAOA can outperform Goemans-Williamson on MaxCut, it is also likely to excel in other complex problems such as supply chain optimization, job-shop scheduling, vehicle routing, and so on. In situations where no definitive best classical algorithm exists, XQAOA could prove especially beneficial," says Mr Vijendran.
Aritra Das, a PhD student at ANU and co-author of the study, is fascinated by the foundational aspects of their newly proposed algorithm. He remarks, "The pivotal role of overparameterised entangling operations in smoothing the unruly cost landscapes typical of quantum circuits was unforeseen and it profoundly challenged our previous assumptions." Furthermore, he adds, "The significant contribution of mixer rotations in enhancing the algorithm's expressivity also took us by surprise." Mr Vijendran uses a relatable analogy to explain overparameterisation: Consider the task of finding your favorite ride in an amusement park with two maps. The first shows only the main paths, while the second details every possible shortcut and side route. At first glance, the more detailed map might seem overwhelming. Yet, it's this complexity that actually guides you more effectively, avoiding dead ends and unnecessary detours you'd likely encounter with the simpler map. This mirrors the essence of overparameterisation in optimisation. By introducing more parameters, the model gains flexibility and a richer set of pathways, facilitating the discovery of the optimal solution without being ensnared by less ideal options. In essence, just as the detailed map directs you more smoothly and directly to your goal, overparameterisation clears the path to the most efficient solution.
The development of the XQAOA marks a significant advancement in quantum computing, showcasing its ability to outperform conventional methods for solving complex problems. This breakthrough not only boosts our computational capacities but also opens new avenues for quantum technologies to tackle real-world problems across various sectors. For instance, it could be used to optimise public transportation systems, such as improving the scheduling of trains and buses to avoid delays. It could also help in planning more efficient delivery routes that save time and reduce fuel consumption, design financial models that predict stock market trends more accurately, or accelerate the development of new medications by analysing vast amounts of data more quickly. As we continue to surmount technical barriers and enhance quantum circuit designs, XQAOA and similar technologies hold great promise for revolutionising industries by solving some of their most complex issues with unprecedented efficiency and precision.