An in-principle super-polynomial quantum advantage for approximating
combinatorial optimization problems via computational learning theory
- URL: http://arxiv.org/abs/2212.08678v4
- Date: Tue, 13 Feb 2024 10:40:31 GMT
- Title: An in-principle super-polynomial quantum advantage for approximating
combinatorial optimization problems via computational learning theory
- Authors: Niklas Pirnay, Vincent Ulitzsch, Frederik Wilde, Jens Eisert,
Jean-Pierre Seifert
- Abstract summary: We prove that quantum computers feature an in-principle super-polynomial advantage over classical computers in approximating solutions to optimization problems.
The core of the quantum advantage is ultimately borrowed from Shor's quantum algorithm for factoring.
- Score: 5.907281242647458
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Combinatorial optimization - a field of research addressing problems that
feature strongly in a wealth of scientific and industrial contexts - has been
identified as one of the core potential fields of applicability of quantum
computers. It is still unclear, however, to what extent quantum algorithms can
actually outperform classical algorithms for this type of problems. In this
work, by resorting to computational learning theory and cryptographic notions,
we prove that quantum computers feature an in-principle super-polynomial
advantage over classical computers in approximating solutions to combinatorial
optimization problems. Specifically, building on seminal work by Kearns and
Valiant and introducing a new reduction, we identify special types of problems
that are hard for classical computers to approximate up to polynomial factors.
At the same time, we give a quantum algorithm that can efficiently approximate
the optimal solution within a polynomial factor. The core of the quantum
advantage discovered in this work is ultimately borrowed from Shor's quantum
algorithm for factoring. Concretely, we prove a super-polynomial advantage for
approximating special instances of the so-called integer programming problem.
In doing so, we provide an explicit end-to-end construction for advantage
bearing instances. This result shows that quantum devices have, in principle,
the power to approximate combinatorial optimization solutions beyond the reach
of classical efficient algorithms. Our results also give clear guidance on how
to construct such advantage-bearing problem instances.
Related papers
- Variational Quantum Algorithms for Combinatorial Optimization [0.571097144710995]
Variational Algorithms (VQA) have emerged as one of the strongest candidates towards reaching practical applicability of NISQ systems.
This paper explores the current state and recent developments of VQAs, emphasizing their applicability to Approximate optimization.
We implement QAOA circuits with varying depths to solve the MaxCut problem on graphs with 10 and 20 nodes.
arXiv Detail & Related papers (2024-07-08T22:02:39Z) - Towards Quantum Computational Mechanics [1.7201069233638664]
We show how quantum computing can be used to solve representative volume element (RVE) problems in computational homogenisation.
Our quantum RVE solver attains exponential acceleration with respect to classical solvers.
arXiv Detail & Related papers (2023-12-06T12:53:02Z) - Quantum Optimization: Potential, Challenges, and the Path Forward [14.836100818054588]
Recent advances in quantum computers are demonstrating the ability to solve problems at a scale beyond brute force classical simulation.
Widespread interest in quantum algorithms has developed in many areas, with optimization being one of the most pronounced domains.
arXiv Detail & Related papers (2023-12-04T19:00:44Z) - 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) - 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) - Quantum-inspired optimization for wavelength assignment [51.55491037321065]
We propose and develop a quantum-inspired algorithm for solving the wavelength assignment problem.
Our results pave the way to the use of quantum-inspired algorithms for practical problems in telecommunications.
arXiv Detail & Related papers (2022-11-01T07:52:47Z) - Entanglement and coherence in Bernstein-Vazirani algorithm [58.720142291102135]
Bernstein-Vazirani algorithm allows one to determine a bit string encoded into an oracle.
We analyze in detail the quantum resources in the Bernstein-Vazirani algorithm.
We show that in the absence of entanglement, the performance of the algorithm is directly related to the amount of quantum coherence in the initial state.
arXiv Detail & Related papers (2022-05-26T20:32:36Z) - A quantum-inspired tensor network method for constrained combinatorial
optimization problems [5.904219009974901]
We propose a quantum-inspired tensor-network-based algorithm for general locally constrained optimization problems.
Our algorithm constructs a Hamiltonian for the problem of interest, effectively mapping it to a quantum problem.
Our results show the effectiveness of this construction and potential applications.
arXiv Detail & Related papers (2022-03-29T05:44:07Z) - Quantum computational advantage implies contextuality [0.0]
We show that a separation between the class of all problems that can efficiently be solved on a quantum computer and those using classical algorithms implies the time generalized contextuality of quantum algorithms.
Our result subsumes versions of Gottesman-Knill theorem as special cases.
arXiv Detail & Related papers (2021-11-30T19:00:02Z) - Polynomial unconstrained binary optimisation inspired by optical
simulation [52.11703556419582]
We propose an algorithm inspired by optical coherent Ising machines to solve the problem of unconstrained binary optimization.
We benchmark the proposed algorithm against existing PUBO algorithms, and observe its superior performance.
The application of our algorithm to protein folding and quantum chemistry problems sheds light on the shortcomings of approxing the electronic structure problem by a PUBO problem.
arXiv Detail & Related papers (2021-06-24T16:39:31Z)
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.