Benchmarking a heuristic Floquet adiabatic algorithm for the Max-Cut problem
Etienne Granet Henrik Dreyer



=1




















equationsection


fillbetween











    compat=1.18apsrev4-1Quantinuum, Leopoldstrasse 180, 80804 Munich, Germany
        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  problem on 3-regular graphs in a large number of instances, with surprisingly low runtime, even with bond dimensions as low as D=2. 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.
        
        Benchmarking a heuristic Floquet adiabatic algorithm for the Max-Cut problem
            Etienne Granet and Henrik Dreyer
            April 29, 2024
        ============================================================================
        
        Introduction.— The adiabatic theorem of quantum mechanics provides an all-purpose solver for classically hard optimization problems <cit.>. As convergence to the solution requires to control a slow, continuous-time dynamics which comes with a large gate overhead on digital quantum computers, these approaches are mostly seen as long-term fault-tolerant era methods. In the current and near-term stage of quantum computing hardware, variational algorithms such as QAOA are preferred for their low circuit depth <cit.>. These can be interpreted as a kind of adiabatic evolution with a finite number of gates, in which Trotter steps are optimized to minimize the energy. A major challenge of variational algorithms for classical optimization problems is that they replace a hard optimization problem by another optimization problem that can be just as difficult to solve <cit.>.
        
        In this work, we present evidence for the fact that finite Trotter steps can be used in the adiabatic algorithm (instead of costly continuous-time dynamics) while preserving guarantees to reach the ground state in the slow evolution regime. This holds true only for optimization problems where the target Hamiltonian is classical. The dynamics imposed on the system is then always a Floquet dynamics that alternates between different Hamiltonians during a finite time. Using matrix product state (MPS) simulations of these dynamics, we will show two main points. First, the “Floquet" adiabatic algorithm with a finite Trotter step δ t succeeds in finding the optimal solution to a  problem on a 3-regular graph in a very large number of instances, despite the number of samples being a minuscule part of the state space. Extrapolating our numerics, we make an estimate for the resources required by a quantum computer to reach system sizes out of reach of classical solvers, whether exact or approximate. Second, we observe that, surprisingly, using a MPS with a small bond dimension does not (in the vast majority of cases) prevent the adiabatic algorithm to find the optimal solution. This yields a new classical approach to approximately solve the  problem with good practical performance that is very different from usual solvers.
        
        
        
        The Max-Cut problem.— The  problem is a paradigmatic classical optimization problem. Let G be a graph on a set of L vertices V={1,...,L} with a set of edges E⊂ V^2. This problem consists in finding a partition V=V_0∪ V_1 with V_0∩ V_1=∅ that maximises the number of edges (i,j)∈ E that connect the two subsets of vertices, namely i∈ V_0 and j∈ V_1. This number of edges is often referred to as the size of the cut. This problem is equivalently formulated as finding the ground state of the Ising Hamiltonian
        
            H=∑_(i,j)∈ EZ_iZ_j .
        
        Indeed, a basis of eigenstates of H is trivially given by product states in the Z basis |b_1...b_L⟩ with b_j∈{0,1}, and their eigenvalue is -c+(|E|-c)=-2c+|E| where c is the number of edges (i,j)∈ E such that b_i=0 and b_j=1. Hence finding a product state that minimizes the energy is equivalent to finding a configuration that maximizes c, i.e. solving the  problem on the graph. 
        In this work we will focus on 3-regular graphs, namely graphs where each vertex has exactly 3 neighbours.
        
        The  problem for a generic graph is NP-hard <cit.>. There is no known classical algorithm to solve  for a generic graph whose runtime is polynomial in the number of vertices L, and it is strongly believed that such an algorithm does not exist. Finding a partition with a cut size c' that approximates the maximal cut size c up to a ratio 16/17≈ 0.941, namely c'>16c/17, is also known to be NP-hard, and so cannot be solved in a time polynomial in L neither <cit.>. In practice, there exist however highly optimized generic exact solvers that can solve graphs of intermediate sizes, despite their runtime being exponential in L<cit.>. For larger graphs or approximate solutions, there exists a plethora of approximate solvers that are used in the industry <cit.>. 
        For 3-regular graphs, there is a polynomial time algorithm with approximation ratio ≈ 0.9326<cit.>, and going beyond 331/333≈ 0.994 is known to be NP-hard <cit.>. 
        Due to the high relevance of this kind of optimization problems in the industry, any improvement in the runtime of these solvers can have significant impact <cit.>.
        
        The adiabatic algorithm.— One of the workhorse of quantum computing is the adiabatic algorithm and its variants. We consider the following time-dependent Hamiltonian for 0≤ s≤ 1
            H(s)=-(1-s)∑_j=1^L X_j+s∑_(i,j)∈ EZ_iZ_j .
        
        The ground state of H(s) at s=0 is the product state |++...+⟩, while the ground state of H(s) at s=1 solves the  problem on the graph. Let us consider |ψ(t)⟩ a state equal to |++...+⟩ at time t=0, and evolve it for a time T with the time-dependent Hamiltonian H(t/T), namely
        
            ∂_t |ψ⟩=iH(t/T)|ψ⟩ .
        
        No crossings can occur in H(t/T) for 0<t<T due to the Perron-Frobenius theorem <cit.>. Hence, according to the adiabatic theorem, provided the time evolution is slow enough, i.e. if T is large enough, then |ψ(t)⟩ remains in the ground state of H(t/T) for all t. In particular the state prepared at time t=T becomes closer to a  solution as T grows larger. On a classical computer, computing this time evolution is strongly believed to be exponentially costly in L or T depending on the method used, see e.g. <cit.> for MPS simulations. On a quantum computer however, this time evolution can be computed with a runtime that is polynomial in system size L and simulation time T<cit.>. The scaling of the runtime with L to solve  with the adiabatic state preparation depends thus crucially on the simulation time T(L) that is required for |ψ(T)⟩ to have an appreciable overlap with a  solution. 
        
        Implementing the adiabatic evolution (<ref>) on a gate-based quantum computer requires to discretize the time evolution, for example with a Trotter decomposition. We define the circuit
        
            U(M,δ t)=W_1(δ t)...W_2/M(δ t)W_1/M(δ t) ,
        
        with M an integer, δ t some time step, and where we denote for a real 0≤ s≤ 1
            W_s(δ t)=∏_(j,k)∈ Ee^isδ t Z_jZ_k∏_j=1,...,L e^-i(1-s)δ t X_j .
        
        Taking δ t=T/M, we have according to the Trotter formula
        
            M→∞lim U(M,TM)|+...+⟩=|ψ(T)⟩ .
        
        The number of steps M to take to reach precision ϵ on the prepared state is M∼T^2L/ϵ<cit.>. This gives a total gate count ∼T^2L^2/ϵ. Previous works in different contexts have suggested more favorable scalings <cit.>. There exist other algorithms for running adiabatic evolution with a better scaling, but they are more involved <cit.>. Implementations of the adiabatic algorithm for classical optimization problems have been done in the past in various works, whether classically simulated or on actual hardware <cit.>. 
        
        
        
        The Floquet adiabatic algorithm.— Instead of scaling the time step δ t to 0, as would be done to minimize errors due to Trotterization, let us fix the time step δ t to some finite value δ t=1/n for a real n, take the adiabatic time T to be an integer multiple of 1/n, and fix the number of Trotter steps M=nT. The operator that we implement is thus 𝒰(T)≡ U(nT,1n) given by
        
            𝒰(T)=W_1(1n)...W_2/(nT)(1n)W_1/(nT)(1n) ,
        
        with W_s(δ t) defined in (<ref>).
        
        The operator 𝒰(T)does not implement the standard adiabatic algorithm. Even when T→∞, the time step is finite and the time evolution alternates between purely X_j evolution and purely Z_jZ_k for a finite duration. In particular, the state of the system is never in the ground state of H(s) when 0<s<1, even when T→∞. However, the spectrum of the unitary operator W_s(δ t) when s goes from 0 to 1, goes smoothly from {e^-iδ t x} with x eigenvalues of ∑_j=1^L X_j, to {e^iδ t z} with z the eigenvalues of ∑_(j,k)∈ EZ_jZ_k. Let us write
        
            W_s(δ t)=e^iδ tF_δ t(s) ,
        
        with F_δ t(s) called Floquet Hamiltonian. When T→∞, because the Trotter step δ t is kept finite, we still alternate with time evolution e^isδ t Z_jZ_k and time evolution  e^-i(1-s)δ t X_j. However, the rate at which s is modified from one term W_s(δ t) to the next decreases with T. In the limit T→∞, we thus implement an adiabatic evolution with respect to F_δ t(s) instead of H(s). Now, the crucial point is that, because H(s=1) is a sum of commuting terms, we have
        
            F_δ t(s=1)= H(s=1) .
        
        This holds true only when targeting classical optimization problems, where the Hamiltonian H is classical. As a consequence, according to the adiabatic theorem, if there is no crossings in the Floquet Hamiltonian F_δ t(s), then a system initially prepared in the ground state of ∑_j=1^L X_j will converge to the ground state of H when T→∞.
        
        
        
        Floquet  adiabatic algorithm for .— This observation motivates us to study the following heuristic algorithm that we implement for solving , dubbed Floquet  adiabatic algorithm (FAA) <cit.>. 
        
        The algorithm takes as input a graph G on L vertices, and as parameters a time step δ t fixed, a number of shots N_S and a stopping criterion. 
        
        The algorithm proceeds as follows. We take an arbitrary initial value of adiabatic time T. We prepare the initial state in the product of |+⟩ at each site,  apply 𝒰(T) defined in (<ref>), and then measure the state in the Z basis, collecting L measurement outcomes, one for each vertex. We repeat this N_S times, obtaining N_S collections of L measurement outcomes. From them, we compute the value taken by H=∑_(i,j)∈ EZ_iZ_j on each of the N_S shots, and define m_G(T) as the minimal value obtained from these N_S shots. We repeat this process for the same graph G, but with increasing T, collecting a sequence m_G(T_1),...,m_G(T_q), until we reach the stopping criterion decided in advance. Then m_G^* is defined as the minimal value of the m_G(T_i) over each of the times T_i assessed. The configuration of spins Z_i=± 1 realizing this minimal energy can be read off from the corresponding measurement outcomes.
        
        Numerical simulations.— The runtime of adiabatic algorithms is most often out of reach of analytical study. In order to evaluate the runtime of FAA, we now present numerical simulations. Exact simulation of FAA with state-vector simulations is exponentially costly in the number of vertices L, limiting this approach to L⪅ 30. To reach larger system sizes, we use Qiskit's MPS simulator with a finite bond dimension D<cit.>. This provides only an approximation to the exact FAA, but the approximation should improve as D increases. The simulation runtime for one graph G and one adiabatic time T is then 𝒪(LTD^3). In the rest of this work, unless stated otherwise we will fix the number of shots per circuit to be N_S=10^3 and Trotter step δ t=1/4.
        
        
        
        
        
        
        We start with presenting in Figure <ref> some runs of the algorithm in the following setting. We fix the number of vertices to L=98 and we generate random 3-regular graph G on these L vertices. Using the exact  solver <cit.>, the maximal cut on these graphs can be found classically in reasonable time on a laptop for system sizes up to L∼ 300, and we denote m_G the exact minimal energy of graph G.  For each of these graphs, we obtain some numerical result m_G(T') for T'=1,2,...,T, and define the minimum m^*_G(T)=min_1≤ T'≤ Tm_G(T'). From this, one obtains an approximation ratio r(T) for the maximal cut in this graph, as r(T)=-m^*_G(T)+3L/2/-m_G+3L/2. Then we report in the top panels of Figure <ref> the value 1-r(T) as a function of T, plotting both individual trajectories for each random graph G, and their average. In the bottom panels, we report histograms of the minimal adiabatic time T_*(G) for which the optimal solution is found, across different graphs G. 
        
        
        
        
        
        
        
        From these results, we make the following three observations. Firstly and most importantly, for all the graphs we tried, we always find the optimal solution m_G provided the adiabatic time T is large enough. This holds true despite the total number of configurations sampled per graph N_ST⪅ 10^5 being well below the total number of configurations 2^L∼ 10^30. We emphasize that, remarkably, this holds true even for bond dimension D=2. In Table <ref> we indicate the number of instances tested in this work for δ t=1/4 across different system sizes L and bond dimensions D, giving a statistical upper bound for the proportion of graphs for which FAA would fail for different D and L. Second, we observe that while variations of the curve m_G(T) are quite pronounced for D=2 across different graphs G, they are much smaller for bond dimension D=8. This suggests that the exact time evolution (obtained for D→∞) would present only low variation for different graphs G. This is confirmed by the bottom left panel, where the distribution of the smallest adiabatic times required to find the optimal solution gets narrower as the bond dimension is increased. On the right bottom panel, we see conversely that at fixed bond dimension, this distribution becomes broader as the system size is increased, reflecting the fact that a fixed bond dimension D will capture a smaller portion of the Hilbert space as L increases. Third, the logarithmic scale plot clearly displays two regimes. There is a first regime up to e.g. time T≈ 7 for D=8 where the improvement is slow. After that point, there is a sharp transition to a fast decay of the energy error, compatible with a power-law behaviour ∼ 1/T^2. There is possibly a third regime with exponential decay at larger times. These scalings would matter when targetting a certain approximation ratio <1 instead of the optimal solution.
        
        
        
        We move on to the study in Figure <ref> of the scaling with number of vertices L of the minimal adiabatic time T_*(L) to find the optimal solution. Indeed, a crucial point in assessing the viability of classical or quantum algorithm is to understand how its complexity scales with input parameters. Given a 3-regular graph G on L vertices, we run FAA starting from adiabatic time T=1 and increasing T by 1 at each iteration, until the maximal cut has been found (computed with ), denoting T_* the corresponding value of T. The first conclusion from this numerics is that, again, we always end up finding the optimal cut when increasing T, even if the fraction of configurations explored is several tens of orders of magnitude below 1. In the leftmost panel of Figure <ref>, we show T_*(L) the average of T_*, as a function of number of vertices L. Up to system sizes studied, the numerics could be compatible with a linear scaling for bond dimension D=2 or D=64 for example, although the scaling is strongly expected to be exponential in L due to NP-hardness. This exponential behaviour should become visible at larger values of L, but these sizes become unreachable by exact solvers. In the second panel of Figure <ref>, we plot the same numerics but for Trotter step δ t=1. The linear scaling for these small to intermediate system sizes is here well visible, as well as the considerably smaller average T^* obtained with state-vector simulation (or D=∞) compared to MPS with D=2.
        
        Next, we investigate in the two rightmost panels of Figure <ref> the effect of the finite Trotter step δ t=1/n. For δ t=π/2, since we have e^iδ t H(s)=± e^iπ s/2(∑_j X_j+∑_(j,k∈ E)Z_jZ_k), FAA cannot succeed as the time evolution is not that of an adiabatic evolution. We thus expect FAA to fail at least around and above δ t ∼π/2. In practice, using state-vector simulations up to L=22, we observe in the third panel of Figure <ref> that for n⪆ 0.8 the growth of T_*(L) with L is mild, and we always find the optimal solution with an adiabatic time T small or moderate. However for n⪅ 0.8 the time T_* blows up with L, and this increase is mainly due to outlier graphs for which FAA fails, i.e. require a very large T to find the solution by just random sampling (with our protocol where we try every integer value of T, we typically expect to find the optimal solution for T_*⪅2^L/N_S).  In the fourth panel, we then show the circuit depth 3nT_* as a function of δ t=1/n. We observe that the curve reaches a minimum between δ t=1 and δ t=1.3, indicating the optimal range of Trotter steps on which to run FAA. This optimal value is very far from δ t=0 required to implement the exact (non-Floquet) adiabatic evolution. 
        
        In Figure <ref> we then plot as a function of system size the runtime of FAA, that of the exact classical solver <cit.>, and that of the approximate classical solver  from the MQLib library <cit.>. They were both used for benchmarking the  problem in previous works <cit.>. In the left panel, we show the classical simulation of FAA with MPS which scales as D^3LT_*(L)^2. Although T_*(L) decreases with bond dimension D, due to the D^3 scaling of MPS simulations, we find that D=2 provides the best runtime. We see that FAA simulated with a MPS is expected to perform better than  around system size L=400.
        
        
        
        On a quantum computer.— We now describe the performance of running FAA on a quantum computer. We assume a runtime of 1ms per two-qubit gate, and possible parallelization of L/2 gates in the quantum circuit since gates that apply on disjoint edges can be performed simultaneously, in contrast with classical simulations. As a consequence the runtime of the quantum implementation of FAA only scales as T_*(L)^2, and the minimal adiabatic time T_*(L) corresponds to that of MPS with D=∞. In the right panel of Figure <ref>, we show  an estimation of this runtime for a single adiabatic time T=T_* (i.e., without doing the step by step increase in T), with T_*(L) obtained with classical MPS simulation with  D=64. For these system sizes L≤ 72, the runtime as a function of L is seen to be compatible with a linear behaviour. This linear behaviour is expected to eventually disappear at larger L, but it could in principle hold for a certain interesting and useful range of intermediate sizes. From the left panel, we see that system sizes L=2000 become completely out of reach of classical solvers, whether exact or approximate. Assuming the linear behaviour holds up to these sizes, and extrapolating our numerics for T_* with δ t=1/4 up to L∼ 10^3, we find T_*∼ 10^2, so around 12LT_*∼ 10^6 two-qubit gates. Taking into account a few trials at different values of T, this would take around one day runtime. 
         
         This favorable extrapolated runtime is only possible due to keeping finite Trotter steps in FAA, in which the circuit depth is only 𝒪(nT_*). In contrast, the implementation of quantum (non-Floquet) adiabatic algorithms require a circuit depth 𝒪(T_*^2 L/ϵ). Moreover we saw in the two rightmost panels of Figure <ref> that the adiabatic time required when δ t→ 0 is only slightly smaller than for e.g. δ=1/4. Even neglecting the factor 1/ϵ, this represents an improvement 𝒪(T_*L) in circuit depth and number of gates. For sizes L∼ 10^3 beyond what can be solved with classical solvers, this represents a saving of order ∼ 10^5 both in circuit depth and gate count. 
        
         Let us finally comment on the effect of hardware noise, which is the main limiting factor of current and near-term quantum processors. Any source of noise that can be described by a quantum channel can be seen as applying Kraus operators with some probability p after each gate in the circuit <cit.>.
        Then, in a circuit with N noisy gates, there will always be a fraction (1-p)^N of all the shots that are effectively noiseless. In general quantum computing applications, mitigating or correcting the noise requires to know in which shots an error occurred. However, in case of a classical optimization problem in NP, given a list of measurement outcomes in the Z basis, one can compute the energy and check whether it is lower than previous measurement outcomes, without knowing whether an error occurred or not. Thus, one can obtain an estimate of the minimal energy from low-fidelity simulations at the only cost of extra shots (albeit exponentially many in pN). Compared to applications that require a global fidelity of order ∼ 1 for noise to be mitigated, this entails a significant resource saving, as one can save a factor 10 on the gate error at the cost of doing ∼ 10^4 more shots. We note that this argument is not specific to FAA. In the case of the  problem on a 3-regular graphs, our estimate was that a circuit with around ∼ 10^6 two-qubit gates was necessary to compete with classical computers, whence a required gate error probability p∼ 10^-5. This would set the resources to ∼ 10^-5 gate error probability and ∼ 10^3 qubits for a quantum computer to compete with classical solvers at the specific task of finding the optimal cut in a 3-regular graph. Of course, these numbers rely on extrapolating trends observed numerically for system sizes L⪅ 100 that could break at larger L. However, they are encouraging and suggest a direction to explore further for industrial applications in the intermediate term. Before that, the classical verifiability of the algorithm presented here can be used as to benchmark quantum computers on application-oriented problems in large variety of circuit depths and number of qubits.
        
        
        We thank David Amaro and Frederic Sauvage for useful comments on the manuscript. We thank Fermioniq for their MPS simulator initially used in this project <cit.>. E.G. acknowledges support by the Bavarian Ministry of Economic Affairs, Regional Development and Energy (StMWi) under project Bench-QC (DIK0425/01).
        
        
        
        
        
        
        
        
        
        
        
        50
        fxundefined [1]
         ifx#1
        fnum [1]
          #1firstoftwo
         secondoftwo
         
        fx [1]
          #1firstoftwo
         secondoftwo
         
        
        
        
        
        
        noop [0]secondoftwo
        
        ref[1]@startlink#1@href
        href[1]#1@endlink
        anitize@url [0] `
        12 `$12 `&12 `#12 `1̂2 `_12 `%12
        startlink[1]
        endlink[0]
        
        rl [1]href #1
        
        
        
        
        
        
        
        
        
        
        
        
        @bib@innerbibempty
        
         [Farhi et al.(2000)Farhi, Goldstone, Gutmann, and Sipser]farhi2000quantum
          authorauthorE. Farhi, authorJ. Goldstone, authorS. Gutmann,  and authorM. Sipser,  10.48550/arXiv.quant-ph/0001106journaljournalarXiv preprint quant-ph/0001106  (year2000), 10.48550/arXiv.quant-ph/0001106NoStop
         [Farhi et al.(2014)Farhi, Goldstone, and Gutmann]farhi2014quantum
          authorauthorE. Farhi, authorJ. Goldstone,  and authorS. Gutmann,  10.48550/arXiv.1411.4028journaljournalarXiv preprint arXiv:1411.4028  (year2014), 10.48550/arXiv.1411.4028NoStop
         [Peruzzo et al.(2014)Peruzzo, McClean, Shadbolt, Yung, Zhou, Love, Aspuru-Guzik, and O’brien]peruzzo2014variational
          authorauthorA. Peruzzo, authorJ. McClean, authorP. Shadbolt, authorM.-H. Yung, authorX.-Q. Zhou, authorP. J. Love, authorA. Aspuru-Guzik,  and authorJ. L. O’brien,  10.1038/ncomms5213journaljournalNature communications volume5, pages4213 (year2014)NoStop
         [Blekos et al.(2024)Blekos, Brand, Ceschini, Chou, Li, Pandya, and Summer]blekos2024review
          authorauthorK. Blekos, authorD. Brand, authorA. Ceschini, authorC.-H. Chou, authorR.-H. Li, authorK. Pandya,  and authorA. Summer,  10.1016/j.physrep.2024.03.002journaljournalPhysics Reports volume1068, pages1 (year2024)NoStop
         [Leontica and Amaro(2024)]leontica2024exploring
          authorauthorS. Leontica and authorD. Amaro,  10.1103/PhysRevResearch.6.013071journaljournalPhysical Review Research volume6, pages013071 (year2024)NoStop
         [McClean et al.(2018)McClean, Boixo, Smelyanskiy, Babbush, and Neven]mcclean2018barren
          authorauthorJ. R. McClean, authorS. Boixo, authorV. N. Smelyanskiy, authorR. Babbush,  and authorH. Neven,  10.1038/s41467-018-07090-4journaljournalNature communications volume9, pages4812 (year2018)NoStop
         [Wang et al.(2021)Wang, Fontana, Cerezo, Sharma, Sone, Cincio, and Coles]wang2021noise
          authorauthorS. Wang, authorE. Fontana, authorM. Cerezo, authorK. Sharma, authorA. Sone, authorL. Cincio,  and authorP. J. Coles,  10.1038/s41467-021-27045-6journaljournalNature communications volume12, pages6961 (year2021)NoStop
         [Lykov et al.(2023)Lykov, Wurtz, Poole, Saffman, Noel, and Alexeev]lykov2023sampling
          authorauthorD. Lykov, authorJ. Wurtz, authorC. Poole, authorM. Saffman, authorT. Noel,  and authorY. Alexeev,  10.48550/arXiv.2206.03579journaljournalnpj Quantum Information volume9, pages73 (year2023)NoStop
         [Ho and Abanin(2016)]ho2016quasi
          authorauthorW. W. Ho and authorD. A. Abanin,  10.48550/arXiv.1611.05024journaljournalarXiv preprint arXiv:1611.05024  (year2016), 10.48550/arXiv.1611.05024NoStop
         [Lewis(1983)]lewis1983michael
          authorauthorH. R. Lewis, @noop journaljournalThe Journal of Symbolic Logic volume48, pages498 (year1983)NoStop
         [Håstad(2001)]haastad2001some
          authorauthorJ. Håstad,  10.1145/502090.502098journaljournalJournal of the ACM (JACM) volume48, pages798 (year2001)NoStop
         [Kügel(2010)]kugel2010improved
          authorauthorA. Kügel,  10.29007/38lmjournaljournalPos@ sat volume8, pages15 (year2010)NoStop
         [Goemans and Williamson(1995)]goemans1995improved
          authorauthorM. X. Goemans and authorD. P. Williamson,  10.1145/227683.227684journaljournalJournal of the ACM (JACM) volume42, pages1115 (year1995)NoStop
         [Gurobi Optimization, LLC(2023)]gurobi
          authorauthorGurobi Optimization, LLC, https://www.gurobi.comtitleGurobi Optimizer Reference Manual,  (year2023)NoStop
         [Dunning et al.(2018)Dunning, Gupta, and Silberholz]DunningEtAl2018
          authorauthorI. Dunning, authorS. Gupta,  and authorJ. Silberholz,  10.1287/ijoc.2017.0798journaljournalINFORMS Journal on Computing volume30 (year2018), 10.1287/ijoc.2017.0798NoStop
         [Halperin et al.(2004)Halperin, Livnat, and Zwick]halperin2004max
          authorauthorE. Halperin, authorD. Livnat,  and authorU. Zwick,  10.1016/j.jalgor.2004.06.001journaljournalJournal of Algorithms volume53, pages169 (year2004)NoStop
         [Berman and Karpinski(1999)]berman1999some
          authorauthorP. Berman and authorM. Karpinski, in @noop booktitleAutomata, Languages and Programming: 26th International Colloquium, ICALP’99 Prague, Czech Republic, July 11–15, 1999 Proceedings 26 (organizationSpringer, year1999) pp. pages200–209NoStop
         [Kochenberger et al.(2014)Kochenberger, Hao, Glover, Lewis, Lü, Wang, and Wang]kochenberger2014unconstrained
          authorauthorG. Kochenberger, authorJ.-K. Hao, authorF. Glover, authorM. Lewis, authorZ. Lü, authorH. Wang,  and authorY. Wang,  10.1007/s10878-014-9734-0journaljournalJournal of combinatorial optimization volume28, pages58 (year2014)NoStop
         [Schuch et al.(2008)Schuch, Wolf, Verstraete, and Cirac]schuch2008entropy
          authorauthorN. Schuch, authorM. M. Wolf, authorF. Verstraete,  and authorJ. I. Cirac,  10.1103/PhysRevLett.100.030504journaljournalPhysical review letters volume100, pages030504 (year2008)NoStop
         [Lloyd(1996)]lloyd1996universal
          authorauthorS. Lloyd,  10.1126/science.273.5278.1073journaljournalScience volume273, pages1073 (year1996)NoStop
         [Suzuki(1991)]suzuki1991general
          authorauthorM. Suzuki,  10.1063/1.529425journaljournalJournal of Mathematical Physics volume32, pages400 (year1991)NoStop
         [Childs et al.(2021)Childs, Su, Tran, Wiebe, and Zhu]childs2021theory
          authorauthorA. M. Childs, authorY. Su, authorM. C. Tran, authorN. Wiebe,  and authorS. Zhu,  10.1103/PhysRevX.11.011020journaljournalPhysical Review X volume11, pages011020 (year2021)NoStop
         [Kovalsky et al.(2023)Kovalsky, Calderon-Vargas, Grace, Magann, Larsen, Baczewski, and Sarovar]kovalsky2023self
          authorauthorL. K. Kovalsky, authorF. A. Calderon-Vargas, authorM. D. Grace, authorA. B. Magann, authorJ. B. Larsen, authorA. D. Baczewski,  and authorM. Sarovar,  10.1103/PhysRevLett.131.060602journaljournalPhysical Review Letters volume131, pages060602 (year2023)NoStop
         [Yi(2021)]yi2021success
          authorauthorC. Yi,  10.1103/PhysRevA.104.052603journaljournalPhysical Review A volume104, pages052603 (year2021)NoStop
         [Berry et al.(2015)Berry, Childs, Cleve, Kothari, and Somma]berry2015simulating
          authorauthorD. W. Berry, authorA. M. Childs, authorR. Cleve, authorR. Kothari,  and authorR. D. Somma,  10.1103/PhysRevLett.114.090502journaljournalPhysical review letters volume114, pages090502 (year2015)NoStop
         [Berry et al.(2020)Berry, Childs, Su, Wang, and Wiebe]berry2020time
          authorauthorD. W. Berry, authorA. M. Childs, authorY. Su, authorX. Wang,  and authorN. Wiebe,  10.22331/q-2020-04-20-254journaljournalQuantum volume4, pages254 (year2020)NoStop
         [Granet and Dreyer(2023)]granet2023continuous
          authorauthorE. Granet and authorH. Dreyer,  10.48550/arXiv.2308.03694journaljournalarXiv preprint arXiv:2308.03694  (year2023), 10.48550/arXiv.2308.03694NoStop
         [Farhi et al.(2001)Farhi, Goldstone, Gutmann, Lapan, Lundgren, and Preda]farhi2001quantum
          authorauthorE. Farhi, authorJ. Goldstone, authorS. Gutmann, authorJ. Lapan, authorA. Lundgren,  and authorD. Preda,  10.1126/science.1057726journaljournalScience volume292, pages472 (year2001)NoStop
         [Crosson et al.(2014)Crosson, Farhi, Lin, Lin, and Shor]crosson2014different
          authorauthorE. Crosson, authorE. Farhi, authorC. Y.-Y. Lin, authorH.-H. Lin,  and authorP. Shor,  10.48550/arXiv.1401.7320journaljournalarXiv preprint arXiv:1401.7320  (year2014), 10.48550/arXiv.1401.7320NoStop
         [Hamerly et al.(2019)Hamerly, Inagaki, McMahon, Venturelli, Marandi, Onodera, Ng, Langrock, Inaba, Honjoet al.]hamerly2019experimental
          authorauthorR. Hamerly, authorT. Inagaki, authorP. L. McMahon, authorD. Venturelli, authorA. Marandi, authorT. Onodera, authorE. Ng, authorC. Langrock, authorK. Inaba, authorT. Honjo,  et al.,  10.1126/sciadv.aau0823journaljournalScience advances volume5, pageseaau0823 (year2019)NoStop
         [Zhou et al.(2020)Zhou, Wang, Choi, Pichler, and Lukin]zhou2020quantum
          authorauthorL. Zhou, authorS.-T. Wang, authorS. Choi, authorH. Pichler,  and authorM. D. Lukin,  10.1103/PhysRevX.10.021067journaljournalPhysical Review X volume10, pages021067 (year2020)NoStop
         [Ebadi et al.(2022)Ebadi, Keesling, Cain, Wang, Levine, Bluvstein, Semeghini, Omran, Liu, Samajdaret al.]ebadi2022quantum
          authorauthorS. Ebadi, authorA. Keesling, authorM. Cain, authorT. T. Wang, authorH. Levine, authorD. Bluvstein, authorG. Semeghini, authorA. Omran, authorJ.-G. Liu, authorR. Samajdar,  et al.,  10.1126/science.abo6587journaljournalScience volume376, pages1209 (year2022)NoStop
         [Barends et al.(2016)Barends, Shabani, Lamata, Kelly, Mezzacapo, Heras, Babbush, Fowler, Campbell, Chenet al.]barends2016digitized
          authorauthorR. Barends, authorA. Shabani, authorL. Lamata, authorJ. Kelly, authorA. Mezzacapo, authorU. L. Heras, authorR. Babbush, authorA. G. Fowler, authorB. Campbell, authorY. Chen,  et al.,  10.1038/nature17658journaljournalNature volume534, pages222 (year2016)NoStop
         [Mehta et al.(2022)Mehta, Jin, De Raedt, and Michielsen]mehta2022quantum
          authorauthorV. Mehta, authorF. Jin, authorH. De Raedt,  and authorK. Michielsen,  10.1103/PhysRevA.105.062406journaljournalPhysical Review A volume105, pages062406 (year2022)NoStop
         [Vert et al.(2021)Vert, Sirdey, and Louise]vert2021benchmarking
          authorauthorD. Vert, authorR. Sirdey,  and authorS. Louise,  10.1007/s42979-021-00483-1journaljournalSN Computer Science volume2, pages1 (year2021)NoStop
         [Farhi et al.(2012)Farhi, Gosset, Hen, Sandvik, Shor, Young, and Zamponi]farhi2012performance
          authorauthorE. Farhi, authorD. Gosset, authorI. Hen, authorA. Sandvik, authorP. Shor, authorA. Young,  and authorF. Zamponi,  10.1103/PhysRevA.86.052334journaljournalPhysical Review A volume86, pages052334 (year2012)NoStop
         [Ikeda et al.(2019)Ikeda, Nakamura, and Humble]ikeda2019application
          authorauthorK. Ikeda, authorY. Nakamura,  and authorT. S. Humble,  10.1038/s41598-019-49172-3journaljournalScientific reports volume9, pages12837 (year2019)NoStop
         [Denchev et al.(2016)Denchev, Boixo, Isakov, Ding, Babbush, Smelyanskiy, Martinis, and Neven]denchev2016computational
          authorauthorV. S. Denchev, authorS. Boixo, authorS. V. Isakov, authorN. Ding, authorR. Babbush, authorV. Smelyanskiy, authorJ. Martinis,  and authorH. Neven,  10.1103/PhysRevX.6.031015journaljournalPhysical Review X volume6, pages031015 (year2016)NoStop
         [Otterbach et al.(2017)Otterbach, Manenti, Alidoust, Bestwick, Block, Bloom, Caldwell, Didier, Fried, Honget al.]otterbach2017unsupervised
          authorauthorJ. S. Otterbach, authorR. Manenti, authorN. Alidoust, authorA. Bestwick, authorM. Block, authorB. Bloom, authorS. Caldwell, authorN. Didier, authorE. S. Fried, authorS. Hong,  et al.,  10.48550/arXiv.1712.05771journaljournalarXiv preprint arXiv:1712.05771  (year2017), 10.48550/arXiv.1712.05771NoStop
         [Albash and Lidar(2018)]albash2018demonstration
          authorauthorT. Albash and authorD. A. Lidar,  10.1103/PhysRevX.8.031016journaljournalPhysical Review X volume8, pages031016 (year2018)NoStop
         [Mohseni et al.(2022)Mohseni, McMahon, and Byrnes]mohseni2022ising
          authorauthorN. Mohseni, authorP. L. McMahon,  and authorT. Byrnes,  10.1038/s42254-022-00440-8journaljournalNature Reviews Physics volume4, pages363 (year2022)NoStop
         [Santra et al.(2014)Santra, Quiroz, Ver Steeg, and Lidar]santra2014max
          authorauthorS. Santra, authorG. Quiroz, authorG. Ver Steeg,  and authorD. A. Lidar,  10.1088/1367-2630/16/4/045006journaljournalNew Journal of Physics volume16, pages045006 (year2014)NoStop
         [King et al.(2022)King, Suzuki, Raymond, Zucca, Lanting, Altomare, Berkley, Ejtemaee, Hoskinson, Huanget al.]king2022coherent
          authorauthorA. D. King, authorS. Suzuki, authorJ. Raymond, authorA. Zucca, authorT. Lanting, authorF. Altomare, authorA. J. Berkley, authorS. Ejtemaee, authorE. Hoskinson, authorS. Huang,  et al.,  10.1038/s41567-022-01741-6journaljournalNature Physics volume18, pages1324 (year2022)NoStop
         [Amaro et al.(2022)Amaro, Modica, Rosenkranz, Fiorentini, Benedetti, and Lubasch]amaro2022filtering
          authorauthorD. Amaro, authorC. Modica, authorM. Rosenkranz, authorM. Fiorentini, authorM. Benedetti,  and authorM. Lubasch,  10.1088/2058-9565/ac3e54journaljournalQuantum Science and Technology volume7, pages015021 (year2022)NoStop
         [Keever and Lubasch(2023)]keever2023towards
          authorauthorC. M. Keever and authorM. Lubasch,  10.48550/arXiv.2311.05544journaljournalarXiv preprint arXiv:2311.05544  (year2023), 10.48550/arXiv.2311.05544NoStop
         [Suzuki(1990)]suzuki1990fractal
          authorauthorM. Suzuki,  10.1016/0375-9601(90)90962-NjournaljournalPhysics Letters A volume146, pages319 (year1990)NoStop
         [Qiskit contributors(2023)]Qiskit
          authorauthorQiskit contributors,  10.5281/zenodo.2573505titleQiskit: An open-source framework for quantum computing,  (year2023)NoStop
         [Guerreschi and Matsuura(2019)]guerreschi2019qaoa
          authorauthorG. G. Guerreschi and authorA. Y. Matsuura,  10.1038/s41598-019-43176-9journaljournalScientific reports volume9, pages6903 (year2019)NoStop
         [Nielsen and Chuang(2010)]nielsen2010quantum
          authorauthorM. A. Nielsen and authorI. L. Chuang, @noop titleQuantum computation and quantum information (publisherCambridge university press, year2010)NoStop
         [Fermioniq B.V.(2023)]fermioniq
          authorauthorFermioniq B.V., https://www.fermioniq.com/titleFermioniq,  (year2023)NoStop
