Mixed-Integer Programming Using a Bosonic Quantum Computer

• URL: http://arxiv.org/abs/2112.13917v2
• Date: Tue, 7 Jun 2022 22:48:26 GMT
• Title: Mixed-Integer Programming Using a Bosonic Quantum Computer
• Authors: Farhad Khosravi, Artur Scherer, and Pooya Ronagh
• Abstract summary: We propose a scheme for solving mixed-integer programming problems in which the optimization problem is translated to a ground-state preparation problem on a bosonic quantum field modes (qumodes) We show numerical demonstrations by a circuit-based optical quantum computer with each individual qumode prepared.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We propose a scheme for solving mixed-integer programming problems in which the optimization problem is translated to a ground-state preparation problem on a set of bosonic quantum field modes (qumodes). We perform numerical demonstrations by simulating a circuit-based optical quantum computer with each individual qumode prepared in a Gaussian state. We simulate an adiabatic evolution from an initial mixing Hamiltonian, written in terms of the momentum operators of the qumodes, to a final Hamiltonian which is a polynomial of the position and boson number operators. In these demonstrations, we solve a variety of small non-convex optimization problems in integer programming, continuous non-convex optimization, and mixed-integer programming.

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)
• Mixed Integer Linear Programming Solver Using Benders Decomposition Assisted by Neutral Atom Quantum Processor [0.0]
  This paper presents a new hybrid classical-quantum approach to solve Mixed Linear Programming (MILP) We apply Benders decomposition (BD) to segment MILPs into a master problem (MP) and a subproblem (SP) Our MILP to QUBO conversion tightens the upper bounds of the involved continuous variables, positively impacting the required qubit count, and the convergence of the algorithm.
  arXiv  Detail & Related papers  (2024-02-08T15:33:09Z)
• A Universal Quantum Algorithm for Weighted Maximum Cut and Ising Problems [0.0]
  We propose a hybrid quantum-classical algorithm to compute approximate solutions of binary problems. We employ a shallow-depth quantum circuit to implement a unitary and Hermitian operator that block-encodes the weighted maximum cut or the Ising Hamiltonian. Measuring the expectation of this operator on a variational quantum state yields the variational energy of the quantum system.
  arXiv  Detail & Related papers  (2023-06-10T23:28:13Z)
• Depth analysis of variational quantum algorithms for heat equation [0.0]
  We consider three approaches to solve the heat equation on a quantum computer. An exponential number of Pauli products in the Hamiltonian decomposition does not allow for the quantum speed up to be achieved. The ansatz tree approach exploits an explicit form of the matrix what makes it possible to achieve an advantage over classical algorithms.
  arXiv  Detail & Related papers  (2022-12-23T14:46:33Z)
• Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
  We study the problem of designing worst-case to average-case reductions for quantum algorithms. We provide an explicit and efficient transformation of quantum algorithms that are only correct on a small fraction of their inputs into ones that are correct on all inputs.
  arXiv  Detail & Related papers  (2022-12-06T22:01:49Z)
• Quantum Goemans-Williamson Algorithm with the Hadamard Test and Approximate Amplitude Constraints [62.72309460291971]
  We introduce a variational quantum algorithm for Goemans-Williamson algorithm that uses only $n+1$ qubits. Efficient optimization is achieved by encoding the objective matrix as a properly parameterized unitary conditioned on an auxilary qubit. We demonstrate the effectiveness of our protocol by devising an efficient quantum implementation of the Goemans-Williamson algorithm for various NP-hard problems.
  arXiv  Detail & Related papers  (2022-06-30T03:15:23Z)
• 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)
• Adiabatic Quantum Computing for Solving the Weapon-Target Assignment Problem [0.0]
  Recent technological advancements suggest that the adiabatic quantum computing ansatz may soon see practical applications. In this work, we adopt this computation paradigm to develop a quantum computation based solver of the well-known weapon target assignment problem.
  arXiv  Detail & Related papers  (2021-05-05T12:16:03Z)
• 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)
• Quantum Permutation Synchronization [88.4588059792167]
  We present QuantumSync, the quantum algorithm for solving a quantum vision problem in the context of computer vision. We show how to insert permutation constraints into a QUBO problem and to solve the constrained QUBO problem on the current generation of the abatic quantum DWave computer.
  arXiv  Detail & Related papers  (2021-01-19T17:51:02Z)
• Combinatorial optimization through variational quantum power method [0.0]
  We present a variational quantum circuit method for the power iteration. It can be used to find the eigenpairs of unitary matrices and so their associated Hamiltonians. The circuit can be simulated on the near term quantum computers with ease.
  arXiv  Detail & Related papers  (2020-07-02T10:34:16Z)

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.