Constrained Optimization via Quantum Zeno Dynamics

• URL: http://arxiv.org/abs/2209.15024v6
• Date: Tue, 8 Aug 2023 23:48:38 GMT
• Title: Constrained Optimization via Quantum Zeno Dynamics
• Authors: Dylan Herman, Ruslan Shaydulin, Yue Sun, Shouvanik Chakrabarti, Shaohan Hu, Pierre Minssen, Arthur Rattew, Romina Yalovetzky, Marco Pistoia
• Abstract summary: We introduce a technique that uses quantum Zeno dynamics to solve optimization problems with multiple arbitrary constraints, including inequalities. We show that the dynamics of quantum optimization can be efficiently restricted to the in-constraint subspace on a fault-tolerant quantum computer.
• Score: 23.391640416533455
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Constrained optimization problems are ubiquitous in science and industry. Quantum algorithms have shown promise in solving optimization problems, yet none of the current algorithms can effectively handle arbitrary constraints. We introduce a technique that uses quantum Zeno dynamics to solve optimization problems with multiple arbitrary constraints, including inequalities. We show that the dynamics of quantum optimization can be efficiently restricted to the in-constraint subspace on a fault-tolerant quantum computer via repeated projective measurements, requiring only a small number of auxiliary qubits and no post-selection. Our technique has broad applicability, which we demonstrate by incorporating it into the quantum approximate optimization algorithm (QAOA) and variational quantum circuits for optimization. We evaluate our method numerically on portfolio optimization problems with multiple realistic constraints and observe better solution quality and higher in-constraint probability than state-of-the-art techniques. We implement a proof-of-concept demonstration of our method on the Quantinuum H1-2 quantum processor.

Related papers

• Bayesian Parameterized Quantum Circuit Optimization (BPQCO): A task and hardware-dependent approach [49.89480853499917]
  Variational quantum algorithms (VQA) have emerged as a promising quantum alternative for solving optimization and machine learning problems. In this paper, we experimentally demonstrate the influence of the circuit design on the performance obtained for two classification problems. We also study the degradation of the obtained circuits in the presence of noise when simulating real quantum computers.
  arXiv  Detail & Related papers  (2024-04-17T11:00:12Z)
• Photonic counterdiabatic quantum optimization algorithm [3.2174634059872154]
  We propose a hybrid quantum- approximate optimization algorithm for quantum computing that is tailored for continuous-variable problems. We conduct proof-of-principle experiments on an-photo quantum chip.
  arXiv  Detail & Related papers  (2023-07-27T13:33:33Z)
• Enhancing Quantum Algorithms for Quadratic Unconstrained Binary Optimization via Integer Programming [0.0]
  In this work, we integrate the potentials of quantum and classical techniques for optimization. We reduce the problem size according to a linear relaxation such that the reduced problem can be handled by quantum machines of limited size. We present numerous computational results from real quantum hardware.
  arXiv  Detail & Related papers  (2023-02-10T20:12:53Z)
• Constrained Quantum Optimization for Extractive Summarization on a Trapped-ion Quantum Computer [13.528362112761805]
  We show the largest-to-date execution of a quantum optimization algorithm that preserves constraints on quantum hardware. We execute XY-QAOA circuits that restrict the quantum evolution to the in-constraint subspace, using up to 20 qubits and a two-qubit gate depth of up to 159. We discuss the respective trade-offs of the algorithms and implications for their execution on near-term quantum hardware.
  arXiv  Detail & Related papers  (2022-06-13T16:21:04Z)
• Efficient Use of Quantum Linear System Algorithms in Interior Point Methods for Linear Optimization [0.0]
  We develop an Inexact Infeasible Quantum Interior Point Method to solve linear optimization problems. We also discuss how can we get an exact solution by Iterative Refinement without excessive time of quantum solvers.
  arXiv  Detail & Related papers  (2022-05-02T21:30:56Z)
• Quadratic Unconstrained Binary Optimisation via Quantum-Inspired Annealing [58.720142291102135]
  We present a classical algorithm to find approximate solutions to instances of quadratic unconstrained binary optimisation. We benchmark our approach for large scale problem instances with tuneable hardness and planted solutions.
  arXiv  Detail & Related papers  (2021-08-18T09:26:17Z)
• Adiabatic Quantum Graph Matching with Permutation Matrix Constraints [75.88678895180189]
  Matching problems on 3D shapes and images are frequently formulated as quadratic assignment problems (QAPs) with permutation matrix constraints, which are NP-hard. We propose several reformulations of QAPs as unconstrained problems suitable for efficient execution on quantum hardware. The proposed algorithm has the potential to scale to higher dimensions on future quantum computing architectures.
  arXiv  Detail & Related papers  (2021-07-08T17:59:55Z)
• Variational Quantum Optimization with Multi-Basis Encodings [62.72309460291971]
  We introduce a new variational quantum algorithm that benefits from two innovations: multi-basis graph complexity and nonlinear activation functions. Our results in increased optimization performance, two increase in effective landscapes and a reduction in measurement progress.
  arXiv  Detail & Related papers  (2021-06-24T20:16:02Z)
• 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)
• Space-efficient binary optimization for variational computing [68.8204255655161]
  We show that it is possible to greatly reduce the number of qubits needed for the Traveling Salesman Problem. We also propose encoding schemes which smoothly interpolate between the qubit-efficient and the circuit depth-efficient models.
  arXiv  Detail & Related papers  (2020-09-15T18:17:27Z)

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.