Continuous-time quantum walks for MAX-CUT are hot
arXiv:2306.10365 · doi:10.22331/q-2024-02-13-1254
Abstract
By exploiting the link between time-independent Hamiltonians and thermalisation, heuristic predictions on the performance of continuous-time quantum walks for MAX-CUT are made. The resulting predictions depend on the number of triangles in the underlying MAX-CUT graph. We extend these results to the time-dependent setting with multi-stage quantum walks and Floquet systems. The approach followed here provides a novel way of understanding the role of unitary dynamics in tackling combinatorial optimisation problems with continuous-time quantum algorithms.
arXiv comment34 pages, 30 figures
References in corpus (53)
- Chaos and Quantum Thermalization
- Thermalization and its mechanism for generic isolated quantum systems
- Many body localization and thermalization in quantum statistical mechanics
- QuTiP 2: A Python framework for the dynamics of open quantum systems
- From Quantum Chaos and Eigenstate Thermalization to Statistical Mechanics and Thermodynamics
- QuTiP: An open-source Python framework for the dynamics of open quantum systems
- Adiabatic Quantum Computing
- Quantum Computation and Decision Trees
- Quantum thermalization through entanglement in an isolated many-body system
- Probing the relaxation towards equilibrium in an isolated strongly correlated 1D Bose gas
- Universal computation by quantum walk
- Exponential algorithmic speedup by quantum walk
- Spatial search by quantum walk
- Area laws in quantum systems: mutual information and correlations
- Quantum Approximate Optimization Algorithm: Performance, Mechanism, and Implementation on Near-Term Devices
- Quench dynamics and relaxation in isolated integrable quantum spin chains
- Eigenstate Thermalization Hypothesis
- Equilibrium states of generic quantum systems subject to periodic driving
- Long-time behavior of periodically driven isolated interacting lattice systems
- Breakdown of thermalization in finite one-dimensional systems
- Perspectives of quantum annealing: Methods and implementations
- Localization protected quantum order
- Testing whether all eigenstates obey the Eigenstate Thermalization Hypothesis
- Onset of quantum chaos in one-dimensional bosonic and fermionic systems and its relation to thermalization
- Effect of Rare Fluctuations on the Thermalization of Isolated Quantum Systems
- Random Walks: A Review of Algorithms and Applications
- Does a single eigenstate encode the full Hamiltonian?
- Many-body energy localization transition in periodically driven systems
- Thermalization near integrability in a dipolar quantum Newton's cradle
- Eigenstate thermalization within isolated spin-chain systems
- Critical thermalization of a disordered dipolar spin system in diamond
- Pushing the limits of the eigenstate thermalization hypothesis towards mesoscopic quantum systems
- Entropy of isolated quantum systems after a quench
- The microscopic origin of thermodynamic entropy in isolated systems
- Eigenstate thermalization in the two-dimensional transverse field Ising model: II. Off-diagonal matrix elements of observables
- Eigenstate Thermalization in a Locally Perturbed Integrable System
- Eigenstate thermalization and quantum chaos in the Holstein polaron model
- Time-resolved observation of thermalization in an isolated quantum system
- The performance of the quantum adiabatic algorithm on random instances of two optimization problems on regular hypergraphs
- Thermodynamic entropy of a many body energy eigenstate
- Numerical Large Deviation Analysis of Eigenstate Thermalization Hypothesis
- Relevance of the eigenstate thermalization hypothesis for thermal relaxation
- Centrality measure based on continuous-time quantum walks and experimental realization
- Eigenstate Thermalization in Systems with Spontaneously Broken Symmetry
- Finding spin-glass ground states using quantum walks
- An energetic perspective on rapid quenches in quantum annealing
- Geometric characteristics of quantum evolution: curvature and torsion
- Eigenstate thermalization hypothesis and eigenstate-to-eigenstate fluctuations
- Equilibration times in closed quantum many-body systems
- Controlled quantum search on structured databases
- Comparing the hardness of MAX 2-SAT problem instances for quantum and classical algorithms
- Geometric properties of evolutionary graph states and their detection on a quantum computer
- Properties of thermal quantum states: locality of temperature, decay of correlations, and more
Cited by in corpus (7)
- Quantum algorithms for scientific computing
- Guided quantum walk
- Grover Speedup from Many Forms of the Zeno Effect
- Continuous-time quantum optimisation without the adiabatic principle
- Zeno-effect Computation: Opportunities and Challenges
- Improving success probability in the LHZ parity embedding by computing with quantum walks
- Quantum annealing and condensed matter physics