Reinforcement Quantum Annealing: A Hybrid Quantum Learning Automata
Open accessAbstract
We introduce the notion of reinforcement quantum annealing (RQA) scheme in which an intelligent agent searches in the space of Hamiltonians and interacts with a quantum annealer that plays the stochastic environment role of learning automata. At each iteration of RQA, after analyzing results (samples) from the previous iteration, the agent adjusts the penalty of unsatisfied constraints and re-casts the given problem to a new Ising Hamiltonian. As a proof-of-concept, we propose a novel approach for casting the problem of Boolean satisfiability (SAT) to Ising Hamiltonians and show how to apply the RQA for increasing the probability of finding the global optimum. Our experimental results on two different benchmark SAT problems (namely factoring pseudo-prime numbers and random SAT with phase transitions), using a D-Wave 2000Q quantum processor, demonstrated that RQA finds notably better solutions with fewer samples, compared to the best-known techniques in the realm of quantum annealing.
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Integrity signals
Registry
Cites
Statistics
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Claims other papers make about this one
Each is checked against this paper’s own text: does it say what the citing paper says it does?
Penalty terms in the cost Hamiltonian for constraint incorporation have been defined using reinforcement learning.
“Furthermore, penalty terms in the cost Hamiltonian for constraint incorporation have been defined using reinforcement learning [9].”
From Quantum Combinatorial Optimization in the NISQ Era: A Systematic Mapping Study (2024) · cites this paper as [9]
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Cites
Reinforcement Learning: An Introduction
Sutton, R. S., & Barto, A. (2005) · IEEE Transactions on Neural Networks · doi:10.1109/tnn.2004.842673 · Cited by 25,263 · see citing works
The Proceedings of the National Academy of Sciences
Richards, J. W. (1915) · Science · doi:10.1126/science.42.1074.161 · Cited by 13,941 · see citing works
Reinforcement Learning: A Survey
Kaelbling, L. P., Littman, M. L., & Moore, A. W. (1996) · Journal of Artificial Intelligence Research · doi:10.1613/jair.301 · Cited by 8,972 · see citing works
de Moura, L., & Bjørner, N. (2008) · Lecture Notes in Computer Science · doi:10.1007/978-3-540-78800-3_24 · Cited by 6,595 · see citing works
Biamonte, J., Wittek, P., Pancotti, N., Rebentrost, P., Wiebe, N., & Lloyd, S. (2017) · Nature · doi:10.1038/nature23474 · Cited by 4,779 · see citing works
Ladd, T. D., Jelezko, F., Laflamme, R., Nakamura, Y., Monroe, C., & O’Brien, J. L. (2010) · Nature · doi:10.1038/nature08812 · Cited by 3,592 · see citing works
Ising formulations of many NP problems
Lucas, A. (2014) · Frontiers in Physics · doi:10.3389/fphy.2014.00005 · Cited by 2,512 · see citing works
Quantum annealing in the transverse Ising model
Kadowaki, T., & Nishimori, H. (1998) · Physical Review E · doi:10.1103/physreve.58.5355 · Cited by 2,339 · see citing works
Quantum annealing with manufactured spins
Johnson, M. W., Amin, M. H. S., Gildert, S., Lanting, T., Hamze, F., Dickson, N., Harris, R., Berkley, A. J., Johansson, J., Bunyk, P., et al. (2011) · Nature · doi:10.1038/nature10012 · Cited by 1,891 · see citing works
Learning Automata: An Introduction
Narendra, K. S., & Thathachar, M. A. L. (1989) · CERN Document Server (European Organization for Nuclear Research) · Cited by 1,556 · see citing works
Machine learning & artificial intelligence in the quantum domain: a review of recent progress
Dunjko, V., & Briegel, H. J. (2018) · Reports on Progress in Physics · doi:10.1088/1361-6633/aab406 · Cited by 1,132 · see citing works
Where the really hard problems are
Cheeseman, P., Kanefsky, B., & Taylor, W. M. (1991) · Cited by 1,015 · see citing works
Theory of Quantum Annealing of an Ising Spin Glass
Santoro, G. E., Martoňák, R., Tosatti, E., & Car, R. (2002) · Science · doi:10.1126/science.1068774 · Cited by 734 · see citing works
<i>Colloquium</i> : Quantum annealing and analog quantum computation
Das, A., & Chakrabarti, B. K. (2008) · Reviews of Modern Physics · doi:10.1103/revmodphys.80.1061 · Cited by 700 · see citing works
Quantum annealing: A new method for minimizing multidimensional functions
Finnila, A. B., Gomez, M. A., Sebenik, C., Stenson, C., & Doll, J. D. (1994) · Chemical Physics Letters · doi:10.1016/0009-2614(94)00117-0 · Cited by 698 · see citing works
Finding low-energy conformations of lattice protein models by quantum annealing
Perdomo-Ortiz, A., Dickson, N., Drew-Brook, M., Rose, G., & Aspuru-Guzik, A. (2012) · Scientific Reports · doi:10.1038/srep00571 · Cited by 366 · see citing works
SATLIB: An Online Resource for Research on SAT
Hoos, H. H., Stützle, T., Gent, I. P., et al. (2000) · Cited by 306 · see citing works
Generating hard satisfiability problems
Selman, B., Mitchell, D. G. M., & Levesque, H. J. (1996) · Artificial Intelligence · doi:10.1016/0004-3702(95)00045-3 · Cited by 300 · see citing works
The European Physical Journal Special Topics
(2013) · The European Physical Journal Special Topics · doi:10.1007/11734.1951-6401 · Cited by 286 · see citing works
A practical heuristic for finding graph minorsPreprint
Cai, J. L., Macready, W. G., & Roy, A. (2014) · arXiv (Cornell University) · doi:10.48550/arxiv.1406.2741 · Cited by 284 · see citing works
Anderson localization makes adiabatic quantum optimization fail
Altshuler, B. L., Krovi, H., & Roland, J. (2010) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.1002116107 · Cited by 237 · see citing works
A case study in programming a quantum annealer for hard operational planning problems
Rieffel, E. G., Venturelli, D., O’Gorman, B., Do, M. B., Prystay, E. M., & Smelyanskiy, V. (2014) · Quantum Information Processing · doi:10.1007/s11128-014-0892-x · Cited by 221 · see citing works
Ray, P., Chakrabarti, B. K., & Chakrabarti, A. (1989) · Physical review. B, Condensed matter · doi:10.1103/physrevb.39.11828 · Cited by 209 · see citing works
Understanding Random SAT: Beyond the Clauses-to-Variables Ratio
Nudelman, E., Leyton‐Brown, K., Hoos, H. H., et al. (2004) · Lecture notes in computer science · doi:10.1007/978-3-540-30201-8_33 · Cited by 184 · see citing works
Generating Satisfiable Problem Instances
Achlioptas, D., Gomes, C. P., Kautz, H., et al. (2000) · Cited by 147 · see citing works
Quantum annealing by the path-integral Monte Carlo method: The two-dimensional random Ising model
Martoňák, R., Santoro, G. E., & Tosatti, E. (2002) · Physical review. B, Condensed matter · doi:10.1103/physrevb.66.094203 · Cited by 140 · see citing works
Nonnegative/Binary matrix factorization with a D-Wave quantum annealer
O’Malley, D., Vesselinov, V. V., Alexandrov, B. S., & Alexandrov, L. B. (2018) · PLOS ONE · doi:10.1371/journal.pone.0206653 · Cited by 140 · see citing works
Quantum Annealing Implementation of Job-Shop SchedulingPreprint
Venturelli, D., Marchand, D. J. J., & Rojo, G. (2015) · arXiv (Cornell University) · doi:10.48550/arxiv.1506.08479 · Cited by 129 · see citing works
Discrete optimization using quantum annealing on sparse Ising models
Bian, Z., Chudak, F. A., Israel, R. B., Lackey, B., Macready, W. G., & Roy, A. (2014) · Frontiers in Physics · doi:10.3389/fphy.2014.00056 · Cited by 129 · see citing works
Next-Generation Topology of D-Wave Quantum Processors
Boothby, K., Bunyk, P., Raymond, J., & Roy, A. (2020) · arXiv · doi:10.48550/arxiv.2003.00133 · Cited by 125 · see citing works
Amara, P., Hsu, D., & Straub, J. E. (1993) · The Journal of Physical Chemistry · doi:10.1021/j100127a023 · Cited by 120 · see citing works
Control of Automated Guided Vehicles Without Collision by Quantum Annealer and Digital Devices
Ohzeki, M., Miki, A., Miyama, M. J., & Terabe, M. (2019) · Frontiers in Computer Science · doi:10.3389/fcomp.2019.00009 · Cited by 104 · see citing works
Quantum annealing correction for random Ising problems
Pudenz, K. L., Albash, T., & Lidar, D. A. (2015) · Physical Review A · doi:10.1103/physreva.91.042302 · Cited by 99 · see citing works
A NASA perspective on quantum computing: Opportunities and challenges
Biswas, R., Zhang, J., Kechezhi, K., Knysh, S., Mandrà, S., O’Gorman, B., Perdomo‐Ortiz, A., Petukhov, A. G., Realpe-Gómez, J., Rieffel, E. G., et al. (2016) · Parallel Computing · doi:10.1016/j.parco.2016.11.002 · Cited by 96 · see citing works
Exponential Enhancement of the Efficiency of Quantum Annealing by Non-Stoquastic Hamiltonians
Nishimori, H., & Takada, K. (2017) · Frontiers in ICT · doi:10.3389/fict.2017.00002 · Cited by 95 · see citing works
Improving solutions by embedding larger subproblems in a D-Wave quantum annealer
Okada, S., Ohzeki, M., Terabe, M., & Taguchi, S. (2019) · Scientific Reports · doi:10.1038/s41598-018-38388-4 · Cited by 91 · see citing works
Basic protocols in quantum reinforcement learning with superconducting circuits
Lamata, L. (2017) · Scientific Reports · doi:10.1038/s41598-017-01711-6 · Cited by 89 · see citing works
Mapping Constrained Optimization Problems to Quantum Annealing with Application to Fault Diagnosis
Bian, Z., Chudak, F. A., Israel, R. B., Lackey, B., Macready, W. G., & Roy, A. (2016) · Frontiers in ICT · doi:10.3389/fict.2016.00014 · Cited by 86 · see citing works
A quantum annealing approach for fault detection and diagnosis of graph-based systems
Perdomo‐Ortiz, A., Fluegemann, J., Narasimhan, S., Biswas, R., & Smelyanskiy, V. (2015) · The European Physical Journal Special Topics · doi:10.1140/epjst/e2015-02347-y · Cited by 78 · see citing works
Factoring larger integers with fewer qubits via quantum annealing with optimized parameters
Peng, W., Wang, B., Hu, F., Wang, Y.-J., Fang, X., Chen, X., & Wang, C. (2019) · Science China Physics Mechanics and Astronomy · doi:10.1007/s11433-018-9307-1 · Cited by 76 · see citing works
Prime factorization using quantum annealing and computational algebraic geometry
Dridi, R., & Alghassi, H. (2017) · Scientific Reports · doi:10.1038/srep43048 · Cited by 75 · see citing works
A Hybrid Quantum-Classical Approach to Solving Scheduling Problems
Tran, T. T., Do, M., Rieffel, E. G., Frank, J., Wang, Z., O’Gorman, B., Venturelli, D., & Beck, J. C. (2021) · Proceedings of the International Symposium on Combinatorial Search · doi:10.1609/socs.v7i1.18390 · Cited by 73 · see citing works
Theory versus practice in annealing-based quantum computing
McGeoch, C. C. (2020) · Theoretical Computer Science · doi:10.1016/j.tcs.2020.01.024 · Cited by 69 · see citing works
A path towards quantum advantage in training deep generative models with quantum annealers
Vinci, W., Buffoni, L., Sadeghi, H., Khoshaman, A. H., Andriyash, E., & Amin, M. H. S. (2020) · Machine Learning Science and Technology · doi:10.1088/2632-2153/aba220 · Cited by 57 · see citing works
Quantum Annealing: An Introduction and New Developments
Ohzeki, M., & Nishimori, H. (2011) · Journal of Computational and Theoretical Nanoscience · doi:10.1166/jctn.2011.1776963 · Cited by 52 · see citing works
Erratum: Prime factorization using quantum annealing and computational algebraic geometry
Dridi, R., & Alghassi, H. (2017) · Scientific Reports · doi:10.1038/srep44963 · Cited by 50 · see citing works
The Strategy Challenge in SMT Solving
de Moura, L., & Passmore, G. O. (2013) · Lecture notes in computer science · doi:10.1007/978-3-642-36675-8_2 · Cited by 49 · see citing works
Non-stoquastic Hamiltonians in quantum annealing via geometric phases
Vinci, W., & Lidar, D. A. (2017) · npj Quantum Information · doi:10.1038/s41534-017-0037-z · Cited by 48 · see citing works
A quantum annealing approach for boolean satisfiability problem
Su, J., Tu, T., & He, L. (2016) · ACM/IEEE Design Automation Conference (DAC) · doi:10.1145/2897937.2897973 · Cited by 39 · see citing works
Embedding Inequality Constraints for Quantum Annealing Optimization
Vyskočil, T., Pakin, S., & Djidjev, H. N. (2019) · Lecture notes in computer science · doi:10.1007/978-3-030-14082-3_2 · Cited by 36 · see citing works
Solving SAT and MaxSAT with a Quantum Annealer: Foundations and a Preliminary Report
Bian, Z., Chudak, F. A., Macready, W. G., Roy, A., Sebastiani, R., & Varotti, S. (2017) · Lecture notes in computer science · doi:10.1007/978-3-319-66167-4_9 · Cited by 31 · see citing works
Optimizing the Spin Reversal Transform on the D-Wave 2000Q
Pelofske, E., Hahn, G., & Djidjev, H. (2019) · 2019 IEEE International Conference on Rebooting Computing (ICRC) · doi:10.1109/icrc.2019.8914719 · Cited by 26 · see citing works
Quantum Annealing Based Binary Compressive Sensing with Matrix UncertaintyPreprint
Ayanzadeh, R., Mousavi, S., Halem, M., & Finin, T. (2019) · arXiv (Cornell University) · doi:10.13016/m2k6ga-cvu4 · Cited by 25 · see citing works
Self-citationAn Ensemble Approach for Compressive Sensing with Quantum Annealers
Ayanzadeh, R., Halem, M., & Finin, T. (2020) · IEEE International Geoscience and Remote Sensing Symposium (IGARSS) · doi:10.1109/igarss39084.2020.9323509 · Cited by 18 · see citing works
Self-citationSantoro, G. E., & Tosatti, E. (2007) · Nature Physics · doi:10.1038/nphys706 · Cited by 12 · see citing works
Clausal Form Transformation in MaxSAT
Li, C. M., Manyà, F., & Soler, J. R. (2019) · Proceedings/Proceedings - International Symposium on Multiple-Valued Logic · doi:10.1109/ismvl.2019.00031 · Cited by 10 · see citing works
Ramezanpour, A. (2018) · Physical Review A · doi:10.1103/physreva.98.062309 · Cited by 8 · see citing works
Simple Constraint Embedding for Quantum Annealers
Vyskočil, T., & Djidjev, H. N. (2018) · IEEE International Conference on Rebooting Computing (ICRC) · doi:10.1109/icrc.2018.8638624 · Cited by 8 · see citing works
Quantum-Assisted Greedy AlgorithmsPreprint
Ayanzadeh, R., Halem, M., Dorband, J. E., & Finin, T. (2019) · arXiv (Cornell University) · doi:10.13016/m2n5ap-kape · Cited by 8 · see citing works
Self-citationSAT-based Compressive SensingPreprint
Halem, M., & Finin, T. (2019) · arXiv (Cornell University) · doi:10.13016/m2ou7d-6jos · Cited by 7 · see citing works
Self-citationBalasubramanian, K., & Abbas, A. M. (2017) · Advances in information security, privacy, and ethics book series · doi:10.4018/978-1-5225-2915-6.ch017 · Cited by 4 · see citing works
Flagged first, then by citations
Research works printed but not linked: 9
- [34]Adachi, S. H. & Henderson, M. P. Application of quantum annealing to training of deep neural networks. arXiv preprint arXiv:1510.06356 (2015). · arXiv
- [39]Dorband, J. E. Extending the d-wave with support for higher precision coefficients. arXiv preprint arXiv:1807.05244 (2018). · arXiv
- [41]Dorband, J. E. A method of finding a lower energy solution to a qubo/ising objective function. arXiv preprint arXiv:1801.04849 (2018). · arXiv
- [45]Biere, A., Heule, M. & van Maaren, H. Handbook of satisfiability, vol.185 (IOS press, 2009).
- [59]Golden, J. K. & O’Malley, D. Pre-and post-processing in quantum-computational hydrologic inverse analysis. arXiv preprint arXiv:1910.00626 (2019). · arXiv
- [61]Mooney, G. J., Tonetto, S. U., Hill, C. D. & Hollenberg, L. C. Mapping np-hard problems to restricted adiabatic quantum architectures. arXiv preprint arXiv:1911.00249 (2019). · arXiv
- [64]Mousavi, S., Taghiabadi, M. M. R. & Ayanzadeh, R. A survey on compressive sensing: Classical results and recent advancements. arXiv preprint arXiv:1908.01014 (2019). · arXiv
- [65]Garey, M. R. & Johnson, D. S. Computers and intractability, vol. 29 (wh freeman New York, 2002).
- [67]Cox, D. R. & Miller, H. D. The theory of stochastic processes (Routledge, 1977).
Cited by
Sorted by citations
Quantum Combinatorial Optimization in the NISQ Era: A Systematic Mapping Study
Gemeinhardt, F., Garmendia, A., Wimmer, M., Weder, B., & Leymann, F. (2024) · ACM Computing Surveys · doi:10.1145/3620668 · Cited by 22 · see citing works
“Furthermore, penalty terms in the cost Hamiltonian for constraint incorporation have been defined using reinforcement learning [9].”
BackgroundMethodInfluential
- Authors
- Ayanzadeh, R., Halem, M., & Finin, T.
- Affiliations
- University of Maryland, Baltimore County (US)
- Corresponding author
- Ayanzadeh, Ramin
- Venue
- Scientific Reports
- Published
- 2020-05-14
- Volume
- 10
- Issue
- 1
- Pages
- 7952-7952
- ISSN
- 2045-2322 (ISSN-L)
- PMC
- PMC7224393
- OpenAlex
- W3025966862
- Cited by
- 57
- References
- 61
- Citations by year
- 2026: 3 · 2025: 7 · 2024: 8 · 2023: 11 · 2022: 14 · 2021: 8 · 2020: 5 · 2019: 1
- FWCI
- 3.73
- Type
- journal article
- Language
- en
- Open access
- gold
- doi.org
- Locations
- Scientific Reports (publishedVersion, cc-by)
- PubMed Central (publishedVersion, cc-by)
- PubMed (publishedVersion)
- Maryland Shared Open Access Repository (USMAI Consortium) (submittedVersion, cc-by)
- Digital Repository at the University of Maryland (University of Maryland College Park) (cc-by)
- Funders
- National Aeronautics and Space Administration (NNH16ZDA001N-AIST16-0091, NNH16ZDA001N-AIST, NNH16ZDA001N)
- National Institute of Advanced Industrial Science and Technology
- National Institutes of Health
- National Institute of General Medical Sciences (R25-GM55036, GM55036, 2 R25-GM55036, R25GM055036)
- Topics
- Physical Sciences › Computer Science › Artificial Intelligence › Quantum Computing Algorithms and Architecture
- Physical Sciences › Computer Science › Artificial Intelligence › Metaheuristic Optimization Algorithms Research
- Physical Sciences › Computer Science › Computer Networks and Communications › Constraint Satisfaction and Optimization
- Keywords
- learning automata, quantum annealing, Ising Hamiltonian, Boolean satisfiability, constraint satisfaction, D-Wave 2000Q, global optimum, phase transitions
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
