Forbidden subspaces for level-1 quantum approximate optimization algorithm and instantaneous quantum polynomial circuits
Streif M, Leib M (2020)
Publication Type: Journal article
Publication year: 2020
Journal
Book Volume: 102
Article Number: 042416
Journal Issue: 4
DOI: 10.1103/PhysRevA.102.042416
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 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.
Authors with CRIS profile
Involved external institutions
Germany (DE)How to cite
APA:
Streif, M., & Leib, M. (2020). Forbidden subspaces for level-1 quantum approximate optimization algorithm and instantaneous quantum polynomial circuits. Physical Review A, 102(4). https://dx.doi.org/10.1103/PhysRevA.102.042416
MLA:
Streif, Michael, and Martin Leib. "Forbidden subspaces for level-1 quantum approximate optimization algorithm and instantaneous quantum polynomial circuits." Physical Review A 102.4 (2020).
BibTeX: Download