Adiabatic Quantum Optimization Fails to Solve the Knapsack Problem

• URL: http://arxiv.org/abs/2008.07456v1
• Date: Mon, 17 Aug 2020 16:29:34 GMT
• Title: Adiabatic Quantum Optimization Fails to Solve the Knapsack Problem
• Authors: Lauren Pusey-Nazzaro, Prasanna Date
• Abstract summary: We use the D-Wave 2000Q adiabatic quantum computer to solve the integer-weight knapsack problem. We find that adiabatic quantum optimization fails to produce solutions corresponding to optimal filling of the knapsack.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In this work, we attempt to solve the integer-weight knapsack problem using the D-Wave 2000Q adiabatic quantum computer. The knapsack problem is a well-known NP-complete problem in computer science, with applications in economics, business, finance, etc. We attempt to solve a number of small knapsack problems whose optimal solutions are known; we find that adiabatic quantum optimization fails to produce solutions corresponding to optimal filling of the knapsack in all problem instances. We compare results obtained on the quantum hardware to the classical simulated annealing algorithm and two solvers employing a hybrid branch-and-bound algorithm. The simulated annealing algorithm also fails to produce the optimal filling of the knapsack, though solutions obtained by simulated and quantum annealing are no more similar to each other than to the correct solution. We discuss potential causes for this observed failure of adiabatic quantum optimization.

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)
• Solving non-native combinatorial optimization problems using hybrid quantum-classical algorithms [0.0]
  Combinatorial optimization is a challenging problem applicable in a wide range of fields from logistics to finance. Quantum computing has been used to attempt to solve these problems using a range of algorithms. This work presents a framework to overcome these challenges by integrating quantum and classical resources with a hybrid approach.
  arXiv  Detail & Related papers  (2024-03-05T17:46:04Z)
• Assessing Quantum Computing Performance for Energy Optimization in a Prosumer Community [1.072460284847973]
  "Prosumer problem" is the problem of scheduling the household loads on the basis of the user needs, the electricity prices, and the availability of local renewable energy. Quantum computers can offer a significant breakthrough in treating this problem thanks to the intrinsic parallel nature of quantum operations. We report on an extensive set of experiments, on simulators and real quantum hardware, for different problem sizes.
  arXiv  Detail & Related papers  (2023-11-17T15:48:51Z)
• Hybrid classical-quantum branch-and-bound algorithm for solving integer linear problems [0.0]
  Quantum annealers are suited to solve several logistic optimization problems expressed in the QUBO formulation. The solutions proposed by the quantum annealers are generally not optimal, as thermal noise and other disturbing effects arise when the number of qubits involved in the calculation is too large. We propose the use of the classical branch-and-bound algorithm, that divides the problem into sub-problems which are described by a lower number of qubits.
  arXiv  Detail & Related papers  (2023-11-16T09:19:01Z)
• 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)
• 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)
• 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)
• A Hybrid Quantum-Classical Algorithm for Robust Fitting [47.42391857319388]
  We propose a hybrid quantum-classical algorithm for robust fitting. Our core contribution is a novel robust fitting formulation that solves a sequence of integer programs. We present results obtained using an actual quantum computer.
  arXiv  Detail & Related papers  (2022-01-25T05:59:24Z)
• 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)
• 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)
• 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.