Theoretical work finds shortcut to solving the Max-Cut problem with a quantum computer

We are surrounded by optimization problems – for example, what’s the most efficient route for getting all your chores done on a Sunday? What’s the best way to pack a suitcase? Modern businesses can’t escape the importance of optimization problems, they’re critical in everything from charting shipping routes to setting prices. 

To solve such real-world examples, experts build mathematical models and explore computer algorithms capable of finding the optimal path through a problem. In many cases, as they scale, problems become intractable to even the most powerful classical supercomputers. Research suggests that for some problems, quantum algorithms offer some new promise. Our researchers have explored a quantum approach to a widely applicable optimization problem called “Max-Cut”, where one cuts a graph to snip as many vertices as possible.

Finding exact solutions to the Max-Cut problem in a reasonable amount of time would have practical applications in a wide range of situations, including supply chain management, machine scheduling, image recognition, quality control, fraud detection, patient diagnostics, and electric circuit design. For a generic graph, this problem is really hard: a computer scientist would call it “NP hard”. There is no known classical algorithm to solve Max-Cut for a generic graph whose runtime is polynomial in the number of vertices L, and it is strongly believed that no such classical algorithm exists. Many other useful optimization problems have a similar problem: they may simply be too expensive to solve exactly with classical computers. Back in the real world, this explains why many aspects of daily life run sub-optimally. Consider the experience of multiple drivers delivering a succession of small goods from the same vendor, often packaged in clearly oversized boxes. The costs of this sort of inefficiency accrue in terms of time, money, and environmental impact, locally and at the full scale of the global economy.

Our team has been working on applying a quantum solution to the Max-Cut problem based on the adiabatic theorem of quantum mechanics. Using the adiabatic theorem to solve an optimization problem involves encoding the problem into the qubits (setting up the Hamiltonian), then letting the system slowly evolve some parameter, carefully keeping it in the ground state the whole time. This method is an all-purpose solver for classically hard optimization problems, but it comes at a large computational cost: the “slow” evolution means applying lots of expensive gates to perform the many time steps needed. 

Our team figured out that instead of taking many expensive steps they could instead take a limited amount without destroying the convergence, as long as the optimization problem has a classical Hamiltonian. They call this “Floquet adiabatic evolution” and find that this approach reduces the required number of gates by several orders of magnitude.

Contrary to variational quantum algorithms such as Quantum Approximate Optimization Algorithm (QAOA), these low circuit depths can be achieved without classical optimization of parameters (whose sensitivity to noise and scaling behavior is not well understood).

Extrapolating their numerical simulation results, the team estimated that there may be a quantum speedup for this problem with a 2-qubit gate infidelity around 10^-5 and roughly 2000 qubits. Our H1 system already boasts a world-class 2-qubit gate infidelity of 8.8 × 10^-4, and we are well on our way towards even better fidelity with more qubits. You can see our roadmap here, and read the paper here.

In the meantime, the paper proposes that this method could be used as a quantum computing benchmark for application-oriented problems, making a valuable contribution to the Bench-QC project, of which Quantinuum is a founding member.