An investigation of IBM Quantum Computing device performance on Combinatorial Optimisation Problems

• URL: http://arxiv.org/abs/2107.03638v3
• Date: Fri, 22 Apr 2022 14:45:41 GMT
• Title: An investigation of IBM Quantum Computing device performance on Combinatorial Optimisation Problems
• Authors: Maxine T. Khumalo, Hazel A. Chieza, Krupa Prag and Matthew Woolway
• Abstract summary: This paper juxtaposes classical and quantum optimisation algorithms' performance to solve two common COP, the Travelling Salesman Problem (TSP) and the Quadratic Assignment Problem (QAP) Two accepted classical optimisation methods, Branch and Bound (BNB) and Simulated Annealing (SA), are compared to two quantum optimisation methods, Variational Quantum Eigensolver (VQE) algorithm and Quantum Approximate optimisation Algorithm (QAOA) Our results show that the VQE performs better than QAOA for these metrics, and we infer that this is due to the increased number of operations required.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: The intractability of deterministic solutions in solving $\mathcal{NP}$-Hard Combinatorial Optimisation Problems (COP) is well reported in the literature. One mechanism for overcoming this difficulty has been the use of efficient COP non-deterministic approaches. However, with the advent of quantum technology, these modern devices' potential to overcome this tractability limitation requires exploration. This paper juxtaposes classical and quantum optimisation algorithms' performance to solve two common COP, the Travelling Salesman Problem (TSP) and the Quadratic Assignment Problem (QAP). Two accepted classical optimisation methods, Branch and Bound (BNB) and Simulated Annealing (SA), are compared to two quantum optimisation methods, Variational Quantum Eigensolver (VQE) algorithm and Quantum Approximate Optimisation Algorithm (QAOA). These algorithms are respectively executed on both classical devices and IBM's suite of Noisy Intermediate-Scale Quantum (NISQ) devices. We have encoded the COP problems for the respective technologies and algorithms and provided the computational encodings for the NISQ devices. Our experimental results show that current classical devices significantly outperform the presently available NISQ devices, which agrees and extends with findings in the literature. Further, we introduce additional performance metrics to better compare the two approaches concerning computational time, feasibility and solution quality. Our results show that the VQE performs better than QAOA for these metrics, and we infer that this is due to the increased number of operations required. Additionally, we investigate the impact of a new set of basis gates on the quantum optimisation techniques and show they yield no notable improvement in the results. Finally, we present the shortcomings of state-of-the-art NISQ IBM quantum devices and argue for potential future work and investigation.

Related papers

• Quantum Approximate Optimization: A Computational Intelligence Perspective [1.756184965281354]
  We introduce quantum computing and variational quantum algorithms (VQAs) We explain Farhi et al.'s quantum approximate optimization algorithm (Farhi's QAOA) We discuss connections of QAOA to relevant domains, such as computational learning theory and genetic algorithms.
  arXiv  Detail & Related papers  (2024-07-09T19:40:23Z)
• 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)
• Bayesian Parameterized Quantum Circuit Optimization (BPQCO): A task and hardware-dependent approach [49.89480853499917]
  Variational quantum algorithms (VQA) have emerged as a promising quantum alternative for solving optimization and machine learning problems. In this paper, we experimentally demonstrate the influence of the circuit design on the performance obtained for two classification problems. We also study the degradation of the obtained circuits in the presence of noise when simulating real quantum computers.
  arXiv  Detail & Related papers  (2024-04-17T11:00:12Z)
• Unlocking Quantum Optimization: A Use Case Study on NISQ Systems [0.0]
  This paper considers two industrial relevant use cases: one in the realm of optimizing charging schedules for electric vehicles, the other concerned with the optimization of truck routes. Our central contribution are systematic series of examples derived from these uses cases that we execute on different processors of the gate-based quantum computers of IBM as well as on the quantum annealer of D-Wave.
  arXiv  Detail & Related papers  (2024-04-10T17:08:07Z)
• Quantum Subroutine for Variance Estimation: Algorithmic Design and Applications [80.04533958880862]
  Quantum computing sets the foundation for new ways of designing algorithms. New challenges arise concerning which field quantum speedup can be achieved. Looking for the design of quantum subroutines that are more efficient than their classical counterpart poses solid pillars to new powerful quantum algorithms.
  arXiv  Detail & Related papers  (2024-02-26T09:32:07Z)
• A joint optimization approach of parameterized quantum circuits with a tensor network [0.0]
  Current intermediate-scale quantum (NISQ) devices remain limited in their capabilities. We propose the use of parameterized Networks (TNs) to attempt an improved performance of the Variational Quantum Eigensolver (VQE) algorithm.
  arXiv  Detail & Related papers  (2024-02-19T12:53:52Z)
• 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)
• Evaluation of Parameterized Quantum Circuits with Cross-Resonance Pulse-Driven Entanglers [0.27998963147546146]
  Variational Quantum Algorithms (VQAs) have emerged as a powerful class of algorithms that is highly suitable for noisy quantum devices. Previous works have shown that choosing an effective parameterized quantum circuit (PQC) or ansatz for VQAs is crucial to their overall performance. In this paper, we utilize pulse-level access to quantum machines and our understanding of their two-qubit interactions to optimize the design of two-qubit entanglers.
  arXiv  Detail & Related papers  (2022-11-01T09:46:34Z)
• 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)
• Quantum circuit architecture search for variational quantum algorithms [88.71725630554758]
  We propose a resource and runtime efficient scheme termed quantum architecture search (QAS) QAS automatically seeks a near-optimal ansatz to balance benefits and side-effects brought by adding more noisy quantum gates. We implement QAS on both the numerical simulator and real quantum hardware, via the IBM cloud, to accomplish data classification and quantum chemistry tasks.
  arXiv  Detail & Related papers  (2020-10-20T12:06: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.