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.

13 pages, 11 figures

References in corpus (8)

• Supplementary information for "Quantum supremacy using a programmable superconducting processor"
• The density-matrix renormalization group in the age of matrix product states
• Quantum computational advantage using photons
• An introduction to quantum machine learning
• Randomized Benchmarking of Quantum Gates
• A class of quantum many-body states that can be efficiently simulated
• Criticality, the area law, and the computational power of PEPS
• Scaling of entanglement support for Matrix Product States

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