Optimizing QAOA: Success Probability and Runtime Dependence on Circuit Depth

Abstract

The quantum approximate optimization algorithm~(QAOA) first proposed by Farhi et al. promises near-term applications based on its simplicity, universality, and provable optimality. A depth-p QAOA consists of p interleaved unitary transformations induced by two mutually non-commuting Hamiltonians. A long-standing question concerning the performance of QAOA is the dependence of its success probability as a function of circuit depth p. We make initial progress by analyzing the success probability of QAOA for realizing state transfer in a one-dimensional qubit chain using two-qubit XY Hamiltonians and single-qubit Hamiltonians. We provide analytic state transfer success probability dependencies on p in both low and large p limits by leveraging the unique spectral property of the XY Hamiltonian. We support our proof under a given QAOA ansatz with numerical optimizations of QAOA for up to \(N\)=20 qubits. We show that the optimized QAOA can achieve the well-known quadratic speedup, Grover speedup, over the classical alternatives. Treating QAOA optimization as a quantum control problem, we also provide numerical evidence of how the circuit depth determines the controllability of the QAOA ansatz.

References in corpus (24)

• The Quantum Internet
• Quantum state transfer and entanglement distribution among distant nodes in a quantum network
• A Quantum Adiabatic Evolution Algorithm Applied to Random Instances of an NP-Complete Problem
• A Quantum Approximate Optimization Algorithm
• Quantum Communication Through an Unmodulated Spin Chain
• Non-local propagation of correlations in long-range interacting quantum systems
• Perfect Transfer of Arbitrary States in Quantum Spin Networks
• Quantum Optimization of Maximum Independent Set using Rydberg Atom Arrays
• Quantum Approximate Optimization Algorithm for MaxCut: A Fermionic View
• Robust Quantum State Transfer in Random Unpolarized Spin Chains
• Quantum Supremacy through the Quantum Approximate Optimization Algorithm
• Perfect quantum state transfer in a superconducting qubit chain with parametrically tunable couplings
• Near-optimal quantum circuit for Grover's unstructured search using a transverse field
• Bounds on Information Propagation in Disordered Quantum Spin Chains
• Efficient variational simulation of non-trivial quantum states
• Digital Quantum Simulation of Spin Systems in Superconducting Circuits
• Quantum approximate optimization is computationally universal
• Accuracy vs run time in adiabatic quantum search
• Singularities of Quantum Control Landscapes
• For Fixed Control Parameters the Quantum Approximate Optimization Algorithm's Objective Function Value Concentrates for Typical Instances
• Adiabatic Quantum Transport in a Spin Chain with a Moving Potential
• The role of controllability in optimizing quantum dynamics
• Quantum Control Landscapes Are Almost Always Trap Free
• Computational complexity of the Rydberg blockade in two dimensions

Cited by in corpus (11)

• Parameter Concentration in Quantum Approximate Optimization
• Improved success probability with greater circuit depth for the quantum approximate optimization algorithm
• Training Saturation in Layerwise Quantum Approximate Optimisation
• Policy Gradient based Quantum Approximate Optimization Algorithm
• Parameters Fixing Strategy for Quantum Approximate Optimization Algorithm
• Analytical Framework for Quantum Alternating Operator Ansätze
• Mixer-Phaser Ansätze for Quantum Optimization with Hard Constraints
• Progress towards analytically optimal angles in quantum approximate optimisation
• A quantum algorithm to count weighted ground states of classical spin Hamiltonians
• QPack: Quantum Approximate Optimization Algorithms as universal benchmark for quantum computers
• Variational Quantum Algorithms for Euclidean Discrepancy and Covariate-Balancing