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.

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

References in corpus (4)

• Variational Quantum Algorithms
• A Quantum Approximate Optimization Algorithm
• Filtering variational quantum algorithms for combinatorial optimization
• 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 QAOA 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