Calibrating the Classical Hardness of the Quantum Approximate Optimization Algorithm

Abstract

Trading fidelity for scale enables approximate classical simulators such as matrix product states (MPS) to run quantum circuits beyond exact methods. A control parameter, the so-called bond dimension $\chi$ for MPS, governs the allocated computational resources and the output fidelity. Here, we characterize the fidelity for the quantum approximate optimization algorithm by the expectation value of the cost function it seeks to minimize and find that it follows a scaling law $F(\ln \chi /N)$ with $N$ the number of qubits. With $\ln \chi$ amounting to the entanglement that an MPS can encode, we show that the relevant variable for investigating the fidelity is the entanglement per qubit. Importantly, our results calibrate the classical computational power required to achieve the desired fidelity and benchmark the performance of quantum hardware in a realistic setup. For instance, we quantify the hardness of performing better classically than a noisy superconducting quantum processor by readily matching its output to the scaling function. Moreover, we relate the global fidelity to that of individual operations and establish its relationship with $\chi$ and $N$. We sharpen the requirements for noisy quantum computers to outperform classical techniques at running a quantum optimization algorithm in speed, size, and fidelity.

arXiv comment13 pages, 11 figures

References in corpus (47)

• Quantum Computing in the NISQ era and beyond
• Supplementary information for "Quantum supremacy using a programmable superconducting processor"
• Quantum Machine Learning
• The density-matrix renormalization group in the age of matrix product states
• Variational Quantum Algorithms
• Quantum computational advantage using photons
• A Practical Introduction to Tensor Networks: Matrix Product States and Projected Entangled Pair States
• Efficient simulation of one-dimensional quantum many-body systems
• An introduction to quantum machine learning
• Characterizing Quantum Supremacy in Near-Term Devices
• Randomized Benchmarking of Quantum Gates
• A class of quantum many-body states that can be efficiently simulated
• Quantum Computational Supremacy
• From the Quantum Approximate Optimization Algorithm to a Quantum Alternating Operator Ansatz
• Quantum Approximate Optimization Algorithm: Performance, Mechanism, and Implementation on Near-Term Devices
• Criticality, the area law, and the computational power of PEPS
• Classical simulation of quantum many-body systems with a tree tensor network
• Large-scale silicon quantum photonics implementing arbitrary two-qubit processing
• Quantum Approximate Optimization of Non-Planar Graph Problems on a Planar Superconducting Processor
• Quantum Optimization of Maximum Independent Set using Rydberg Atom Arrays
• Hand-waving and Interpretive Dance: An Introductory Course on Tensor Networks
• Theory of finite-entanglement scaling at one-dimensional quantum critical points
• Quantum Approximate Optimization Algorithm for MaxCut: A Fermionic View
• Universality of Phase Transition Dynamics: Topological Defects from Symmetry Breaking
• QAOA for Max-Cut requires hundreds of qubits for quantum speed-up
• Scaling of entanglement support for Matrix Product States
• Obstacles to State Preparation and Variational Optimization from Symmetry Protection
• Quantum Approximate Optimization of the Long-Range Ising Model with a Trapped-Ion Quantum Simulator
• Exploring entanglement and optimization within the Hamiltonian Variational Ansatz
• What limits the simulation of quantum computers?
• $XY$-mixers: analytical and numerical results for QAOA
• High-precision finite-size scaling analysis of the quantum-critical point of S=1/2 Heisenberg antiferromagnetic bilayers
• Avoiding local minima in variational quantum eigensolvers with the natural gradient optimizer
• Near-optimal quantum circuit for Grover's unstructured search using a transverse field
• Filtering variational quantum algorithms for combinatorial optimization
• Benchmarking the Quantum Approximate Optimization Algorithm
• Implementation of the XY interaction family with calibration of a single pulse
• Training A Quantum Optimizer
• Classical variational simulation of the Quantum Approximate Optimization Algorithm
• Improved success probability with greater circuit depth for the quantum approximate optimization algorithm
• How many qubits are needed for quantum computational supremacy?
• Classical simulation of lossy boson sampling using matrix product operators
• Progress toward favorable landscapes in quantum combinatorial optimization
• Optimising Matrix Product State Simulations of Shor's Algorithm
• Reachability Deficits in Quantum Approximate Optimization of Graph Problems
• Practical Verification of Quantum Properties in Quantum Approximate Optimization Runs
• Benchmarking treewidth as a practical component of tensor-network--based quantum simulation

Cited by in corpus (12)

• A Review on Quantum Approximate Optimization Algorithm and its Variants
• Towards adiabatic quantum computing using compressed quantum circuits
• A density-matrix renormalization group algorithm for simulating quantum circuits with a finite fidelity
• Quantum-Enhanced Greedy Combinatorial Optimization Solver
• Calibrating the role of entanglement in variational quantum circuits
• Mean-Field Approximate Optimization Algorithm
• Bias-Field Digitized Counterdiabatic Quantum Algorithm for Higher-Order Binary Optimization
• Genuine Multipartite Entanglement in Quantum Optimization
• Machine-Learning Insights into the Entanglement-trainability Correlation of Parameterized Quantum Circuits
• Optimization via Quantum Preconditioning
• Variational matrix product states for combinatorial optimization
• A New Scaling Function for QAOA Tensor Network Simulations