Paper 2023/1854

A note on quantum approximate optimization algorithm

Zhengjun Cao
Abstract

The general quantum approximate optimization algorithm (QAOA) produces approximate solutions for combinatorial optimization problems. The algorithm depends on a positive integer $p$ and the quality of approximation improves as $p$ is increased. In this note, we put some questions about the general QAOA. We also find the recursive QAOA for MaxCut problem is flawed because all quantum gates involved in the algorithm are single qubit gates. No any entangling gate is used, which results in that the quantum computing power cannot be certified for the problem.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
Preprint.
Keywords
Combinatorial optimizationQAOARQAOAMaxCutComputational basisUniform superposition
Contact author(s)
caozhj @ shu edu cn
History
2023-12-04: approved
2023-12-03: received
See all versions
Short URL
https://ia.cr/2023/1854
License
No rights reserved
CC0

BibTeX

@misc{cryptoeprint:2023/1854,
      author = {Zhengjun Cao},
      title = {A note on quantum approximate optimization algorithm},
      howpublished = {Cryptology {ePrint} Archive, Paper 2023/1854},
      year = {2023},
      url = {https://eprint.iacr.org/2023/1854}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.