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

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 $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.

arXiv comment6 pages

References in corpus (33)

• A variational eigenvalue solver on a quantum processor
• Barren plateaus in quantum neural network training landscapes
• A Quantum Adiabatic Evolution Algorithm Applied to Random Instances of an NP-Complete Problem
• A Quantum Approximate Optimization Algorithm
• Simulating Hamiltonian dynamics with a truncated Taylor series
• Quantum Approximate Optimization Algorithm: Performance, Mechanism, and Implementation on Near-Term Devices
• Quantum Computation by Adiabatic Evolution
• A Theory of Trotter Error
• Digitized adiabatic quantum computing with a superconducting circuit
• Quantum Optimization of Maximum Independent Set using Rydberg Atom Arrays
• Entropy scaling and simulability by Matrix Product States
• A Review on Quantum Approximate Optimization Algorithm and its Variants
• QAOA for Max-Cut requires hundreds of qubits for quantum speed-up
• Experimental investigation of performance differences between Coherent Ising Machines and a quantum annealer
• What is the Computational Value of Finite Range Tunneling?
• Unsupervised Machine Learning on a Hybrid Quantum Computer
• Coherent quantum annealing in a programmable 2000-qubit Ising chain
• Demonstration of a scaling advantage for a quantum annealer over simulated annealing
• Quantum annealing initialization of the quantum approximate optimization algorithm
• Application of Quantum Annealing to Nurse Scheduling Problem
• Beyond-classical computation in quantum simulation
• The performance of the quantum adiabatic algorithm on random instances of two optimization problems on regular hypergraphs
• Time-dependent Hamiltonian simulation with $L^1$-norm scaling
• Towards adiabatic quantum computing using compressed quantum circuits
• Different Strategies for Optimization Using the Quantum Adiabatic Algorithm
• MAX 2-SAT with up to 108 qubits
• Self-healing of Trotter error in digital adiabatic state preparation
• Continuous Hamiltonian dynamics on digital quantum computers without discretization error
• Success of digital adiabatic simulation with large Trotter step
• Quantum annealing for hard 2-SAT problems : Distribution and scaling of minimum energy gap and success probability
• Exploring the neighborhood of 1-layer QAOA with Instantaneous Quantum Polynomial circuits
• Genuine Multipartite Entanglement in Quantum Optimization
• How Much Entanglement Do Quantum Optimization Algorithms Require?

Cited by in corpus (1)

• AppQSim: Application-oriented benchmarks for Hamiltonian simulation on a quantum computer