Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2404.16001 · Scientific Reports

Benchmarking a heuristic Floquet adiabatic algorithm for the Max-Cut problem

Etienne Granet, Henrik Dreyer

Published Aug 30, 2025• 1 citation
arXivHTMLPDF

Abstract

According to the adiabatic theorem of quantum mechanics, a system initially in the ground state of a Hamiltonian remains in the ground state if one slowly changes the Hamiltonian. This can be used in principle to solve hard problems on quantum computers. Generically, however, implementation of this Hamiltonian dynamics on digital quantum computers requires scaling Trotter step size with system size and simulation time, which incurs a large gate count. In this work, we argue that for classical optimization problems, the adiabatic evolution can be performed with a fixed, finite Trotter step. This "Floquet adiabatic evolution" reduces by several orders of magnitude the gate count compared to the usual, continuous-time adiabatic evolution. We give numerical evidence using matrix-product-state simulations that it can optimally solve the Max-Cut problem on 3-regular graphs in a large number of instances, with surprisingly low runtime, even with bond dimensions as low as [Formula: see text]. Extrapolating our numerical results, we estimate the resources needed for a quantum computer to compete with classical exact or approximate solvers for this specific problem.

DOI
10.1038/s41598-025-13923-2

Related papers

A Max K-Cut Implementation for QAOA in the Measurement Based Quantum Computing Formalism

Sebastiano Corli, Daniele Dragoni, Massimiliano Proietti +3 more

The MaxCut is a combinatorial problem which belongs to the NP-hard class. The algorithm to solve it can be mapped into a quantum system, where the optimal configuration matches the ground state of a target Hamiltonian. It is possible to implement the adiabatic theorem into the circuit model via the QAOA algorithm, by arbitrarily choosing from both the gate-based and the measurement-based quantum computing (MBQC) settings. Recently, the MaxCut problem has been generalized to the Max K-Cut version also in the MBQC frame, where K stands for the number of cuts to implement. Here, the QAOA algorithm for a Max K-Cut is solved for a graph with arbitrary number of vertices V and number of cuts K scaling as a power of 2, along with the circuit depth p. The problem is solved on a emulator based on classical HPC resources. In order to test the performances of a Max K-cut implemented in the MBQC frame, we report how the average runtime and the approximation ratio scale by increasing V, K and p, comparing the results from two different topologies of graphs, 2-regular graphs with null weights on the diagonals versus the the fully-connected graphs. Eventually, the approximation ratio, evaluated as a parameter of success, is shown to yield optimal performances.

IEEE International Conference on Quantum Computing and Engineering (QCE)•Sep 17, 2023•12 citations

Optimal Solution of Max-Cut Problem Using Quantum Adiabatic Approximation

WANG Fumin, NI Ming, ZHOU Ming, WU Yongzheng

When using classical approximation algorithm to solve the max-cut problem,the time complexity increases with the complexity of graph.In order to improve the solution efficiency,this paper uses quantum adiabatic approximation algorithm to solve the ground state for Hamiltonian of max-cut problem,and the ground state value is the optimal solution.The time complexity is independent of the number of vertices and edges of graph using quantum adiabatic approximation algorithm,and the max-cut problem can be calculated within finite steps.The computing process is based on the ProjectQ software developed.By establishing the evolutionary path from initial Hamiltonian to max-cut problem Hamiltonian,the change of the expected value is analyzed to determine whether the algorithm can find the optimal solution of max-cut problem or not.Numerical analysis results show that,this algorithm can effectively improve the efficiency of solving the max-cut problem,the accuracy of solution is 0.999 9 for 3-vertex undirected graph and 6-vertex undirected sparse graph,and the results for the 6-vertex undirected complete graph is 0.969 6.

•Jan 1, 2020•0 citations

A comprehensive benchmark of an Ising machine on the Max-Cut problem

Salwa Shaglel, Markus Kirsch, Mårten Winkler +4 more

QUBO formulations of combinatorial optimization problems allow for solving them using various quantum heuristics. While large-scale quantum computations are currently still out of reach, we can already numerically test such QUBO formulations on a perhaps surprisingly large scale. In this work, we benchmark Fujitsu’s Digital Annealer (DA) on the Max-Cut problem, which captures the main complexity of the QUBO problem. We make a comprehensive benchmark against leading other heuristic algorithms on graphs with up to 53,000 variables by focusing on the wall-clock time. Moreover, we compare the DA performance against published performance results of the D-Wave hybrid quantum-classical annealer and the recently proposed QIS3 heuristic. Based on performance statistics for over 2,000 graphs from the MQLib, we find that the DA yields competitive results. We hope that this benchmark demonstrates the extent to which large QUBO instances can be heuristically solved today, yielding consistent results across different solvers.

•Oct 21, 2025•0 citations

Alternative adiabatic quantum dynamics with algorithmic applications

Joseph Cunningham, Jérémie Roland

