On Circuit Depth Scaling For Quantum Approximate Optimization

Abstract

Variational quantum algorithms are the centerpiece of modern quantum programming. These algorithms involve training parameterized quantum circuits using a classical co-processor, an approach adapted partly from classical machine learning. An important subclass of these algorithms, designed for combinatorial optimization on currrent quantum hardware, is the quantum approximate optimization algorithm (QAOA). It is known that problem density - a problem constraint to variable ratio - induces under-parametrization in fixed depth QAOA. Density dependent performance has been reported in the literature, yet the circuit depth required to achieve fixed performance (henceforth called critical depth) remained unknown. Here, we propose a predictive model, based on a logistic saturation conjecture for critical depth scaling with respect to density. Focusing on random instances of MAX-2-SAT, we test our predictive model against simulated data with up to 15 qubits. We report the average critical depth, required to attain a success probability of 0.7, saturates at a value of 10 for densities beyond 4. We observe the predictive model to describe the simulated data within a $3\sigma$ confidence interval. Furthermore, based on the model, a linear trend for the critical depth with respect problem size is recovered for the range of 5 to 15 qubits.

REVTeX, 6+2 pages, 4 figures

References in corpus (5)

• Layerwise learning for quantum neural networks
• Non-perturbative k-body to two-body commuting conversion Hamiltonians and embedding problem instances into Ising spins
• Parameter Concentration in Quantum Approximate Optimization
• Training Saturation in Layerwise Quantum Approximate Optimisation
• Reachability Deficits in Quantum Approximate Optimization of Graph Problems

Cited by in corpus (11)

• Evidence of Scaling Advantage for the Quantum Approximate Optimization Algorithm on a Classically Intractable Problem
• Simulations of Frustrated Ising Hamiltonians with Quantum Approximate Optimization
• Robustness of Variational Quantum Algorithms against stochastic parameter perturbation
• Progress towards analytically optimal angles in quantum approximate optimisation
• Characterization of variational quantum algorithms using free fermions
• Mitigating Quantum Gate Errors for Variational Eigensolvers Using Hardware-Inspired Zero-Noise Extrapolation
• Compressed sensing enhanced by quantum approximate optimization algorithm
• Cheaper and more noise-resilient quantum state preparation using eigenvector continuation
• Efficient Large-Scale Quantum Optimization via Counterdiabatic Ansatz
• Lower bounds on the number of rounds of the quantum approximate optimization algorithm required for guaranteed approximation ratios
• Role of overparametrization in quantum approximate optimization