Thermal Quantum Annealing (tQuA) is a quantum architecture in which a system coupled non-adiabatically to a thermodynamic reservoir evolves toward the ground state of a target Hamiltonian . This paper provides a rigorous and honest foundation for tQuA and its extension to Quantum Intelligent Matrix Methods (QIMM). We distinguish carefully among Theorems (proved in cited literature), Propositions (proof sketches with explicitly identified gaps), and Conjectures (claims with open steps). This work delivers three principal contributions: Convergence Proof Chain: We present a five-pillar proof chain establishing that tQuA converges to the global minimum from any initial state, without adiabatic scheduling, without eigenstate knowledge, and with a strictly positive escape rate from every local minimum at any . Honest Scaling Benchmarks: We present scaling benchmarks for the Liouvillian spectral gap on gopherhole Hamiltonians, reporting a key finding: fixed-schedule tQuA achieves a perfectly flat gap (, independent of up to ) when the number of local minima is fixed and small, but experiences steep polynomial decay () when grows proportionally to . Adaptive Policy Framework: Third, we outline a rich adaptive annealing policy framework using observed function evaluations and prior probability distributions over problem classes, framing it as a primary research direction for future empirical tuning. The framework applies broadly to nonconvex optimization in artificial intelligence, signal processing, and imaging, with specific application to "seeing the sky" technologies described in the companion paper on intensity-correlation interferometry (Hyland & Werbos 2024).
Thermal Quantum Annealing (tQuA) is a quantum architecture in which a system coupled non-adiabatically to a thermodynamic reservoir evolves toward the ground state of a target Hamiltonian . This paper provides a rigorous and honest foundation for tQuA and its extension to Quantum Intelligent Matrix Methods (QIMM). We distinguish carefully among Theorems (proved in cited literature), Propositions (proof sketches with explicitly identified gaps), and Conjectures (claims with open steps). This work delivers three principal contributions: Convergence Proof Chain: We present a five-pillar proof chain establishing that tQuA converges to the global minimum from any initial state, without adiabatic scheduling, without eigenstate knowledge, and with a strictly positive escape rate from every local minimum at any . Honest Scaling Benchmarks: We present scaling benchmarks for the Liouvillian spectral gap on gopherhole Hamiltonians, reporting a key finding: fixed-schedule tQuA achieves a perfectly flat gap (, independent of up to ) when the number of local minima is fixed and small, but experiences steep polynomial decay () when grows proportionally to . Adaptive Policy Framework: Third, we outline a rich adaptive annealing policy framework using observed function evaluations and prior probability distributions over problem classes, framing it as a primary research direction for future empirical tuning. The framework applies broadly to nonconvex optimization in artificial intelligence, signal processing, and imaging, with specific application to "seeing the sky" technologies described in the companion paper on intensity-correlation interferometry (Hyland & Werbos 2024).
Previous work on Thermal Quantum Annealing (tQuA) established a natural-bath architecture with strong numerical evidence for favorable scaling, but a fully rigorous proof of logarithmic mixing time remained elusive, with key results labeled as conjectures. This paper resolves that open problem by introducing Engineered Dissipation tQuA (ED-tQuA), a new quantum optimization architecture that replaces the passive thermal bath with programmable, non-local jump operators. We prove three rigorous theorems with complete, self-contained proofs: (1) a logarithmic lower bound on the Liouvillian spectral gap, , establishing a mixing time of ; (2) monotonic energy decrease and guaranteed convergence to the global minimum via dark-state engineering; and (3) robustness of the performance guarantees to bounded control errors. No conjectures are required. The design encompasses a broad family of architectures, including all-to-all, restricted connectivity graphs, and various cooling schedules, all of which inherit the same provable guarantees. This work provides the first complete mathematical foundation for a provably fast, open-system quantum optimizer, directly enabling stronger patent claims and a clear path to near-term hardware demonstration.
Quantum annealing has emerged as a transformative approach in solving combinatorial optimization problems by leveraging the principles of quantum mechanics. A comprehensive survey of quantum annealing is presented, delineating its foundational concepts, state-of-the-art advancements, and diverse applications across domains such as logistics, finance, machine learning, and energy optimization. Notable contributions include the introduction of a systematic benchmarking framework to evaluate quantum annealing against classical optimization techniques across metrics like time-to-target, scalability, and energy efficiency. Additionally, novel hybrid quantum-classical paradigms and hardware advancements are explored, addressing challenges in qubit connectivity, coherence, and noise resilience. Optimization problems are mapped to suitable quantum annealing platforms, offering practical guidelines for leveraging quantum technologies in real-world scenarios. Critical gaps in scalability and integration with machine learning are identified, with future research directions proposed to bridge these challenges. These findings provide a holistic understanding of quantum annealing's potential, offering a foundational resource for advancing quantum computing in optimization.
We establish and discuss a number of connections between a digitized version of Quantum Annealing (QA) with the Quantum Approximate Optimization Algorithm (QAOA) introduced by Farhi et al. (arXiv:1411.4028) as an alternative hybrid quantum-classical variational scheme for quantum-state preparation and optimization. We introduce a technique that allows to prove, for instance, a rigorous bound concerning the performance of QAOA for MaxCut on a 2-regular graph, equivalent to an unfrustrated antiferromagnetic Ising chain. The bound shows that the optimal variational error of a depth-P quantum circuit has to satisfy εPres≥(2P+2)−1. In a separate work (Mbeng et al., arXiv:1911.12259) we have explicitly shown, exploiting a Jordan-Wigner transformation, that among the 2P degenerate variational minima which can be found for this problem, all strictly satisfying the equality εPres=(2P+2)−1, one can construct a special {\em regular} optimal solution, which is computationally optimal and does not require any prior knowledge about the spectral gap. We explicitly demonstrate here that such a schedule is adiabatic, in a digitized sense, and can therefore be interpreted as an optimized digitized-QA protocol. We also discuss and compare our bound on the residual energy to well-known results on the Kibble-Zurek mechanism behind a continuous-time QA. These findings help elucidating the intimate relation between digitized-QA, QAOA, and optimal Quantum Control.
This paper presents an adaptive quantum annealing algorithm designed to improve the performance of quantum annealing in solving combinatorial optimization problems. Traditional quantum annealing relies on a fixed annealing schedule, which may not be optimal for all problems. This work introduces a novel approach that utilizes reinforcement learning to dynamically adjust the annealing parameters during the annealing process, based on the observed progress towards a solution. The algorithm learns an optimal annealing schedule by interacting with the quantum annealing system, maximizing the probability of finding a good solution within a given time limit. We demonstrate the theoretical framework and outline the core components of the adaptive algorithm, highlighting its potential advantages over conventional fixed-schedule quantum annealing. The key performance metric is the solution quality (e.g., objective function value) achieved after annealing. The algorithm's effectiveness is evaluated through conceptual analysis and design considerations. This approach aims to bridge the gap between the theoretical potential of quantum annealing and its practical application in solving real-world combinatorial optimization challenges.
Finding the global minimum in a rugged potential landscape is a computationally hard task, often equivalent to relevant optimization problems. Annealing strategies, either classical or quantum, explore the configuration space by evolving the system under the influence of thermal or quantum fluctuations. The thermal annealing dynamics can rapidly freeze the system into a low-energy configuration, and it can be simulated well on a classical computer, but it easily gets stuck in local minima. Quantum annealing, on the other hand, can be guaranteed to find the true ground state and can be implemented in modern quantum simulators; however, quantum adiabatic schemes become prohibitively slow in the presence of quasidegeneracies. Here, we propose a strategy which combines ideas from simulated annealing and quantum annealing. In such a hybrid algorithm, the outcome of a quantum simulator is processed on a classical device. While the quantum simulator explores the configuration space by repeatedly applying quantum fluctuations and performing projective measurements, the classical computer evaluates each configuration and enforces a lowering of the energy. We have simulated this algorithm for small instances of the random energy model, showing that it potentially outperforms both simulated thermal annealing and adiabatic quantum annealing. It becomes most efficient for problems involving many quasidegenerate ground states.
Abstract Quantum annealing solves combinatorial optimization problems by finding the energetic ground states of an embedded Hamiltonian. However, quantum annealing dynamics under the embedded Hamiltonian may violate the principles of adiabatic evolution and generate excitations that correspond to errors in the computed solution. Here we empirically benchmark the probability of chain breaks and identify sweet spots for solving a suite of embedded Hamiltonians. We further correlate the physical location of chain breaks in the quantum annealing hardware with the underlying embedding technique and use these localized rates in a tailored post-processing strategies. Our results demonstrate how to use characterization of the quantum annealing hardware to tune the embedded Hamiltonian and remove computational errors.