Beyond Quantum Annealing: Optimal control solutions to MaxCut problems

Abstract

Quantum Annealing (QA) relies on mixing two Hamiltonian terms, a simple driver and a complex problem Hamiltonian, in a linear combination. The time-dependent schedule for this mixing is often taken to be linear in time: improving on this linear choice is known to be essential and has proven to be difficult. Here, we present different techniques for improving on the linear-schedule QA along two directions, conceptually distinct but leading to similar outcomes: 1) the first approach consists of constructing a Trotter-digitized QA (dQA) with schedules parameterized in terms of Fourier modes or Chebyshev polynomials, inspired by the Chopped Random Basis algorithm (CRAB) for optimal control in continuous time; 2) the second approach is technically a Quantum Approximate Optimization Algorithm (QAOA), whose solutions are found iteratively using linear interpolation or expansion in Fourier modes. Both approaches emphasize finding smooth optimal schedule parameters, ultimately leading to hybrid quantum-classical variational algorithms of the alternating Hamiltonian Ansatz type. We apply these techniques to MaxCut problems on weighted 3-regular graphs with N = 14 sites, focusing on hard instances that exhibit a small spectral gap, for which a standard linear-schedule QA performs poorly. We characterize the physics behind the optimal protocols for both the dQA and QAOA approaches, discovering shortcuts to adiabaticity-like dynamics. Furthermore, we study the transferability of such smooth solutions among hard instances of MaxCut at different circuit depths. Finally, we show that the smoothness pattern of these protocols obtained in a digital setting enables us to adapt them to continuous-time evolution, contrarily to generic non-smooth solutions. This procedure results in an optimized quantum annealing schedule that is implementable on analog devices.

18 pages, 13 figures

References in corpus (53)

• Quantum Computing in the NISQ era and beyond
• Quantum Mechanics helps in searching for a needle in a haystack
• Variational Quantum Algorithms
• Ising formulations of many NP problems
• Barren plateaus in quantum neural network training landscapes
• Noisy intermediate-scale quantum (NISQ) algorithms
• Adiabatic Quantum Computing
• The Variational Quantum Eigensolver: a review of methods and best practices
• Shortcuts to adiabaticity: concepts, methods, and applications
• From the Quantum Approximate Optimization Algorithm to a Quantum Alternating Operator Ansatz
• Theory of Quantum Annealing of an Ising Spin Glass
• Quantum Approximate Optimization Algorithm: Performance, Mechanism, and Implementation on Near-Term Devices
• Grover's quantum searching algorithm is optimal
• Quantum Search by Local Adiabatic Evolution
• Defining and detecting quantum speedup
• Digitized adiabatic quantum computing with a superconducting circuit
• Training variational quantum algorithms is NP-hard
• Optimal control technique for Many Body Quantum Systems dynamics
• Chopped random-basis quantum optimization
• An initialization strategy for addressing barren plateaus in parametrized quantum circuits
• Layerwise learning for quantum neural networks
• QAOA for Max-Cut requires hundreds of qubits for quantum speed-up
• Geometry and non-adiabatic response in quantum and classical systems
• Second order gradient ascent pulse engineering
• Undecidability of the Spectral Gap (short version)
• Quantum Approximate Optimization of the Long-Range Ising Model with a Trapped-Ion Quantum Simulator
• The Quantum Approximate Optimization Algorithm and the Sherrington-Kirkpatrick Model at Infinite Size
• Quantum annealing initialization of the quantum approximate optimization algorithm
• Adiabatic quantum dynamics of a random Ising chain across its quantum critical point
• Theory of quantum system certification: a tutorial
• Dressing the chopped-random-basis optimization: a bandwidth-limited access to the trap-free landscape
• The Quantum Adiabatic Algorithm applied to random optimization problems: the quantum spin glass perspective
• Digitized-counterdiabatic quantum approximate optimization algorithm
• One decade of quantum optimal control in the chopped random basis
• Counterdiabaticity and the quantum approximate optimization algorithm
• Counterdiabatic Optimised Local Driving
• Many-body transverse interactions in the quantum annealing of the p-spin ferromagnet
• Reinforcement Learning assisted Quantum Optimization
• Avoiding barren plateaus via transferability of smooth solutions in Hamiltonian Variational Ansatz
• Synergy Between Quantum Circuits and Tensor Networks: Short-cutting the Race to Practical Quantum Advantage
• Reverse quantum annealing of the $p$-spin model with relaxation
• Improving quantum annealing of the ferromagnetic $p$-spin model through pausing
• Parameter Setting in Quantum Approximate Optimization of Weighted Problems
• Two-dimensional ${\mathbb{Z}}_2$ lattice gauge theory on a near-term quantum simulator: variational quantum optimization, confinement, and topological order
• Variational optimization of the quantum annealing schedule for the Lechner-Hauke-Zoller scheme
• Designing Quantum Annealing Schedules using Bayesian Optimization
• Variationally Scheduled Quantum Simulation
• Robust Quantum Control for Adiabatic Quantum Computation
• Optimal working point in digitized quantum annealing
• Quantum Annealing for Neural Network optimization problems: a new approach via Tensor Network simulations
• Diabatic Quantum Annealing for the Frustrated Ring Model
• Mitigated barren plateaus in the time-nonlocal optimization of analog quantum-algorithm protocols
• Noise amplification at spin-glass bottlenecks of quantum annealing: a solvable model

Cited by in corpus (2)

• Barren Plateaus in Variational Quantum Computing
• A Quantum Annealing Protocol to Solve the Nuclear Shell Model