DOE OSTI · 1830115
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.
Explore related subjects
Keep this discovery
Explore connections, maps & timelines
Herrman, Rebekah, Treffert, Lorna, Ostrowski, James, Lotshaw, Phillip C., Humble, Travis S., Siopsis, George. 2021-10-11. Globally Optimizing QAOA Circuit Depth for Constrained Optimization Problems. https://doi.org/10.3390/a14100294. https://searchnasa.com/record/osti%3A1830115/globally-optimizing-qaoa-circuit-depth-for-constrained-optimization-problems
Citations retain the original authors and DOI and include this site’s record URL. If this discovery service contributed to your research, you can also cite Search NASA by Indiciae: BibTeX · RIS.