Researchers have come up with a radical new algorithm to significantly boost the performance of quantum computers in certain problems, and also show that classical solutions can be just as good in other circumstances.

Quantum computers leverage the principles of quantum mechanics which enables them to perform some complex calculations at speeds far in excess of that of conventional computers. Like their classical counterparts, quantum computers operate by executing an algorithm composed of precise set of instructions.

“Our new algorithm effectively shortcuts the task of navigating through immense solution spaces, making it a powerful tool for solving classically hard optimization problems," said V Vijendran, an ANU student and lead author of the research.

Practical quantum computing faces challenges from noise, state preparation errors, measurement errors and limited connections, often restricting the size of quantum circuits, and the number of operations that can be implemented - known as the depth of the circuit. 

However, this new algorithm, published in Quantum Science and Technology is designed to overcome these obstacles, and so is easier to implement on the current generation of quantum computers. 

"This means using fewer quantum resources and shallower quantum circuits without sacrificing performance," said Mr Vijendran, who conducted his undergraduate research at ANU with the ARC Centre of Excellence for Quantum Computation and Communication Technology (CQC2T) and A*STAR in Singapore.

Mr Vijendran tested his algorithm on called MaxCut, which is of a class known as combinatorial optimization problems, which require finding the best solution from a finite set of possibilities. MaxCut deals with partitioning points on a graph in a way that maximises connections between them - the challenge is that the number of possibilities can grow exponentially with the problem size, in this case the number of points.

"For these types of problems, finding the perfect solution is often impractical," said Mr Vijendran. 

"Instead, we use approximation algorithms to find a solution that is good enough. However, there's a trade-off: the faster you want a solution, the more you may have to compromise on its quality, meaning it might not be as close to the optimal solution."

The best-known approximation algorithm for the MaxCut problem is the 1994 Goemans-Williamson algorithm, which is a classical algorithm.

In 2014, researchers at the Massachusetts Institute of Technology first turned to quantum computing. Their approach was known as the Quantum Approximate Optimization Algorithm (QAOA) and starts with a quantum state that is an initial guess, and aims to evolve that to the state that solves the given problem, by adjusting parameters controlling the evolution. Ongoing research into QAOA's efficacy suggests that, in theory, with sufficiently deep quantum circuits, QAOA has the potential to outperform the state-of-the-art Goemans-Williamson algorithm.

But as yet, it is impossible to test the potential, as quantum computing hardware is not good enough, Mr Vijendran said. 

“In practice the hardware is noisy which means that with many sequential operations, the quality of the solution degrades.”

"Even when fault-tolerant quantum computing becomes a reality, QAOA can still get stuck in traps in its search throughout the parameter space, potentially negating any quantum advantage."

While seeking ways to overcome these limitations, Mr Vijendran drew inspiration from neural networks. One advantage of neural networks is their ability to learn and approximate various functions, especially when the model has more parameters than the function it aims to learn and approximate, a case called overparameterization.

Mr Vijendran anticipated that by overparameterizing QAOA, it would be possible to fine-tune the variational parameters more effectively, potentially leading to better performance and overcoming some of the inherent limitations.

Mr Vijendran teamed up with ANU PhD student Aritra Das and A*STAR scientist Dr Dax Enshan Koh, under the supervision of Dr Syed Assad and Professor Ping Koy Lam to apply this approach to QAOA.

To evaluate the effectiveness of the algorithm, the team derived analytical expressions quantifying the performance, and classically simulated them.

Their algorithm, named eXpressive QAOA (XQAOA), outperformed the standard QAOA, its variants, and the classical state-of-the-art Goemans-Williamson algorithm on the MaxCut problem for graphs with 128 and 256 vertices (equivalent to 128 and 256 qubits) - even when using a minimum number of operations.

Unlike QAOA, XQAOA did not suffer from traps, significantly easing the evolution of the quantum state.

More surprisingly, they found their algorithm converged to a classical solution, Mr Vijendran explained. 

“The XQAOA begins with an entangled trial quantum state. Through the process of fine-tuning the parameters so the algorithm converges to an optimum, the entanglement gradually diminishes, along with other quantum features such as superposition, and the resulting state is a classical state.”

The finding underscores that quantum computers will not supersede classical computers, but offer a complementary approach to solving problems, Mr Vijendran said. 

“There is a misconception that quantum computers offer all-encompassing, universal solutions. But classical solutions prove more efficient for certain tasks. 

“It’s a mistake to immediately choose quantum methods to solve problems without first considering whether the quantum approach outperforms classical methods.

"These problems, include real-world optimization challenges such as transport optimization, vehicle routing, scheduling, and planning—issues highly relevant to industry." 

While their current research indicates no quantum advantage for the set of problems they considered, Mr Vijendran remains optimistic.

"As we tackle more complex problems, we may discover scenarios where quantum computing offers a distinct advantage," he said.