Multi-tasking through quantum annealing

Abstract

Quantum annealing approximately solves combinatorial optimization problems by leveraging the principles of adiabatic quantum systems. In this approach, the system's Hamiltonian evolves from an initial general state to a problem-specific state. This study introduces multi-tasking quantum annealing (MTQA), a method that enables the parallel processing of multiple optimization problems by embedding them into spatially distinct regions on quantum hardware. MTQA is evaluated using two NP-hard problems: the minimum vertex cover problem (MVCP) and the graph partitioning problem (GPP). This parallel approach optimizes quantum resource utilization by concurrently utilizing idle qubits. The findings demonstrate that MTQA achieves a solution quality comparable to single-problem quantum annealing and classical simulated annealing (SA), while notably reducing the time-to-solution (TTS) metrics. Eigenspectrum analysis further theoretically supports the hypothesis that parallel embedding preserves quantum coherence and does not increase computational complexity by efficiently utilizing available quantum hardware (e.g., qubits and couplers). MTQA enables efficient multitasking in quantum annealing, optimizing hardware utilization and improving throughput for concurrent tasks and demonstrating performance for problems up to 100 nodes in real-world applications.

16 pages, 9 figures. Corresponding author: Jun-ichi Shirakashi

References in corpus (18)

• Array Programming with NumPy
• Ising formulations of many NP problems
• Quantum Annealing in the Transverse Ising Model
• Adiabatic Quantum Computing
• Quantum annealing with more than one hundred qubits
• Perspectives of quantum annealing: Methods and implementations
• Mathematical Foundation of Quantum Annealing
• Experimental investigation of performance differences between Coherent Ising Machines and a quantum annealer
• Experimental signature of programmable quantum annealing
• Nonadiabatic Landau-Zener-Stückelberg-Majorana transitions, dynamics, and interference
• Digitized-counterdiabatic quantum approximate optimization algorithm
• Quantum Annealing Correction with Minor Embedding
• A Compound Josephson Junction Coupler for Flux Qubits With Minimal Crosstalk
• Programmable Quantum Annealers as Noisy Gibbs Samplers
• Variational optimization of the quantum annealing schedule for the Lechner-Hauke-Zoller scheme
• Solving Larger Maximum Clique Problems Using Parallel Quantum Annealing
• Using Quantum Annealers to Calculate Ground State Properties of Molecules
• Performance enhancement of quantum annealing under the Lechner-Hauke-Zoller scheme by non-linear driving of the constraint term