Quantum Approximate Optimization Algorithm pseudo-Boltzmann states

Abstract

In this letter, we provide analytical and numerical evidence that the single-layer Quantum Approximate Optimization Algorithm (QAOA) on universal Ising spin models produces thermal-like states. We find that these pseudo-Boltzmann states can not be efficiently simulated on classical computers according to the general state-of-the-art condition that ensures rapid mixing for Ising models. Moreover, we observe that the temperature depends on a hidden universal correlation between the energy of a state and the covariance of other energy levels and the Hamming distances of the state to those energies.

arXiv comment6 pages, 5 figures + Supplementary material (7 pages, 6 figures). v3: close to the published version

References in corpus (13)

• Variational Quantum Algorithms
• From Quantum Chaos and Eigenstate Thermalization to Statistical Mechanics and Thermodynamics
• A Quantum Approximate Optimization Algorithm
• Quantum Approximate Optimization of Non-Planar Graph Problems on a Planar Superconducting Processor
• Average-case complexity versus approximate simulation of commuting quantum computations
• Obstacles to State Preparation and Variational Optimization from Symmetry Protection
• The Quantum Approximate Optimization Algorithm and the Sherrington-Kirkpatrick Model at Infinite Size
• Reachability Deficits in Quantum Approximate Optimization
• Performance of hybrid quantum/classical variational heuristics for combinatorial optimization
• Filtering variational quantum algorithms for combinatorial optimization
• A quantum algorithm to train neural networks using low-depth circuits
• Using models to improve optimizers for variational quantum algorithms
• Expectation Values from the Single-Layer Quantum Approximate Optimization Algorithm on Ising Problems

Cited by in corpus (15)

• Does provable absence of barren plateaus imply classical simulability?
• Multiobjective variational quantum optimization for constrained problems: an application to Cash Management
• A Parameter Setting Heuristic for the Quantum Alternating Operator Ansatz
• Symmetry-informed transferability of optimal parameters in the Quantum Approximate Optimization Algorithm
• Low-depth Clifford circuits approximately solve MaxCut
• Exploring the neighborhood of 1-layer QAOA with Instantaneous Quantum Polynomial circuits
• Connection between single-layer Quantum Approximate Optimization Algorithm interferometry and thermal distributions sampling
• LX-mixers for QAOA: Optimal mixers restricted to subspaces and the stabilizer formalism
• Universal resources for quantum approximate optimization algorithm and quantum annealing
• Effective temperature in approximate quantum many-body states
• Constraint-Aware Quantum Optimization via Hamming Weight Operators
• Neural-network-assisted Monte Carlo sampling trained by Quantum Approximate Optimization Algorithm
• Quantum approximate optimization of finite-state bosonic systems
• Pilot-Wave Simulator: Exact Classical Sampling from Ideal and Noisy Quantum Circuits up to Hundreds of Qubits
• Hidden local adiabatic ramp in the modulated time evolution and the quantum approximate optimization algorithm