In adiabatic quantum computing the aim is to track an eigenstate as the Hamiltonian changes. In the usual setup this is achieved using the natural time-dependent Hamiltonian evolution of the system and the main technical tool is the adiabatic theorem. We propose several alternative processes that achieve the same goal, but can easily be implemented on a gate-based quantum computer without the overhead of simulating time-dependent Hamiltonian evolution. We give a general framework for deriving `adiabatic' theorems for these processes. As an application, we give various algorithms for solving the Quantum Linear Systems Problem (QLSP) with optimal scaling in the condition number. One of these algorithms was previously developed in [Cunningham, Roland 2024] and another can be seen as a randomised version of the discrete adiabatic algorithm of [Costa et al. 2022]. We also describe versions of Trotterisation in our framework, which allows several results from [An et al. 2025] to be reproduced in a randomised setting. In particular, bounds on the Trotter error in terms of the fidelity are obtained that are asymptotically better than the standard bounds.

quant-pharXiv:2605.30110•May 29, 2026•0 citations

Large time-step discretization of adiabatic quantum dynamics

Dong Un An, Pedro C. S. Costa, Dominic William Berry

Adiabatic quantum computing is a general framework for preparing eigenstates of Hamiltonians on quantum devices. However, its digital implementation requires an efficient Hamiltonian simulation subroutine, which may introduce extra computational overhead or complicated quantum control logic. In this work, we show that the time-step sizes in time discretization can be much larger than expected, and the overall complexity is greatly reduced. Remarkably, regardless of the general convergence order of the numerical method, we can choose a uniform time-step size independent of tolerated error and evolution time for sufficiently accurate simulation. Furthermore, with the boundary cancellation condition where the continuous diabatic errors are exponentially suppressed, we provide strong evidence for a superpolynomial convergence of first-order Trotter with uniform time-step size. We apply our analysis to the example of adiabatic unstructured search and show several preferable features of the Trotterized adiabatic approach: It can match the Grover lower bound, it does not require knowledge of the number of marked states, and its performance can be asymptotically comparable with that of the quantum approximate optimization algorithm.

arXiv:2509.00171•Physical Review Research•Oct 2, 2026•0 citations

Study on quantum adiabatic approximate solution of max-cut with different vertices

XinKai Gao, Ming Ni, Ming Quan Zhou +1 more

The max-cut is used to solve maximum partition for given undirected weighted graph, the sum of the weights of all sides between the subset of vertex and complementary subset obtains a maximum value. Quantum adiabatic approximation is used to design system Hamiltonian Hsys, and the ground state of system Hamiltonian corresponds to the solution of max-cut problem. System Hamiltonian Hsys changes slowly along with initial Hamiltonian Hini follow the evolution path of Hamiltonian Hmax, and then the ground state of Hamiltonian can be calculated. By analyzing the change of expected value with evolution time, one can judge whether the approximate solution is the optimal solution or not. In this paper, we test the adiabatic evolution of complete undirected graph with vertices from 6 to 14. Based on Python and Project Q package, we write a solver program that sets parameters according to the number of vertices and edges of undirected graph, and then obtain experimental results by measuring the state of qubits in quantum registers. It can be inferred from experimental results that for a complete undirected graph with less vertices, expected value can converge well, and then the optimal solution of max-cut problem can be obtained. When the number of vertices increase, the energy variation of Hamiltonian become more complex and the expected value is hard to converge.

Applied Optics and Photonics China (AOPC): Optoelectronics and Nanophotonics•Nov 5, 2020•0 citations
According to the adiabatic theorem of quantum mechanics, a system initially in the ground state of a Hamiltonian remains in the ground state if one slowly changes the Hamiltonian. This can be used in principle to solve hard problems on quantum computers. Generically, however, implementation of this Hamiltonian dynamics on digital quantum computers requires scaling Trotter step size with system size and simulation time, which incurs a large gate count. In this work, we argue that for classical optimization problems, the adiabatic evolution can be performed with a fixed, finite Trotter step. This "Floquet adiabatic evolution" reduces by several orders of magnitude the gate count compared to the usual, continuous-time adiabatic evolution. We give numerical evidence using matrix-product-state simulations that it can optimally solve the Max-Cut problem on 3-regular graphs in a large number of instances, with surprisingly low runtime, even with bond dimensions as low as [Formula: see text]. Extrapolating our numerical results, we estimate the resources needed for a quantum computer to compete with classical exact or approximate solvers for this specific problem.
The MaxCut is a combinatorial problem which belongs to the NP-hard class. The algorithm to solve it can be mapped into a quantum system, where the optimal configuration matches the ground state of a target Hamiltonian. It is possible to implement the adiabatic theorem into the circuit model via the QAOA algorithm, by arbitrarily choosing from both the gate-based and the measurement-based quantum computing (MBQC) settings. Recently, the MaxCut problem has been generalized to the Max K-Cut version also in the MBQC frame, where K stands for the number of cuts to implement. Here, the QAOA algorithm for a Max K-Cut is solved for a graph with arbitrary number of vertices V and number of cuts K scaling as a power of 2, along with the circuit depth p. The problem is solved on a emulator based on classical HPC resources. In order to test the performances of a Max K-cut implemented in the MBQC frame, we report how the average runtime and the approximation ratio scale by increasing V, K and p, comparing the results from two different topologies of graphs, 2-regular graphs with null weights on the diagonals versus the the fully-connected graphs. Eventually, the approximation ratio, evaluated as a parameter of success, is shown to yield optimal performances.
When using classical approximation algorithm to solve the max-cut problem,the time complexity increases with the complexity of graph.In order to improve the solution efficiency,this paper uses quantum adiabatic approximation algorithm to solve the ground state for Hamiltonian of max-cut problem,and the ground state value is the optimal solution.The time complexity is independent of the number of vertices and edges of graph using quantum adiabatic approximation algorithm,and the max-cut problem can be calculated within finite steps.The computing process is based on the ProjectQ software developed.By establishing the evolutionary path from initial Hamiltonian to max-cut problem Hamiltonian,the change of the expected value is analyzed to determine whether the algorithm can find the optimal solution of max-cut problem or not.Numerical analysis results show that,this algorithm can effectively improve the efficiency of solving the max-cut problem,the accuracy of solution is 0.999 9 for 3-vertex undirected graph and 6-vertex undirected sparse graph,and the results for the 6-vertex undirected complete graph is 0.969 6.
QUBO formulations of combinatorial optimization problems allow for solving them using various quantum heuristics. While large-scale quantum computations are currently still out of reach, we can already numerically test such QUBO formulations on a perhaps surprisingly large scale. In this work, we benchmark Fujitsu’s Digital Annealer (DA) on the Max-Cut problem, which captures the main complexity of the QUBO problem. We make a comprehensive benchmark against leading other heuristic algorithms on graphs with up to 53,000 variables by focusing on the wall-clock time. Moreover, we compare the DA performance against published performance results of the D-Wave hybrid quantum-classical annealer and the recently proposed QIS3 heuristic. Based on performance statistics for over 2,000 graphs from the MQLib, we find that the DA yields competitive results. We hope that this benchmark demonstrates the extent to which large QUBO instances can be heuristically solved today, yielding consistent results across different solvers.
In adiabatic quantum computing the aim is to track an eigenstate as the Hamiltonian changes. In the usual setup this is achieved using the natural time-dependent Hamiltonian evolution of the system and the main technical tool is the adiabatic theorem. We propose several alternative processes that achieve the same goal, but can easily be implemented on a gate-based quantum computer without the overhead of simulating time-dependent Hamiltonian evolution. We give a general framework for deriving `adiabatic' theorems for these processes. As an application, we give various algorithms for solving the Quantum Linear Systems Problem (QLSP) with optimal scaling in the condition number. One of these algorithms was previously developed in [Cunningham, Roland 2024] and another can be seen as a randomised version of the discrete adiabatic algorithm of [Costa et al. 2022]. We also describe versions of Trotterisation in our framework, which allows several results from [An et al. 2025] to be reproduced in a randomised setting. In particular, bounds on the Trotter error in terms of the fidelity are obtained that are asymptotically better than the standard bounds.
Adiabatic quantum computing is a general framework for preparing eigenstates of Hamiltonians on quantum devices. However, its digital implementation requires an efficient Hamiltonian simulation subroutine, which may introduce extra computational overhead or complicated quantum control logic. In this work, we show that the time-step sizes in time discretization can be much larger than expected, and the overall complexity is greatly reduced. Remarkably, regardless of the general convergence order of the numerical method, we can choose a uniform time-step size independent of tolerated error and evolution time for sufficiently accurate simulation. Furthermore, with the boundary cancellation condition where the continuous diabatic errors are exponentially suppressed, we provide strong evidence for a superpolynomial convergence of first-order Trotter with uniform time-step size. We apply our analysis to the example of adiabatic unstructured search and show several preferable features of the Trotterized adiabatic approach: It can match the Grover lower bound, it does not require knowledge of the number of marked states, and its performance can be asymptotically comparable with that of the quantum approximate optimization algorithm.
The max-cut is used to solve maximum partition for given undirected weighted graph, the sum of the weights of all sides between the subset of vertex and complementary subset obtains a maximum value. Quantum adiabatic approximation is used to design system Hamiltonian Hsys, and the ground state of system Hamiltonian corresponds to the solution of max-cut problem. System Hamiltonian Hsys changes slowly along with initial Hamiltonian Hini follow the evolution path of Hamiltonian Hmax, and then the ground state of Hamiltonian can be calculated. By analyzing the change of expected value with evolution time, one can judge whether the approximate solution is the optimal solution or not. In this paper, we test the adiabatic evolution of complete undirected graph with vertices from 6 to 14. Based on Python and Project Q package, we write a solver program that sets parameters according to the number of vertices and edges of undirected graph, and then obtain experimental results by measuring the state of qubits in quantum registers. It can be inferred from experimental results that for a complete undirected graph with less vertices, expected value can converge well, and then the optimal solution of max-cut problem can be obtained. When the number of vertices increase, the energy variation of Hamiltonian become more complex and the expected value is hard to converge.