Feedback-Based Quantum Strategies for Constrained Combinatorial Optimization Problems

• URL: http://arxiv.org/abs/2502.14369v1
• Date: Thu, 20 Feb 2025 08:57:28 GMT
• Title: Feedback-Based Quantum Strategies for Constrained Combinatorial Optimization Problems
• Authors: Salahuddin Abdul Rahman, Özkan Karabacak, Rafal Wisniewski,
• Abstract summary: We extend the feedback-based quantum algorithms framework to address a broader class of constraints known as invalid configuration (IC) constraints. We propose an alternative method tailored for feedback-based quantum algorithms that directly tackles IC constraints without requiring slack variables. These methods eliminate the need for slack variables, significantly reducing the quantum circuit depth and the number of qubits required.
• Score: 0.6554326244334868
• License:
• Abstract: Feedback-based quantum algorithms have recently emerged as potential methods for approximating the ground states of Hamiltonians. One such algorithm, the feedback-based algorithm for quantum optimization (FALQON), is specifically designed to solve quadratic unconstrained binary optimization problems. Its extension, the feedback-based algorithm for quantum optimization with constraints (FALQON-C), was introduced to handle constrained optimization problems with equality and inequality constraints. In this work, we extend the feedback-based quantum algorithms framework to address a broader class of constraints known as invalid configuration (IC) constraints, which explicitly prohibit specific configurations of decision variables. We first present a transformation technique that converts the constrained optimization problem with invalid configuration constraints into an equivalent unconstrained problem by incorporating a penalizing term into the cost function. Then, leaning upon control theory, we propose an alternative method tailored for feedback-based quantum algorithms that directly tackles IC constraints without requiring slack variables. Our approach introduces a new operator that encodes the optimal feasible solution of the constrained optimization problem as its ground state. Then, a controlled quantum system based on the Lyapunov control technique is designed to ensure convergence to the ground state of this operator. Two approaches are introduced in the design of this operator to address IC constraints: the folded spectrum approach and the deflation approach. These methods eliminate the need for slack variables, significantly reducing the quantum circuit depth and the number of qubits required. We show the effectiveness of our proposed algorithms through numerical simulations.

Related papers

• Feedback-Based Quantum Algorithm for Constrained Optimization Problems [0.6554326244334868]
  We introduce a new operator that encodes the problem's solution as its ground state. We show that our proposed algorithm saves computational resources by reducing the depth of the quantum circuit.
  arXiv  Detail & Related papers  (2024-06-12T12:58:43Z)
• 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)
• Lagrangian Duality in Quantum Optimization: Overcoming QUBO Limitations for Constrained Problems [0.0]
  We propose an approach to solving constrained optimization problems based on embedding the concept of Lagrangian duality into the framework of adiabatic quantum computation. Within the setting of circuit-model fault-tolerant quantum computation, we demonstrate that this approach achieves a quadratic improvement in circuit depth and maintains a constraint-independent circuit width.
  arXiv  Detail & Related papers  (2023-10-06T19:09:55Z)
• Near-Term Distributed Quantum Computation using Mean-Field Corrections and Auxiliary Qubits [77.04894470683776]
  We propose near-term distributed quantum computing that involve limited information transfer and conservative entanglement production. We build upon these concepts to produce an approximate circuit-cutting technique for the fragmented pre-training of variational quantum algorithms.
  arXiv  Detail & Related papers  (2023-09-11T18:00:00Z)
• Hybrid Quantum Algorithms integrating QAOA, Penalty Dephasing and Zeno Effect for Solving Binary Optimization Problems with Multiple Constraints [5.259170150405252]
  This paper presents a hybrid framework that combines the use of standard Ising Hamiltonians to solve a subset of the constraints. The resolution of these non-Ising constraints is achieved through either penalty dephasing or the quantum Zeno effect.
  arXiv  Detail & Related papers  (2023-05-14T03:49:10Z)
• Exploiting In-Constraint Energy in Constrained Variational Quantum Optimization [7.541345730271882]
  In general, such constraints cannot be easily encoded in the circuit, and the quantum circuit measurement outcomes are not guaranteed to respect the constraints. We propose a new approach for solving constrained optimization problems with unimplement, easy-to-constrained quantum ansatze. We implement our method in QVoice, a Python package that interfaces with Qiskit for quick prototyping in simulators and on quantum hardware.
  arXiv  Detail & Related papers  (2022-11-13T20:58:00Z)
• Constrained Optimization via Quantum Zeno Dynamics [23.391640416533455]
  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.
  arXiv  Detail & Related papers  (2022-09-29T18:00:40Z)
• Decomposition of Matrix Product States into Shallow Quantum Circuits [62.5210028594015]
  tensor network (TN) algorithms can be mapped to parametrized quantum circuits (PQCs) We propose a new protocol for approximating TN states using realistic quantum circuits. Our results reveal one particular protocol, involving sequential growth and optimization of the quantum circuit, to outperform all other methods.
  arXiv  Detail & Related papers  (2022-09-01T17:08:41Z)
• 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)
• 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)
• 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.