Two-Stage Estimation and Variance Modeling for Latency-Constrained Variational Quantum Algorithms

Understand

The Quantum Approximate Optimization Algorithm (QAOA) has enjoyed increasing attention in noisy intermediate-scale quantum computing due to its application to combinatorial optimization problems.

• Because combinatorial optimization problems are NP-hard, QAOA could serve as a potential demonstration of quantum advantage in the future.
• As a hybrid quantum-classical algorithm, the classical component of QAOA resembles a simulation optimization problem, in which the simulation outcomes are attainable only through the quantum computer.
• The simulation that derives from QAOA exhibits two unique features that can have a substantial impact on the optimization process: (i) the variance of the stochastic objective values typically decreases in proportion to the optimality gap, and (ii) querying samples from a quantum computer introduces an additional latency overhead.