Analyzing the Effectiveness of Quantum Annealing with Meta-Learning

• URL: http://arxiv.org/abs/2408.00570v1
• Date: Thu, 1 Aug 2024 14:03:11 GMT
• Title: Analyzing the Effectiveness of Quantum Annealing with Meta-Learning
• Authors: Riccardo Pellini, Maurizio Ferrari Dacrema,
• Abstract summary: We propose a new methodology to study the effectiveness of Quantum Annealing (QA) based on meta-learning models. We build a dataset composed of more than five thousand instances of ten different optimization problems. We define a set of more than a hundred features to describe their characteristics, and solve them with both QA and three classical solvers.
• Score: 7.251305766151019
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: The field of Quantum Computing has gathered significant popularity in recent years and a large number of papers have studied its effectiveness in tackling many tasks. We focus in particular on Quantum Annealing (QA), a meta-heuristic solver for Quadratic Unconstrained Binary Optimization (QUBO) problems. It is known that the effectiveness of QA is dependent on the task itself, as is the case for classical solvers, but there is not yet a clear understanding of which are the characteristics of a problem that makes it difficult to solve with QA. In this work, we propose a new methodology to study the effectiveness of QA based on meta-learning models. To do so, we first build a dataset composed of more than five thousand instances of ten different optimization problems. We define a set of more than a hundred features to describe their characteristics, and solve them with both QA and three classical solvers. We publish this dataset online for future research. Then, we train multiple meta-models to predict whether QA would solve that instance effectively and use them to probe which are the features with the strongest impact on the effectiveness of QA. Our results indicate that it is possible to accurately predict the effectiveness of QA, validating our methodology. Furthermore, we observe that the distribution of the problem coefficients representing the bias and coupling terms is very informative to identify the probability of finding good solutions, while the density of these coefficients alone is not enough. The methodology we propose allows to open new research directions to further our understanding of the effectiveness of QA, by probing specific dimensions or by developing new QUBO formulations that are better suited for the particular nature of QA. Furthermore, the proposed methodology is flexible and can be extended or used to study other quantum or classical solvers.

Related papers

• Quantum Algorithms for Drone Mission Planning [0.0]
  Mission planning often involves optimising the use of ISR (Intelligence, Surveillance and Reconnaissance) assets in order to achieve a set of mission objectives. Finding such solutions is often an NP-Hard problem and cannot be solved efficiently on classical computers. We investigate near term quantum algorithms that have the potential to offer speed-ups against current classical methods.
  arXiv  Detail & Related papers  (2024-09-27T10:58:25Z)
• Reinforcement Learning for Variational Quantum Circuits Design [10.136215038345012]
  Variational Quantum Algorithms have emerged as promising tools for solving optimization problems on quantum computers. In this study, we leverage the powerful and flexible Reinforcement Learning paradigm to train an agent capable of autonomously generating quantum circuits. Our results indicate that the $R_yz$-connected circuit achieves high approximation ratios for Maximum Cut problems.
  arXiv  Detail & Related papers  (2024-09-09T10:07:12Z)
• PO-QA: A Framework for Portfolio Optimization using Quantum Algorithms [4.2435928520499635]
  Portfolio Optimization (PO) is a financial problem aiming to maximize the net gains while minimizing the risks in a given investment portfolio. We propose a novel scalable framework, denoted PO-QA, to investigate the variation of quantum parameters. Our results provide effective insights into comprehending PO from the lens of Quantum Machine Learning.
  arXiv  Detail & Related papers  (2024-07-29T10:26:28Z)
• Solving Combinatorial Optimization Problems with a Block Encoding Quantum Optimizer [0.0]
  Block ENcoding Quantum (BEQO) is a hybrid quantum solver that uses block encoding to represent the cost function. Our findings confirm that BENQO performs significantly better than QAOA and competes with VQE across a variety of performance metrics.
  arXiv  Detail & Related papers  (2024-04-22T10:10:29Z)
• Unifying (Quantum) Statistical and Parametrized (Quantum) Algorithms [65.268245109828]
  We take inspiration from Kearns' SQ oracle and Valiant's weak evaluation oracle. We introduce an extensive yet intuitive framework that yields unconditional lower bounds for learning from evaluation queries.
  arXiv  Detail & Related papers  (2023-10-26T18:23:21Z)
• Probabilistic Sampling of Balanced K-Means using Adiabatic Quantum Computing [93.83016310295804]
  AQCs allow to implement problems of research interest, which has sparked the development of quantum representations for computer vision tasks. In this work, we explore the potential of using this information for probabilistic balanced k-means clustering. Instead of discarding non-optimal solutions, we propose to use them to compute calibrated posterior probabilities with little additional compute cost. This allows us to identify ambiguous solutions and data points, which we demonstrate on a D-Wave AQC on synthetic tasks and real visual data.
  arXiv  Detail & Related papers  (2023-10-18T17:59:45Z)
• Problem-Dependent Power of Quantum Neural Networks on Multi-Class Classification [83.20479832949069]
  Quantum neural networks (QNNs) have become an important tool for understanding the physical world, but their advantages and limitations are not fully understood. Here we investigate the problem-dependent power of QCs on multi-class classification tasks. Our work sheds light on the problem-dependent power of QNNs and offers a practical tool for evaluating their potential merit.
  arXiv  Detail & Related papers  (2022-12-29T10:46:40Z)
• 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)
• Quantum circuit architecture search on a superconducting processor [56.04169357427682]
  Variational quantum algorithms (VQAs) have shown strong evidences to gain provable computational advantages for diverse fields such as finance, machine learning, and chemistry. However, the ansatz exploited in modern VQAs is incapable of balancing the tradeoff between expressivity and trainability. We demonstrate the first proof-of-principle experiment of applying an efficient automatic ansatz design technique to enhance VQAs on an 8-qubit superconducting quantum processor.
  arXiv  Detail & Related papers  (2022-01-04T01:53:42Z)
• A Query-based Quantum Eigensolver [8.136660631939154]
  We present an alternative type of quantum method that uses fixed-point quantum search to solve Type II eigenvalue problems. In addition, compared with the QPE method, our query-based method achieves a quadratic speedup in solving Type II problems.
  arXiv  Detail & Related papers  (2020-08-03T00:29:19Z)
• Harvesting and Refining Question-Answer Pairs for Unsupervised QA [95.9105154311491]
  We introduce two approaches to improve unsupervised Question Answering (QA) First, we harvest lexically and syntactically divergent questions from Wikipedia to automatically construct a corpus of question-answer pairs (named as RefQA) Second, we take advantage of the QA model to extract more appropriate answers, which iteratively refines data over RefQA.
  arXiv  Detail & Related papers  (2020-05-06T15:56:06Z)

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.