Iterative Quantum Optimization with Adaptive Problem Hamiltonian

• URL: http://arxiv.org/abs/2204.13432v1
• Date: Thu, 28 Apr 2022 12:04:03 GMT
• Title: Iterative Quantum Optimization with Adaptive Problem Hamiltonian
• Authors: Yifeng Rocky Zhu, David Joseph, Cong Ling, Florian Mintert
• Abstract summary: We describe an iterative algorithm in which a solution obtained with such a restricted problem Hamiltonian is used to define a new problem Hamiltonian that is better suited than the previous one. In numerical examples of the shortest vector problem, we show that the algorithm with a sequence of improved problem Hamiltonians converges to the desired solution.
• Score: 19.4417702222583
• License: http://creativecommons.org/licenses/by-nc-nd/4.0/
• Abstract: Quantum optimization algorithms hold the promise of solving classically hard, discrete optimization problems in practice. The requirement of encoding such problems in a Hamiltonian realized with a finite -- and currently small -- number of qubits, however, poses the risk of finding only the optimum within the restricted space supported by this Hamiltonian. We describe an iterative algorithm in which a solution obtained with such a restricted problem Hamiltonian is used to define a new problem Hamiltonian that is better suited than the previous one. In numerical examples of the shortest vector problem, we show that the algorithm with a sequence of improved problem Hamiltonians converges to the desired solution.

Related papers

• Sum-of-Squares inspired Quantum Metaheuristic for Polynomial Optimization with the Hadamard Test and Approximate Amplitude Constraints [76.53316706600717]
  Recently proposed quantum algorithm arXiv:2206.14999 is based on semidefinite programming (SDP) We generalize the SDP-inspired quantum algorithm to sum-of-squares. Our results show that our algorithm is suitable for large problems and approximate the best known classicals.
  arXiv  Detail & Related papers  (2024-08-14T19:04:13Z)
• BHT-QAOA: Generalizing Quantum Approximate Optimization Algorithm to Solve Arbitrary Boolean Problems as Hamiltonians [0.0]
  A new methodology is proposed to solve classical Boolean problems as Hamiltonians. The total utilized numbers of qubits and quantum gates are dramatically minimized for the final quantum circuits of Hamiltonians.
  arXiv  Detail & Related papers  (2024-07-09T22:02:59Z)
• Scalable embedding of parity constraints in quantum annealing hardware [0.0]
  We present fixed, modular and scalable embeddings that can be used to embed any optimization problem described as an Ising Hamiltonian. These embeddings are the result of an extension of the well-known parity mapping. We show how our new embeddings can be mapped to existing quantum annealers and that the embedded Hamiltonian physical properties match the original Hamiltonian properties.
  arXiv  Detail & Related papers  (2024-05-23T16:14:33Z)
• Symmetries and Dimension Reduction in Quantum Approximate Optimization Algorithm [1.3469999282609788]
  We focus on the generalized formulation of optimization problems defined on the sets of $n-element $d$-ary strings. Our main contribution encompasses dimension for the originally proposed QAOA. Restricting the algorithm to spaces of smaller dimension may lead to significant acceleration of both quantum and classical simulation of circuits.
  arXiv  Detail & Related papers  (2023-09-25T00:35:40Z)
• Ising Hamiltonians for Constrained Combinatorial Optimization Problems and the Metropolis-Hastings Warm-Starting Algorithm [0.0]
  Quantum approximate optimization algorithm (QAOA) is a promising variational quantum algorithm for optimization problems. The Metropolis-Hassting warm-starting algorithm for QAOA is presented which can provably converge to the global optimal solutions.
  arXiv  Detail & Related papers  (2023-07-18T05:28:45Z)
• 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)
• Fixed Depth Hamiltonian Simulation via Cartan Decomposition [59.20417091220753]
  We present a constructive algorithm for generating quantum circuits with time-independent depth. We highlight our algorithm for special classes of models, including Anderson localization in one dimensional transverse field XY model. In addition to providing exact circuits for a broad set of spin and fermionic models, our algorithm provides broad analytic and numerical insight into optimal Hamiltonian simulations.
  arXiv  Detail & Related papers  (2021-04-01T19:06:00Z)
• Conditional gradient methods for stochastically constrained convex minimization [54.53786593679331]
  We propose two novel conditional gradient-based methods for solving structured convex optimization problems. The most important feature of our framework is that only a subset of the constraints is processed at each iteration. Our algorithms rely on variance reduction and smoothing used in conjunction with conditional gradient steps, and are accompanied by rigorous convergence guarantees.
  arXiv  Detail & Related papers  (2020-07-07T21:26:35Z)
• Constructing Driver Hamiltonians for Optimization Problems with Linear Constraints [0.0]
  We develop a simple and intuitive framework for reasoning about the commutation of Hamiltonians with linear constraints. Because unitary operators are exponentials of Hermitian operators, these results can also be applied to the construction of mixers in the Quantum Alternating Operator Ansatz framework.
  arXiv  Detail & Related papers  (2020-06-22T06:47:50Z)
• 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)
• Cross Entropy Hyperparameter Optimization for Constrained Problem Hamiltonians Applied to QAOA [68.11912614360878]
  Hybrid quantum-classical algorithms such as Quantum Approximate Optimization Algorithm (QAOA) are considered as one of the most encouraging approaches for taking advantage of near-term quantum computers in practical applications. Such algorithms are usually implemented in a variational form, combining a classical optimization method with a quantum machine to find good solutions to an optimization problem. In this study we apply a Cross-Entropy method to shape this landscape, which allows the classical parameter to find better parameters more easily and hence results in an improved performance.
  arXiv  Detail & Related papers  (2020-03-11T13:52:41Z)

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.