Quantum Annealing: a journey through Digitalization, Control, and hybrid Quantum Variational schemes

Abstract

We establish and discuss a number of connections between a digitized version of Quantum Annealing (QA) with the Quantum Approximate Optimization Algorithm (QAOA) introduced by Farhi et al. (arXiv:1411.4028) as an alternative hybrid quantum-classical variational scheme for quantum-state preparation and optimization. We introduce a technique that allows to prove, for instance, a rigorous bound concerning the performance of QAOA for MaxCut on a $2$-regular graph, equivalent to an unfrustrated antiferromagnetic Ising chain. The bound shows that the optimal variational error of a depth-$\mathrm{P}$ quantum circuit has to satisfy ${\epsilon }_{\mathrm{P}}^{\mathrm{res}}\ge (2\mathrm{P}+2{)}^{-1}$. In a separate work (Mbeng et al., arXiv:1911.12259) we have explicitly shown, exploiting a Jordan-Wigner transformation, that among the $2^{\mathrm{P}}$ degenerate variational minima which can be found for this problem, all strictly satisfying the equality ${\epsilon }_{\mathrm{P}}^{\mathrm{res}}=(2\mathrm{P}+2{)}^{-1}$, one can construct a special {\em regular} optimal solution, which is computationally optimal and does not require any prior knowledge about the spectral gap. We explicitly demonstrate here that such a schedule is adiabatic, in a digitized sense, and can therefore be interpreted as an optimized digitized-QA protocol. We also discuss and compare our bound on the residual energy to well-known results on the Kibble-Zurek mechanism behind a continuous-time QA. These findings help elucidating the intimate relation between digitized-QA, QAOA, and optimal Quantum Control.

Cited by in corpus (23)

• A Review on Quantum Approximate Optimization Algorithm and its Variants
• Obstacles to State Preparation and Variational Optimization from Symmetry Protection
• Warm-starting quantum optimization
• Quantum Approximate Optimization of the Long-Range Ising Model with a Trapped-Ion Quantum Simulator
• Optimal Protocols in Quantum Annealing and QAOA Problems
• Counterdiabaticity and the quantum approximate optimization algorithm
• Layer VQE: A Variational Approach for Combinatorial Optimization on Noisy Quantum Computers
• Classical symmetries and the Quantum Approximate Optimization Algorithm
• Noise-Resilient Variational Hybrid Quantum-Classical Optimization
• Beating classical heuristics for the binary paint shop problem with the quantum approximate optimization algorithm
• Local classical MAX-CUT algorithm outperforms $p=2$ QAOA on high-girth regular graphs
• Evaluation of QAOA based on the approximation ratio of individual samples
• Optimal Control for Closed and Open System Quantum Optimization
• Optimal working point in digitized quantum annealing
• Discretized quantum adiabatic process for free fermions and comparison with the imaginary-time evolution
• Quantum Annealing for Neural Network optimization problems: a new approach via Tensor Network simulations
• Binary Control Pulse Optimization for Quantum Systems
• Characterization of variational quantum algorithms using free fermions
• Forbidden subspaces for level-1 QAOA and IQP circuits
• A quantum algorithm to count weighted ground states of classical spin Hamiltonians
• Switching Time Optimization for Binary Quantum Optimal Control
• Reducing measurement costs by recycling the Hessian in adaptive variational quantum algorithms
• The deep learning and statistical physics applications to the problems of combinatorial optimization