Connection between single-layer Quantum Approximate Optimization Algorithm interferometry and thermal distributions sampling

Abstract

The Quantum Approximate Optimization Algorithm (QAOA) is an algorithm originally proposed to find approximate solutions to Combinatorial Optimization problems on quantum computers. However, the algorithm has also attracted interest for sampling purposes since it was theoretically demonstrated under reasonable complexity assumptions that one layer of the algorithm already engineers a probability distribution beyond what can be simulated by classical computers. In this regard, a recent study has shown as well that, in universal Ising models, this global probability distribution resembles pure but thermal-like distributions at a temperature that depends on internal correlations of the spin model. In this work, through an interferometric interpretation of the algorithm, we extend the theoretical derivation of the amplitudes of the eigenstates, and the Boltzmann distributions generated by single-layer QAOA. We also review the implications that this behavior has from both a practical and fundamental perspective.

arXiv comment20 pages, 6 figures

References in corpus (26)

• Scikit-learn: Machine Learning in Python
• Quantum Computing in the NISQ era and beyond
• Supplementary information for "Quantum supremacy using a programmable superconducting processor"
• Variational Quantum Algorithms
• Ising formulations of many NP problems
• A Quantum Adiabatic Evolution Algorithm Applied to Random Instances of an NP-Complete Problem
• A Quantum Approximate Optimization Algorithm
• Noisy intermediate-scale quantum (NISQ) algorithms
• Adiabatic Quantum Computing
• Strong quantum computational advantage using a superconducting quantum processor
• Quantum optimization using variational algorithms on near-term quantum devices
• Quantum Approximate Optimization of Non-Planar Graph Problems on a Planar Superconducting Processor
• Phase-Programmable Gaussian Boson Sampling Using Stimulated Squeezed Light
• A Review on Quantum Approximate Optimization Algorithm and its Variants
• Classical simulation of commuting quantum computations implies collapse of the polynomial hierarchy
• Average-case complexity versus approximate simulation of commuting quantum computations
• The Quantum Approximate Optimization Algorithm and the Sherrington-Kirkpatrick Model at Infinite Size
• Quantum Sampling Problems, BosonSampling and Quantum Supremacy
• Performance of hybrid quantum/classical variational heuristics for combinatorial optimization
• Quantum-enhanced Markov chain Monte Carlo
• 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
• Quantum Sampling Algorithms for Near-Term Devices
• Quantum Approximate Optimization Algorithm pseudo-Boltzmann states
• The complexity of simulating constant-depth BosonSampling

Cited by in corpus (3)

• Universal resources for quantum approximate optimization algorithm and quantum annealing
• Out of the Loop: Structural Approximation of Optimisation Landscapes and non-Iterative Quantum Optimisation
• Pilot-Wave Simulator: Exact Classical Sampling from Ideal and Noisy Quantum Circuits up to Hundreds of Qubits