Globally optimizing QAOA circuit depth for constrained optimization problems

• URL: http://arxiv.org/abs/2108.03281v1
• Date: Fri, 6 Aug 2021 19:25:45 GMT
• Title: Globally optimizing QAOA circuit depth for constrained optimization problems
• Authors: Rebekah Herrman, Lorna Treffert, James Ostrowski, Phillip C. Lotshaw, Travis S. Humble, George Siopsis
• Abstract summary: We develop a global variable substitution method that reduces $n$-variable monomials in optimization problems to equivalent instances with monomials in fewer variables. We analyze the optimal quantum circuit depth needed to solve the reduced problem using the quantum approximate optimization algorithm.
• Score: 0.2609784101826761
• License: http://creativecommons.org/licenses/by/4.0/
• 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 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 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.

Related papers

• Decomposition Pipeline for Large-Scale Portfolio Optimization with Applications to Near-Term Quantum Computing [10.049166866086738]
  Portfolio optimization and rebalancing problems with constraints are often intractable or difficult to solve exactly. Our pipeline consistently decomposes real-world portfolio optimization problems into subproblems with a size reduction of approximately 80%. By decomposing large problems into several smaller subproblems, the pipeline enables the use of near-term quantum devices as solvers.
  arXiv  Detail & Related papers  (2024-09-16T14:05:52Z)
• A Sample Efficient Alternating Minimization-based Algorithm For Robust Phase Retrieval [56.67706781191521]
  In this work, we present a robust phase retrieval problem where the task is to recover an unknown signal. Our proposed oracle avoids the need for computationally spectral descent, using a simple gradient step and outliers.
  arXiv  Detail & Related papers  (2024-09-07T06:37:23Z)
• Optimizing Variational Circuits for Higher-Order Binary Optimization [2.578242050187029]
  We propose new approaches to encode their Hamiltonian into a ready-to-implement circuit involving only two-qubit gates. We evaluate our approaches by comparing them with the state of the art, showcasing clear gains in terms of circuit depth.
  arXiv  Detail & Related papers  (2023-07-31T15:27:06Z)
• Quantum Alternating Operator Ansatz for Solving the Minimum Exact Cover Problem [4.697039614904225]
  We adopt quantum alternating operator ansatz (QAOA+) to solve minimum exact cover (MEC) problem. The numerical results show that the solution can be obtained with high probability when level $p$ of the algorithm is low. We also optimize the quantum circuit by removing single-qubit rotating gates $R_Z$.
  arXiv  Detail & Related papers  (2022-11-28T12:45:52Z)
• Twisted hybrid algorithms for combinatorial optimization [68.8204255655161]
  Proposed hybrid algorithms encode a cost function into a problem Hamiltonian and optimize its energy by varying over a set of states with low circuit complexity. We show that for levels $p=2,ldots, 6$, the level $p$ can be reduced by one while roughly maintaining the expected approximation ratio.
  arXiv  Detail & Related papers  (2022-03-01T19:47:16Z)
• Adaptive pruning-based optimization of parameterized quantum circuits [62.997667081978825]
  Variisy hybrid quantum-classical algorithms are powerful tools to maximize the use of Noisy Intermediate Scale Quantum devices. We propose a strategy for such ansatze used in variational quantum algorithms, which we call "Efficient Circuit Training" (PECT) Instead of optimizing all of the ansatz parameters at once, PECT launches a sequence of variational algorithms.
  arXiv  Detail & Related papers  (2020-10-01T18:14:11Z)
• Lower Bounds on Circuit Depth of the Quantum Approximate Optimization Algorithm [0.3058685580689604]
  We show how the structure of problem instances can be used to identify lower bounds for circuit depth. We argue that MaxCut, MaxIndSet, and some instances of Vertex Covering and Boolean satisifiability problems are suitable for QAOA approaches.
  arXiv  Detail & Related papers  (2020-08-04T20:52:34Z)
• Follow the bisector: a simple method for multi-objective optimization [65.83318707752385]
  We consider optimization problems, where multiple differentiable losses have to be minimized. The presented method computes descent direction in every iteration to guarantee equal relative decrease of objective functions.
  arXiv  Detail & Related papers  (2020-07-14T09:50:33Z)
• A Two-Timescale Framework for Bilevel Optimization: Complexity Analysis and Application to Actor-Critic [142.1492359556374]
  Bilevel optimization is a class of problems which exhibit a two-level structure. We propose a two-timescale approximation (TTSA) algorithm for tackling such a bilevel problem. We show that a two-timescale natural actor-critic policy optimization algorithm can be viewed as a special case of our TTSA framework.
  arXiv  Detail & Related papers  (2020-07-10T05:20:02Z)
• Convergence of adaptive algorithms for weakly convex constrained optimization [59.36386973876765]
  We prove the $mathcaltilde O(t-1/4)$ rate of convergence for the norm of the gradient of Moreau envelope. Our analysis works with mini-batch size of $1$, constant first and second order moment parameters, and possibly smooth optimization domains.
  arXiv  Detail & Related papers  (2020-06-11T17:43:19Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.