Forbidden subspaces for level-1 QAOA and IQP circuits

Abstract

We present a thorough investigation of problems that can be solved exactly with the level-1 Quantum Approximate Optimization Algorithm (QAOA). To this end we implicitly define a class of problem Hamiltonians that employed as phase separator in a level-1 QAOA circuit provide unit overlap with a target subspace spanned by a set of computational basis states. For one-dimensional target subspaces we identify instances within the implicitly defined class of Hamiltonians for which Quantum Annealing (QA) and Simulated Annealing (SA) have an exponentially small probability to find the solution. Consequently, our results define a first demarcation line between QAOA, QA and SA, and highlight the fundamental differences between an interference-based search heuristic such as QAOA and heuristics that are based on thermal and quantum fluctuations like SA and QA respectively. Moreover, for two-dimensional solution subspaces we are able to show that the depth of the QAOA circuit grows linearly with the Hamming distance between the two target states. We further show that there are no genuine solutions for target subspaces of dimension higher than $2$ and smaller than $2^n$. We also transfer these results to Instantaneous Quantum Polynomial (IQP) circuits.

arXiv admin note: substantial text overlap with arXiv:1901.01903

References in corpus (33)

• Supplementary information for "Quantum supremacy using a programmable superconducting processor"
• A variational eigenvalue solver on a quantum processor
• Ising formulations of many NP problems
• Quantum Annealing in the Transverse Ising Model
• A Quantum Approximate Optimization Algorithm
• Demonstration of Two-Qubit Algorithms with a Superconducting Quantum Processor
• Demonstration of a small programmable quantum computer with atomic qubits
• Quantum Approximate Optimization Algorithm: Performance, Mechanism, and Implementation on Near-Term Devices
• Digitized adiabatic quantum computing with a superconducting circuit
• Quantum advantage with shallow circuits
• Quantum Approximate Optimization Algorithm for MaxCut: A Fermionic View
• Hierarchical quantum classifiers
• Classical simulation of commuting quantum computations implies collapse of the polynomial hierarchy
• Average-case complexity versus approximate simulation of commuting quantum computations
• Demonstration of Universal Parametric Entangling Gates on a Multi-Qubit Lattice
• What is the Computational Value of Finite Range Tunneling?
• Layered architecture for quantum computing
• Achieving quantum supremacy with sparse and noisy commuting quantum computations
• Quantum Supremacy through the Quantum Approximate Optimization Algorithm
• Quantum Sampling Problems, BosonSampling and Quantum Supremacy
• Efficient classical simulation of random shallow 2D quantum circuits
• Optimizing Variational Quantum Algorithms using Pontryagin's Minimum Principle
• Near-optimal quantum circuit for Grover's unstructured search using a transverse field
• A Quantum Approximate Optimization Algorithm Applied to a Bounded Occurrence Constraint Problem
• Benchmarking the Quantum Approximate Optimization Algorithm
• Efficient Quantum Circuits for Diagonal Unitaries Without Ancillas
• Practical optimization for hybrid quantum-classical algorithms
• Seeking Quantum Speedup Through Spin Glasses: The Good, the Bad, and the Ugly
• Performance of the Quantum Approximate Optimization Algorithm on the Maximum Cut Problem
• A quantum algorithm to train neural networks using low-depth circuits
• A deceptive step towards quantum speedup detection
• For Fixed Control Parameters the Quantum Approximate Optimization Algorithm's Objective Function Value Concentrates for Typical Instances
• Quantum Annealing: a journey through Digitalization, Control, and hybrid Quantum Variational schemes

Cited by in corpus (4)

• Noisy intermediate-scale quantum (NISQ) algorithms
• Beating classical heuristics for the binary paint shop problem with the quantum approximate optimization algorithm
• Quantum algorithms with local particle number conservation: noise effects and error correction
• Multiobjective variational quantum optimization for constrained problems: an application to Cash Management