Solving various NP-Hard problems using exponentially fewer qubits on a Quantum Computer

• URL: http://arxiv.org/abs/2301.06978v2
• Date: Fri, 12 Jan 2024 13:36:13 GMT
• Title: Solving various NP-Hard problems using exponentially fewer qubits on a Quantum Computer
• Authors: Yagnik Chatterjee, Eric Bourreau, Marko J. Ran\v{c}i\'c
• Abstract summary: NP-hard problems are not believed to be exactly solvable through general time algorithms. In this paper, we build upon a proprietary methodology which logarithmically scales with problem size. These algorithms are tested on a quantum simulator with graph sizes of over a hundred nodes and on a real quantum computer up to graph sizes of 256.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: NP-hard problems are not believed to be exactly solvable through general polynomial time algorithms. Hybrid quantum-classical algorithms to address such combinatorial problems have been of great interest in the past few years. Such algorithms are heuristic in nature and aim to obtain an approximate solution. Significant improvements in computational time and/or the ability to treat large problems are some of the principal promises of quantum computing in this regard. The hardware, however, is still in its infancy and the current Noisy Intermediate Scale Quantum (NISQ) computers are not able to optimize industrially relevant problems. Moreover, the storage of qubits and introduction of entanglement require extreme physical conditions. An issue with quantum optimization algorithms such as QAOA is that they scale linearly with problem size. In this paper, we build upon a proprietary methodology which scales logarithmically with problem size - opening an avenue for treating optimization problems of unprecedented scale on gate-based quantum computers. In order to test the performance of the algorithm, we first find a way to apply it to a handful of NP-hard problems: Maximum Cut, Minimum Partition, Maximum Clique, Maximum Weighted Independent Set. Subsequently, these algorithms are tested on a quantum simulator with graph sizes of over a hundred nodes and on a real quantum computer up to graph sizes of 256. To our knowledge, these constitute the largest realistic combinatorial optimization problems ever run on a NISQ device, overcoming previous problem sizes by almost tenfold.

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)
• Discretized Quantum Exhaustive Search for Variational Quantum Algorithms [0.0]
  Currently available quantum devices have only a limited amount of qubits and a high level of noise, limiting the size of problems that can be solved accurately with those devices. We propose a novel method that can improve variational quantum algorithms -- discretized quantum exhaustive search''
  arXiv  Detail & Related papers  (2024-07-24T22:06:05Z)
• A quantum annealing approach to the minimum distance problem of quantum codes [0.0]
  We introduce an approach to compute the minimum distance of quantum stabilizer codes by reformulating the problem as a Quadratic Unconstrained Binary Optimization problem. We demonstrate practical viability of our method by comparing the performance of purely classical algorithms with the D-Wave Advantage 4.1 quantum annealer.
  arXiv  Detail & Related papers  (2024-04-26T21:29:42Z)
• Quantum Optimization for the Maximum Cut Problem on a Superconducting Quantum Computer [0.3518016233072556]
  We investigate the performance of a hybrid quantum-classical algorithm inspired by semidefinite approaches for solving the maximum cut problem. We attain an average performance of 99% over a random ensemble of thousands of problem instances. A runtime analysis shows that the quantum solver on large-scale problems is competitive against Gurobi but short of others.
  arXiv  Detail & Related papers  (2024-04-26T17:59:22Z)
• 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)
• Complexity-Theoretic Limitations on Quantum Algorithms for Topological Data Analysis [59.545114016224254]
  Quantum algorithms for topological data analysis seem to provide an exponential advantage over the best classical approach. We show that the central task of TDA -- estimating Betti numbers -- is intractable even for quantum computers. We argue that an exponential quantum advantage can be recovered if the input data is given as a specification of simplices.
  arXiv  Detail & Related papers  (2022-09-28T17:53:25Z)
• Adiabatic Quantum Computing for Multi Object Tracking [170.8716555363907]
  Multi-Object Tracking (MOT) is most often approached in the tracking-by-detection paradigm, where object detections are associated through time. As these optimization problems are often NP-hard, they can only be solved exactly for small instances on current hardware. We show that our approach is competitive compared with state-of-the-art optimization-based approaches, even when using of-the-shelf integer programming solvers.
  arXiv  Detail & Related papers  (2022-02-17T18:59:20Z)
• Noisy intermediate-scale quantum computing algorithm for solving an $n$-vertex MaxCut problem with log($n$) qubits [0.0]
  I present a novel quantum optimization algorithm, which uses exponentially less qubits as compared to the QAOA. These results represent a 40% increase in graph size as compared to state-of-art experiments on gate-based quantum computers.
  arXiv  Detail & Related papers  (2021-10-20T21:33:41Z)
• Multiple Query Optimization using a Hybrid Approach of Classical and Quantum Computing [1.7077661158850292]
  We tackle the multiple query optimization problem (MQO) which is an important NP-hard problem in the area of data-intensive problems. We propose a novel hybrid classical-quantum algorithm to solve the MQO on a gate-based quantum computer. Our algorithm shows a qubit efficiency of close to 99% which is almost a factor of 2 higher compared to the state of the art implementation.
  arXiv  Detail & Related papers  (2021-07-22T08:12:49Z)
• 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.