Vanishing performance of the parity-encoded quantum approximate optimization algorithm applied to spin-glass models

Abstract

The parity mapping provides a geometrically local encoding of the Quantum Approximate Optimization Algorithm (QAOA), at the expense of having a quadratic qubit overhead for all-to-all connected problems. In this work, we benchmark the parity-encoded QAOA on spin-glass models. We address open questions in the scaling of this algorithm. In particular, we show that for fixed number of parity-encoded QAOA layers, the performance or the output energy, vanishes towards zero (the value achieved by random guessing) with problem size $N$ as $N^{-1/2}$. Our results suggest that the parity-encoded QAOA does not have a promising scaling compared to the standard version of QAOA. We perform tensor-network calculations to confirm our results, and comment on the concentration of optimal QAOA parameters over problem instances.

26 pages, 14 figures

References in corpus (20)

• Variational Quantum Algorithms
• The theory of variational hybrid quantum-classical algorithms
• A Quantum Approximate Optimization Algorithm
• Noisy intermediate-scale quantum (NISQ) algorithms
• Cost Function Dependent Barren Plateaus in Shallow Parametrized Quantum Circuits
• Hybrid quantum-classical algorithms and quantum error mitigation
• Simulating quantum computation by contracting tensor networks
• The Quantum Approximate Optimization Algorithm and the Sherrington-Kirkpatrick Model at Infinite Size
• Hyper-optimized tensor network contraction
• Quantum annealing initialization of the quantum approximate optimization algorithm
• Parameter Concentration in Quantum Approximate Optimization
• The Quantum Approximate Optimization Algorithm Needs to See the Whole Graph: A Typical Case
• Generalized swap networks for near-term quantum computing
• The Quantum Approximate Optimization Algorithm Needs to See the Whole Graph: Worst Case Examples
• Expectation Values from the Single-Layer Quantum Approximate Optimization Algorithm on Ising Problems
• The Quantum Approximate Optimization Algorithm at High Depth for MaxCut on Large-Girth Regular Graphs and the Sherrington-Kirkpatrick Model
• Optimal, hardware native decomposition of parameterized multi-qubit Pauli gates
• Error Mitigation for Quantum Approximate Optimization
• Semidefinite Programs on Sparse Random Graphs and their Application to Community Detection
• Similarity-Based Parameter Transferability in the Quantum Approximate Optimization Algorithm