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.
34 pages, 30 figures
References in corpus (16)
- 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
- 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
- Equilibrium states of generic quantum systems subject to periodic driving
- Breakdown of thermalization in finite one-dimensional systems
- Testing whether all eigenstates obey the Eigenstate Thermalization Hypothesis
- Random Walks: A Review of Algorithms and Applications
- Eigenstate thermalization within isolated spin-chain systems
- Eigenstate thermalization and quantum chaos in the Holstein polaron model
- The performance of the quantum adiabatic algorithm on random instances of two optimization problems on regular hypergraphs
- Relevance of the eigenstate thermalization hypothesis for thermal relaxation
- Centrality measure based on continuous-time quantum walks and experimental realization
Cited by in corpus (6)
- Quantum algorithms for scientific computing
- Guided quantum walk
- Continuous-time quantum optimisation without the adiabatic principle
- Zeno-effect Computation: Opportunities and Challenges
- Quantum annealing and condensed matter physics
- Improving success probability in the LHZ parity embedding by computing with quantum walks