Sum-of-Squares inspired Quantum Metaheuristic for Polynomial Optimization with the Hadamard Test and Approximate Amplitude Constraints

• URL: http://arxiv.org/abs/2408.07774v1
• Date: Wed, 14 Aug 2024 19:04:13 GMT
• Title: Sum-of-Squares inspired Quantum Metaheuristic for Polynomial Optimization with the Hadamard Test and Approximate Amplitude Constraints
• Authors: Iria W. Wang, Robin Brown, Taylor L. Patti, Anima Anandkumar, Marco Pavone, Susanne F. Yelin,
• Abstract summary: 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.
• Score: 76.53316706600717
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Quantum computation shows promise for addressing numerous classically intractable problems, such as optimization tasks. Many optimization problems are NP-hard, meaning that they scale exponentially with problem size and thus cannot be addressed at scale by traditional computing paradigms. The recently proposed quantum algorithm arXiv:2206.14999 addresses this challenge for some NP-hard problems, and is based on classical semidefinite programming (SDP). In this manuscript, we generalize the SDP-inspired quantum algorithm to sum-of-squares programming, which targets a broader problem set. Our proposed algorithm addresses degree-$k$ polynomial optimization problems with $N \leq 2^n$ variables (which are representative of many NP-hard problems) using $O(nk)$ qubits, $O(k)$ quantum measurements, and $O(\textrm{poly}(n))$ classical calculations. We apply the proposed algorithm to the prototypical Max-$k$SAT problem and compare its performance against classical sum-of-squares, state-of-the-art heuristic solvers, and random guessing. Simulations show that the performance of our algorithm surpasses that of classical sum-of-squares after rounding. Our results further demonstrate that our algorithm is suitable for large problems and approximates the best known classical heuristics, while also providing a more generalizable approach compared to problem-specific heuristics.

Related papers

• Moderate Exponential-time Quantum Dynamic Programming Across the Subsets for Scheduling Problems [0.20971479389679337]
  Combination of Quantum Minimum Finding and dynamic programming has proved particularly efficient in improving the complexity of NP-hard problems. In this paper, we provide a bounded-error hybrid algorithm that achieves such an improvement for a broad class of NP-hard single-machine scheduling problems. Our algorithm reduces the exponential-part complexity compared to the best-known classical algorithm, sometimes at the cost of an additional pseudo-polynomial factor.
  arXiv  Detail & Related papers  (2024-08-11T10:28:49Z)
• 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)
• Solving various NP-Hard problems using exponentially fewer qubits on a Quantum Computer [0.0]
  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.
  arXiv  Detail & Related papers  (2023-01-17T16:03:33Z)
• 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)
• Quantum Goemans-Williamson Algorithm with the Hadamard Test and Approximate Amplitude Constraints [62.72309460291971]
  We introduce a variational quantum algorithm for Goemans-Williamson algorithm that uses only $n+1$ qubits. Efficient optimization is achieved by encoding the objective matrix as a properly parameterized unitary conditioned on an auxilary qubit. We demonstrate the effectiveness of our protocol by devising an efficient quantum implementation of the Goemans-Williamson algorithm for various NP-hard problems.
  arXiv  Detail & Related papers  (2022-06-30T03:15:23Z)
• Training variational quantum algorithms is NP-hard [0.7614628596146599]
  We show that the corresponding classical optimization problems are NP-hard. Even for classically tractable systems composed of only logarithmically many qubits or free fermions, we show the optimization to be NP-hard.
  arXiv  Detail & Related papers  (2021-01-18T19:00:01Z)
• Towards Optimally Efficient Tree Search with Deep Learning [76.64632985696237]
  This paper investigates the classical integer least-squares problem which estimates signals integer from linear models. The problem is NP-hard and often arises in diverse applications such as signal processing, bioinformatics, communications and machine learning. We propose a general hyper-accelerated tree search (HATS) algorithm by employing a deep neural network to estimate the optimal estimation for the underlying simplified memory-bounded A* algorithm.
  arXiv  Detail & Related papers  (2021-01-07T08:00:02Z)
• Warm-starting quantum optimization [6.832341432995627]
  We discuss how to warm-start quantum optimization with an initial state corresponding to the solution of a relaxation of an optimization problem. This allows the quantum algorithm to inherit the performance guarantees of the classical algorithm. It is straightforward to apply the same ideas to other randomized-rounding schemes and optimization problems.
  arXiv  Detail & Related papers  (2020-09-21T18:00:09Z)
• 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.