2020/07/24 by Michael Streif, Martin Leib · 8 citations
Computer Science · Mathematics · Physics and Astronomy · #Algorithm #Combinatorics #Computer science #Dimension (graph theory) #Discrete mathematics #Heuristics #Linear subspace #Mathematical analysis #Mathematical optimization #Mathematics #Physics #Polynomial #Pure mathematics #Quantum #Quantum Computing Algorithms and Architecture #Quantum Information and Cryptography #Quantum algorithm #Quantum annealing #Quantum computer #Quantum mechanics #Quantum-Dot Cellular Automata #Qubit #Subspace topology #quant-ph
paper · pdf · doi:10.1103/physreva.102.042416
published in Physical Review A 102(4) (American Physical Society) · arXiv admin note: substantial text overlap with arXiv:1901.01903
arxiv created 2020/07/24 · openalex created_date 2020/07/29 · openalex publication_date 2020/10/28 · arxiv updated 2020/11/04 · openalex updated_date 2026/08/05
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 are employed as phase separators in a level-1 QAOA circuit and 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 of finding the solution. Consequently, our results define a demarcation line between QAOA on one hand and QA and SA on the other, 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 2n. We also transfer these results to instantaneous quantum polynomial (IQP) circuits.