Solving non-native combinatorial optimization problems using hybrid quantum-classical algorithms

• URL: http://arxiv.org/abs/2403.03153v1
• Date: Tue, 5 Mar 2024 17:46:04 GMT
• Title: Solving non-native combinatorial optimization problems using hybrid quantum-classical algorithms
• Authors: Jonathan Wurtz, Stefan Sack, Sheng-Tao Wang
• Abstract summary: 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.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Combinatorial optimization is a challenging problem applicable in a wide range of fields from logistics to finance. Recently, quantum computing has been used to attempt to solve these problems using a range of algorithms, including parameterized quantum circuits, adiabatic protocols, and quantum annealing. These solutions typically have several challenges: 1) there is little to no performance gain over classical methods, 2) not all constraints and objectives may be efficiently encoded in the quantum ansatz, and 3) the solution domain of the objective function may not be the same as the bit strings of measurement outcomes. This work presents "non-native hybrid algorithms" (NNHA): a framework to overcome these challenges by integrating quantum and classical resources with a hybrid approach. By designing non-native quantum variational ansatzes that inherit some but not all problem structure, measurement outcomes from the quantum computer can act as a resource to be used by classical routines to indirectly compute optimal solutions, partially overcoming the challenges of contemporary quantum optimization approaches. These methods are demonstrated using a publicly available neutral-atom quantum computer on two simple problems of Max $k$-Cut and maximum independent set. We find improvements in solution quality when comparing the hybrid algorithm to its ``no quantum" version, a demonstration of a "comparative advantage".

Related papers

• Benchmarking Variational Quantum Algorithms for Combinatorial Optimization in Practice [0.0]
  Variational quantum algorithms and, in particular, variants of the varational quantum eigensolver have been proposed to address optimization (CO) problems. We numerically investigate what this scaling result means in practice for solving CO problems using Max-Cut as a benchmark.
  arXiv  Detail & Related papers  (2024-08-06T09:57:34Z)
• Quantum Subroutine for Variance Estimation: Algorithmic Design and Applications [80.04533958880862]
  Quantum computing sets the foundation for new ways of designing algorithms. New challenges arise concerning which field quantum speedup can be achieved. Looking for the design of quantum subroutines that are more efficient than their classical counterpart poses solid pillars to new powerful quantum algorithms.
  arXiv  Detail & Related papers  (2024-02-26T09:32:07Z)
• Quantum algorithms: A survey of applications and end-to-end complexities [90.05272647148196]
  The anticipated applications of quantum computers span across science and industry. We present a survey of several potential application areas of quantum algorithms. We outline the challenges and opportunities in each area in an "end-to-end" fashion.
  arXiv  Detail & Related papers  (2023-10-04T17:53:55Z)
• Iterative Quantum Algorithms for Maximum Independent Set: A Tale of Low-Depth Quantum Algorithms [0.0]
  We study a new class of hybrid approaches to quantum optimization, termed Iterative Maximum Quantum Algorithms. We show that for QAOA with depth $p=1$, this algorithm performs exactly the same operations and selections as the classical greedy algorithm for MIS.
  arXiv  Detail & Related papers  (2023-09-22T18:00:03Z)
• Quantum-Informed Recursive Optimization Algorithms [0.0]
  We propose and implement a family of quantum-informed recursive optimization (QIRO) algorithms for optimization problems. Our approach leverages quantum resources to obtain information that is used in problem-specific classical reduction steps. We use backtracking techniques to further improve the performance of the algorithm without increasing the requirements on the quantum hardware.
  arXiv  Detail & Related papers  (2023-08-25T18:02:06Z)
• Quantum Annealing for Single Image Super-Resolution [86.69338893753886]
  We propose a quantum computing-based algorithm to solve the single image super-resolution (SISR) problem. The proposed AQC-based algorithm is demonstrated to achieve improved speed-up over a classical analog while maintaining comparable SISR accuracy.
  arXiv  Detail & Related papers  (2023-04-18T11:57:15Z)
• 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)
• Classically-Boosted Quantum Optimization Algorithm [0.0]
  We explore a natural approach to leveraging existing classical techniques to enhance quantum optimization. Specifically, we run a classical algorithm to find an approximate solution and then use a quantum circuit to search its "neighborhood" for higher-quality solutions. We demonstrate the applications of CBQOA to Max 3SAT and Max Bisection, and provide empirical evidence that it outperforms previous approaches on these problems.
  arXiv  Detail & Related papers  (2022-03-25T23:36:14Z)
• 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)
• Solving Quadratic Unconstrained Binary Optimization with divide-and-conquer and quantum algorithms [0.0]
  We apply the divide-and-conquer approach to reduce the original problem to a collection of smaller problems. This technique can be applied to any QUBO instance and leads to either an all-classical or a hybrid quantum-classical approach.
  arXiv  Detail & Related papers  (2021-01-19T19:00:40Z)
• 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.