Globally Optimizing QAOA Circuit Depth for Constrained Optimization Problems
We develop a global variable substitution method that reduces <i>n</i>-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 sol...
| Main Authors: | , , , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
MDPI AG
2021-10-01
|
| Series: | Algorithms |
| Subjects: | |
| Online Access: | https://www.mdpi.com/1999-4893/14/10/294 |
| _version_ | 1797515601729552384 |
|---|---|
| author | Rebekah Herrman Lorna Treffert James Ostrowski Phillip C. Lotshaw Travis S. Humble George Siopsis |
| author_facet | Rebekah Herrman Lorna Treffert James Ostrowski Phillip C. Lotshaw Travis S. Humble George Siopsis |
| author_sort | Rebekah Herrman |
| collection | DOAJ |
| description | We develop a global variable substitution method that reduces <i>n</i>-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. |
| first_indexed | 2024-03-10T06:47:41Z |
| format | Article |
| id | doaj.art-cf21f31684ce4d1b9b954f5bbc4effb6 |
| institution | Directory Open Access Journal |
| issn | 1999-4893 |
| language | English |
| last_indexed | 2024-03-10T06:47:41Z |
| publishDate | 2021-10-01 |
| publisher | MDPI AG |
| record_format | Article |
| series | Algorithms |
| spelling | doaj.art-cf21f31684ce4d1b9b954f5bbc4effb62023-11-22T17:08:29ZengMDPI AGAlgorithms1999-48932021-10-01141029410.3390/a14100294Globally Optimizing QAOA Circuit Depth for Constrained Optimization ProblemsRebekah Herrman0Lorna Treffert1James Ostrowski2Phillip C. Lotshaw3Travis S. Humble4George Siopsis5Department of Industrial and Systems Engineering, University of Tennessee at Knoxville, Knoxville, TN 37996, USADepartment of Industrial and Systems Engineering, University of Tennessee at Knoxville, Knoxville, TN 37996, USADepartment of Industrial and Systems Engineering, University of Tennessee at Knoxville, Knoxville, TN 37996, USAQuantum Computing Institute, Oak Ridge National Laboratory, Oak Ridge, TN 37830, USAQuantum Computing Institute, Oak Ridge National Laboratory, Oak Ridge, TN 37830, USADepartment of Physics and Astronomy, University of Tennessee at Knoxville, Knoxville, TN 37996-1200, USAWe develop a global variable substitution method that reduces <i>n</i>-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.https://www.mdpi.com/1999-4893/14/10/294quantum approximate optimization algorithmcircuit depth3-SAT |
| spellingShingle | Rebekah Herrman Lorna Treffert James Ostrowski Phillip C. Lotshaw Travis S. Humble George Siopsis Globally Optimizing QAOA Circuit Depth for Constrained Optimization Problems Algorithms quantum approximate optimization algorithm circuit depth 3-SAT |
| title | Globally Optimizing QAOA Circuit Depth for Constrained Optimization Problems |
| title_full | Globally Optimizing QAOA Circuit Depth for Constrained Optimization Problems |
| title_fullStr | Globally Optimizing QAOA Circuit Depth for Constrained Optimization Problems |
| title_full_unstemmed | Globally Optimizing QAOA Circuit Depth for Constrained Optimization Problems |
| title_short | Globally Optimizing QAOA Circuit Depth for Constrained Optimization Problems |
| title_sort | globally optimizing qaoa circuit depth for constrained optimization problems |
| topic | quantum approximate optimization algorithm circuit depth 3-SAT |
| url | https://www.mdpi.com/1999-4893/14/10/294 |
| work_keys_str_mv | AT rebekahherrman globallyoptimizingqaoacircuitdepthforconstrainedoptimizationproblems AT lornatreffert globallyoptimizingqaoacircuitdepthforconstrainedoptimizationproblems AT jamesostrowski globallyoptimizingqaoacircuitdepthforconstrainedoptimizationproblems AT phillipclotshaw globallyoptimizingqaoacircuitdepthforconstrainedoptimizationproblems AT travisshumble globallyoptimizingqaoacircuitdepthforconstrainedoptimizationproblems AT georgesiopsis globallyoptimizingqaoacircuitdepthforconstrainedoptimizationproblems |