Classically-Boosted Quantum Optimization Algorithm

• URL: http://arxiv.org/abs/2203.13936v1
• Date: Fri, 25 Mar 2022 23:36:14 GMT
• Title: Classically-Boosted Quantum Optimization Algorithm
• Authors: Guoming Wang
• Abstract summary: 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.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Considerable effort has been made recently in the development of heuristic quantum algorithms for solving combinatorial optimization problems. Meanwhile, these problems have been studied extensively in classical computing for decades. In this paper, 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 propose the Classically-Boosted Quantum Optimization Algorithm (CBQOA) that is based on this idea and can solve a wide range of combinatorial optimization problems, including all unconstrained problems and many important constrained problems such as Max Bisection, Maximum Independent Set, Minimum Vertex Cover, Portfolio Optimization, Traveling Salesperson and so on. A crucial component of this algorithm is an efficiently-implementable continuous-time quantum walk (CTQW) on a properly-constructed graph that connects the feasible solutions. CBQOA utilizes this CTQW and the output of an efficient classical procedure to create a suitable superposition of the feasible solutions which is then processed in certain way. This algorithm has the merits that it solves constrained problems without modifying their cost functions, confines the evolution of the quantum state to the feasible subspace, and does not rely on efficient indexing of the feasible 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.

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)
• 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)
• 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)
• 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)
• A Review on Quantum Approximate Optimization Algorithm and its Variants [47.89542334125886]
  The Quantum Approximate Optimization Algorithm (QAOA) is a highly promising variational quantum algorithm that aims to solve intractable optimization problems. This comprehensive review offers an overview of the current state of QAOA, encompassing its performance analysis in diverse scenarios. We conduct a comparative study of selected QAOA extensions and variants, while exploring future prospects and directions for the algorithm.
  arXiv  Detail & Related papers  (2023-06-15T15:28:12Z)
• 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)
• Prog-QAOA: Framework for resource-efficient quantum optimization through classical programs [0.0]
  Current quantum optimization algorithms require representing the original problem as a binary optimization problem, which is then converted into an equivalent Ising model suitable for the quantum device. We propose to design classical programs for computing the objective function and certifying the constraints, and later compile them to quantum circuits. This results in a new variant of the Quantum Approximate Optimization Algorithm (QAOA), which we name the Prog-QAOA.
  arXiv  Detail & Related papers  (2022-09-07T18:01:01Z)
• 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)
• 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)
• Cross Entropy Hyperparameter Optimization for Constrained Problem Hamiltonians Applied to QAOA [68.11912614360878]
  Hybrid quantum-classical algorithms such as Quantum Approximate Optimization Algorithm (QAOA) are considered as one of the most encouraging approaches for taking advantage of near-term quantum computers in practical applications. Such algorithms are usually implemented in a variational form, combining a classical optimization method with a quantum machine to find good solutions to an optimization problem. In this study we apply a Cross-Entropy method to shape this landscape, which allows the classical parameter to find better parameters more easily and hence results in an improved performance.
  arXiv  Detail & Related papers  (2020-03-11T13:52:41Z)

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.