Test Case Minimization with Quantum Annealers

• URL: http://arxiv.org/abs/2308.05505v1
• Date: Thu, 10 Aug 2023 11:31:53 GMT
• Title: Test Case Minimization with Quantum Annealers
• Authors: Xinyi Wang (1), Asmar Muqeet (1), Tao Yue (1), Shaukat Ali (1 and 2), Paolo Arcaini (3) ((1) Simula Research Laboratory Oslo Norway, (2) Oslo Metropolitan University Oslo Norway, (3) National Institute of Informatics Tokyo Japan)
• Abstract summary: Theoretically, quantum annealers can outperform classical computers. Small-scale, i.e., they have limited quantum bits (qubits) We propose BootQA, the very first effort at solving the test case (TCM) problem with QA.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Quantum annealers are specialized quantum computers for solving combinatorial optimization problems using special characteristics of quantum computing (QC), such as superposition, entanglement, and quantum tunneling. Theoretically, quantum annealers can outperform classical computers. However, the currently available quantum annealers are small-scale, i.e., they have limited quantum bits (qubits); hence, they currently cannot demonstrate the quantum advantage. Nonetheless, research is warranted to develop novel mechanisms to formulate combinatorial optimization problems for quantum annealing (QA). However, solving combinatorial problems with QA in software engineering remains unexplored. Toward this end, we propose BootQA, the very first effort at solving the test case minimization (TCM) problem with QA. In BootQA, we provide a novel formulation of TCM for QA, followed by devising a mechanism to incorporate bootstrap sampling to QA to optimize the use of qubits. We also implemented our TCM formulation in three other optimization processes: classical simulated annealing (SA), QA without problem decomposition, and QA with an existing D-Wave problem decomposition strategy, and conducted an empirical evaluation with three real-world TCM datasets. Results show that BootQA outperforms QA without problem decomposition and QA with the existing decomposition strategy in terms of effectiveness. Moreover, BootQA's effectiveness is similar to SA. Finally, BootQA has higher efficiency in terms of time when solving large TCM problems than the other three optimization processes.

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)
• Benchmarking Quantum Annealers with Near-Optimal Minor-Embedded Instances [0.0]
  This paper establishes a new protocol to generate graph instances with their associated near-optimal minor-embedding mappings to D-Wave Quantum Annealers. We use this method to benchmark QA on large instances of unconstrained and constrained optimization problems and compare the performance of the QPU with efficient classical solvers.
  arXiv  Detail & Related papers  (2024-05-02T15:19:39Z)
• 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)
• Variational quantum eigensolver with linear depth problem-inspired ansatz for solving portfolio optimization in finance [7.501820750179541]
  This paper introduces the variational quantum eigensolver (VQE) to solve portfolio optimization problems in finance. We implement the HDC experiments on the superconducting quantum computer Wu Kong with up to 55 qubits. The HDC scheme shows great potential for achieving quantum advantage in the NISQ era.
  arXiv  Detail & Related papers  (2024-03-07T07:45:47Z)
• 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)
• Optimal Stochastic Resource Allocation for Distributed Quantum Computing [50.809738453571015]
  We propose a resource allocation scheme for distributed quantum computing (DQC) based on programming to minimize the total deployment cost for quantum resources. The evaluation demonstrates the effectiveness and ability of the proposed scheme to balance the utilization of quantum computers and on-demand quantum computers.
  arXiv  Detail & Related papers  (2022-09-16T02:37:32Z)
• 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)
• Adiabatic Quantum Graph Matching with Permutation Matrix Constraints [75.88678895180189]
  Matching problems on 3D shapes and images are frequently formulated as quadratic assignment problems (QAPs) with permutation matrix constraints, which are NP-hard. We propose several reformulations of QAPs as unconstrained problems suitable for efficient execution on quantum hardware. The proposed algorithm has the potential to scale to higher dimensions on future quantum computing architectures.
  arXiv  Detail & Related papers  (2021-07-08T17:59:55Z)
• 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.