Evaluating challenges and prospects of quantum annealing in selected applications

Quantum annealers are specialized devices designed to solve optimization problems by leveraging quantum effects. In this thesis, we first investigate the capabilities of current hardware on standard real-world problem formulations, addressing the complex translation into Quadratic Unconstrained Binary Optimization (QUBO) models. It explores technical hurdles such as limited qubit counts, sparse connectivity, noise, and the heuristic nature of hardware embedding. To address identified limitations, we subsequently propose novel problem reformulations and encoding strategies. Finally, we explore hybrid quantum-classical architectures, combining both paradigms to mitigate topological and size constraints. These methodologies are validated through experiments on job shop scheduling, linear regression, and community detection benchmarks.

I quantum annealer sono dispositivi specializzati progettati per risolvere problemi di ottimizzazione sfruttando gli effetti quantistici. In questa tesi, indaghiamo innanzitutto le capacità dell'hardware attuale su formulazioni standard di problemi reali, affrontando la complessa traduzione in modelli di ottimizzazione binaria quadratica non vincolata (QUBO). Vengono esplorati ostacoli tecnici come il numero limitato di qubit, la connettività sparsa, il rumore e la natura euristica del processo di embedding. Per affrontare le limitazioni identificate, proponiamo successivamente nuove riformulazioni dei problemi e strategie di codifica. Infine, esploriamo architetture ibride quantistiche-classiche, combinando entrambi i paradigmi per mitigare i vincoli topologici e dimensionali. Queste metodologie vengono convalidate attraverso esperimenti sulla pianificazione dei job shop, sulla regressione lineare e sui benchmark di rilevamento di comunità.