Modernizing Quantum Annealing II: Genetic algorithms with the Inference Primitive Formalism
arXiv:1609.05875 · doi:10.1007/s11047-022-09905-2
Abstract
Quantum annealing allows for quantum fluctuations to be used used to assist in finding the solution to some of the worlds most challenging computational problems. Recently, this field has attracted much interest because of the construction of large-scale flux-qubit based quantum annealing devices. There has been recent work on [Chancellor NJP 19(2):023024, 2017] how the control protocols of these devices can be modified so that individual annealer calls on real devices can take initial conditions. Development is being undertaken to implement such protocols in the quantum annealing devices designed by D-Wave Systems Inc. and these features will be available to customers soon. In this paper, I develop a formalism for algorithmic design in quantum annealers, which I call the `inference primitive' formalism. This formalism allows for a natural description of calls to quantum annealers with a general control structure. This more generalized control structure includes not only the ability to include initial conditions in an annealer run, but also to control the annealing schedules of qubits or clusters of qubits independently, thereby representing relative certainty values of different parts of a candidate solution. I discuss the compatability of such controls with a wide variety of other current efforts to improve the performance of annealers, such as non-stoquatic drivers, synchronizing freeze times for the qubits, and belief propagation techniques. To demonstrate the power of the formalism I present here, I discuss how this new formalism can be used to represent annealer implementations of genetic algorithms, and can represent the addition of genetic components to currently used algorithms. The new tools I develop will allow a more complete understanding of the algorithmic space available to quantum annealers, and thereby make the field more competitive.
arXiv comment13 pages, 7 figures Bibtex bug which prevented arXiv numbers from showing up in references rectified in v2, major rewrite for clarity and numerical results added in v3, addition of reference to previous work with closed systems and minor changes in v4, revised to focus more on formalism in v5, title changed in v5, formerly Modernizing Quantum Annealing II: Genetic algorithm and inference
References in corpus (20)
- Quantum Annealing in the Transverse Ising Model
- Adiabatic Quantum Computing
- Parallel Tempering: Theory, Applications, and New Perspectives
- Quantum Annealing: A New Method for Minimizing Multidimensional Functions
- Estimation of effective temperatures in quantum annealers for sampling applications: A case study with possible applications in deep learning
- Application of Quantum Annealing to Training of Deep Neural Networks
- Modernizing Quantum Annealing using Local Searches
- Population Annealing with Weighted Averages: A Monte Carlo Method for Rough Free Energy Landscapes
- Population annealing: Theory and application in spin glasses
- A Direct Mapping of Max k-SAT and High Order Parity Checks to a Chimera Graph
- Global warming: Temperature estimation in annealers
- Quantum annealing with longitudinal bias fields
- Effective optimization using sample persistence: A case study on quantum annealers and various Monte Carlo optimization methods
- Adiabatic optimization versus diffusion Monte Carlo
- Scalable Superconducting Architecture for Adiabatic Quantum Computation
- Optimization of population annealing Monte Carlo for large-scale spin-glass simulations
- Boosting quantum annealer performance via sample persistence
- Fluctuation guided search in quantum annealing
- Optimization by a quantum reinforcement algorithm
- Substochastic Monte Carlo Algorithms