Globally Optimizing QAOA Circuit Depth for Constrained Optimization Problems
Abstract
We develop a global variable substitution method that reduces n-variable monomials in combinatorial optimization problems to equivalent instances with monomials in fewer variables. We apply this technique to 3-SAT and analyze the optimal quantum unitary circuit depth needed to solve the reduced problem using the quantum approximate optimization algorithm. For benchmark 3-SAT problems, we find that the upper bound of the unitary circuit depth is smaller when the problem is formulated as a product and uses the substitution method to decompose gates than when the problem is written in the linear formulation, which requires no decomposition.
Document Details
- Document Type
- Pub Defense Publication
- Publication Date
- Oct 11, 2021
- Source ID
- 10.3390/a14100294
Entities
People
- George Siopsis
- James Ostrowski
- Lorna Treffert
- Phillip C. Lotshaw
- Rebekah Herrman
- Travis Humble
Organizations
- Air Force Office of Scientific Research
- Army Research Office
- Defense Advanced Research Projects Agency
- National Science Foundation