Qubit-efficient quantum local search for combinatorial optimization

• URL: http://arxiv.org/abs/2502.02245v1
• Date: Tue, 04 Feb 2025 11:44:34 GMT
• Title: Qubit-efficient quantum local search for combinatorial optimization
• Authors: M. Podobrii, V. Kuzmin, V. Voloshinov, M. Veshchezerova, M. R. Perelshtein,
• Abstract summary: We present a qubit-efficient variational quantum algorithm that implements a quantum version of local search with only $lceil log l rceil$ qubits. This achievement highlights the algorithm's potential for solving large-scale optimization problems on near-term quantum devices.
• Score: 0.0
• License:
• Abstract: An essential component of many sophisticated metaheuristics for solving combinatorial optimization problems is some variation of a local search routine that iteratively searches for a better solution within a chosen set of immediate neighbors. The size $l$ of this set is limited due to the computational costs required to run the method on classical processing units. We present a qubit-efficient variational quantum algorithm that implements a quantum version of local search with only $\lceil \log_2 l \rceil$ qubits and, therefore, can potentially work with classically intractable neighborhood sizes when realized on near-term quantum computers. Increasing the amount of quantum resources employed in the algorithm allows for a larger neighborhood size, improving the quality of obtained solutions. This trade-off is crucial for present and near-term quantum devices characterized by a limited number of logical qubits. Numerically simulating our algorithm, we successfully solved the largest graph coloring instance that was tackled by a quantum method. This achievement highlights the algorithm's potential for solving large-scale combinatorial optimization problems on near-term quantum devices.

Related papers

• Quantum Subroutines in Branch-Price-and-Cut for Vehicle Routing [0.0]
  We demonstrate in this work how quantums with limited resources can be integrated in large-scale exact optimization algorithms for NP-hard problems. A key feature of our algorithm is it not only from the best solution returned by the quantum but from all solutions below a certain cost threshold.
  arXiv  Detail & Related papers  (2024-12-20T08:27:23Z)
• 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)
• Scaling Up the Quantum Divide and Conquer Algorithm for Combinatorial Optimization [0.8121127831316319]
  We propose a method for constructing quantum circuits which greatly reduces inter-device communication costs. We show that we can construct tractable circuits nearly three times the size of previous QDCA methods while retaining a similar or greater level of quality.
  arXiv  Detail & Related papers  (2024-05-01T20:49:50Z)
• 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)
• 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)
• 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)
• Parallel circuit implementation of variational quantum algorithms [0.0]
  We present a method to split quantum circuits of variational quantum algorithms (VQAs) to allow for parallel training and execution. We apply this specifically to optimization problems, where inherent structures from the problem can be identified. We show that not only can our method address larger problems, but that it is also possible to run full VQA models while training parameters using only one slice.
  arXiv  Detail & Related papers  (2023-04-06T12:52:29Z)
• 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)
• 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.