Assessing Solution Quality of 3SAT on a Quantum Annealing Platform

Optimization by Simulated Annealing

Kirkpatrick, S., Gelatt, C. D., & Vecchi, M. P. (1983) · Science · doi:10.1126/science.220.4598.671 · Cited by 45,134 · see citing works

Simulating physics with computers

Feynman, R. P. (1982) · International Journal of Theoretical Physics · doi:10.1007/bf02650179 · Cited by 7,691 · see citing works

The complexity of theorem-proving procedures

Cook, S. A. (1971) · Proceedings of the third annual ACM symposium on Theory of computing - STOC '71 · doi:10.1145/800157.805047 · Cited by 6,385 · 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

Adiabatic quantum computation

Albash, T., & Lidar, D. A. (2018) · Reviews of Modern Physics · doi:10.1103/revmodphys.90.015002 · Cited by 1,546 · see citing works

Quantum Complexity Theory

Bernstein, E., & Vazirani, U. (1997) · SIAM Journal on Computing · doi:10.1137/s0097539796300921 · Cited by 1,503 · see citing works

Quantum complexity theory

Bernstein, E., & Vazirani, U. (1993) · Proceedings of the twenty-fifth annual ACM symposium on Theory of computing - STOC '93 · doi:10.1145/167088.167097 · Cited by 1,284 · see citing works

A Tabu Search Heuristic for the Vehicle Routing Problem

Gendreau, M., Hertz, A., & Laporte, G. (1994) · Management Science · doi:10.1287/mnsc.40.10.1276 · Cited by 1,280 · see citing works

Complexity and approximation: Combinatorial optimization problems and their approximability properties

(2000) · Computers & Mathematics with Applications · doi:10.1016/s0898-1221(00)90183-4 · Cited by 1,262 · see citing works

Where the really hard problems are

Cheeseman, P., Kanefsky, B., & Taylor, W. M. (1991) · Cited by 1,015 · see citing works

Some NP-complete problems in quadratic and nonlinear programming

Murty, K. G., & Kabadi, S. N. (1987) · Mathematical Programming · doi:10.1007/bf02592948 · Cited by 1,003 · see citing works

Complexity and Approximation

Giorgio Ausiello, A., Marchetti-Spaccamela, A., Crescenzi, P., Gambosi, G., Protasi, M., & Kann, V. (1999) · Springer eBooks · doi:10.1007/978-3-642-58412-1 · Cited by 985 · see citing works

Determining computational complexity from characteristic ‘phase transitions’

Monasson, R., Zecchina, R., Kirkpatrick, S., Selman, B., & Troyansky, L. (1999) · Nature · doi:10.1038/22055 · Cited by 781 · 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

Chaotic simulated annealing by a neural network model with transient chaos

Chen, L., & Aihara, K. (1995) · Neural Networks · doi:10.1016/0893-6080(95)00033-v · Cited by 661 · see citing works

Defining and detecting quantum speedup

Rønnow, T. F., Wang, Z., Job, J., Boixo, S., Isakov, S. V., Wecker, D., Martinis, J. M., Lidar, D. A., & Troyer, M. (2014) · Science · doi:10.1126/science.1252319 · Cited by 601 · see citing works

Critical Behavior in the Satisfiability of Random Boolean Expressions

Kirkpatrick, S., & Selman, B. (1994) · Science · doi:10.1126/science.264.5163.1297 · Cited by 582 · see citing works

Quantum Computation by Adiabatic Evolution

Farhi, E., Goldstone, J., Gutmann, S., & Sipser, M. (2000) · arXiv · doi:10.48550/arxiv.quant-ph/0001106 · Cited by 536 · see citing works

Traffic Flow Optimization Using a Quantum Annealer

Neukart, F., Compostella, G., Seidel, C., Dollen, D. V., Yarkoni, S., & Parney, B. (2017) · Frontiers in ICT · doi:10.3389/fict.2017.00029 · Cited by 470 · see citing works

Random K -satisfiability problem: From an analytic solution to an efficient algorithm

Mézard, M., & Zecchina, R. (2002) · Physical review. E, Statistical physics, plasmas, fluids, and related interdisciplinary topics · doi:10.1103/physreve.66.056126 · Cited by 448 · see citing works

Quantum advantage with shallow circuits

Bravyi, S. B., Gosset, D., & König, R. (2018) · Science · doi:10.1126/science.aar3106 · Cited by 406 · see citing works

Adiabatic Quantum Computation and Quantum Annealing

McGeoch, C. C. (2014) · Synthesis lectures on quantum computing · doi:10.2200/s00585ed1v01y201407qmc008 · Cited by 270 · see citing works

Quantum Arthur–Merlin games

Marriott, C., & Watrous, J. (2005) · Computational Complexity · doi:10.1007/s00037-005-0194-x · Cited by 242 · see citing works

Quantum stochastic optimization

Apolloni, B., Carvalho, C., & de Falco, D. (1989) · Stochastic Processes and their Applications · doi:10.1016/0304-4149(89)90040-9 · Cited by 211 · see citing works

How Powerful is Adiabatic Quantum ComputationPreprint

van Dam, W., Mosca, M., & Vazirani, U. V. (2001) · Cited by 203 · see citing works

A Hybrid Solution Method for the Capacitated Vehicle Routing Problem Using a Quantum Annealer

Feld, S., Roch, C., Gabor, T., Seidel, C., Neukart, F., Galter, I. R., Mauerer, W., & Linnhoff–Popien, C. (2019) · Frontiers in ICT · doi:10.3389/fict.2019.00013 · Cited by 200 · see citing works

Entropy of theK-Satisfiability Problem

Monasson, R., & Zecchina, R. (1996) · Physical Review Letters · doi:10.1103/physrevlett.76.3881 · Cited by 185 · see citing works

Quantum Speedup by Quantum Annealing

Somma, R. D., Nagaj, D., & Kieferová, M. (2012) · Physical Review Letters · doi:10.1103/physrevlett.109.050501 · Cited by 176 · see citing works

How powerful is adiabatic quantum computation?

van Dam, W., Mosca, M., & Vazirani, U. (2001) · Proceedings 42nd IEEE Symposium on Foundations of Computer Science · doi:10.1109/sfcs.2001.959902 · Cited by 175 · see citing works

Experimental evaluation of an adiabiatic quantum system for combinatorial optimization

McGeoch, C. C., & Wang, C. (2013) · ACM International Conference on Computing Frontiers (CF) · doi:10.1145/2482767.2482797 · Cited by 163 · see citing works

Global energy minimum searches using an approximate solution of the imaginary time Schroedinger equation

Amara, P., Hsu, D., & Straub, J. E. (1993) · The Journal of Physical Chemistry · doi:10.1021/j100127a023 · Cited by 120 · see citing works

Proof of the Satisfiability Conjecture for Large k

Ding, J., Sly, A., & Sun, N. (2015) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/2746539.2746619 · Cited by 89 · see citing works

Tabu Search∗

Glover, F., & Laguna, M. (2013) · Springer eBooks · doi:10.1007/978-1-4419-7997-1_17 · Cited by 82 · see citing works

Ontologies and Standards in Bioscience Research: For Machine or for Human

Mi, H., & Thomas, P. D. (2011) · Frontiers in Physiology · doi:10.3389/fphys.2011.00005 · Cited by 75 · see citing works

Exponentially Biased Ground-State Sampling of Quantum Annealing Machines with Transverse-Field Driving Hamiltonians

Mandrà, S., Zhu, Z., & Katzgraber, H. G. (2017) · Physical Review Letters · doi:10.1103/physrevlett.118.070502 · Cited by 72 · see citing works

Quantum adiabatic algorithms, small gaps, and different paths

Farhi, E., Goldstone, J., Gosset, D., Gutmann, S., Meyer, H. B., & Shor, P. W. (2011) · Quantum Information and Computation · doi:10.26421/qic11.3-4-1 · Cited by 57 · see citing works

Adiabatic Quantum Algorithms for the NP-Complete Maximum-Weight Independent Set, Exact Cover and 3SAT ProblemsPreprint

Choi, V. (2010) · arXiv (Cornell University) · doi:10.48550/arxiv.1004.2226 · Cited by 54 · see citing works

Quantum speedup of the traveling-salesman problem for bounded-degree graphs

Moylett, D. J., Linden, N., & Montanaro, A. (2017) · Physical Review A · doi:10.1103/physreva.95.032323 · Cited by 43 · see citing works

Different adiabatic quantum optimization algorithms

Choi, V. (2011) · Quantum Information and Computation · doi:10.26421/qic11.7-8-7 · Cited by 18 · see citing works

Small Traveling Salesman Problems

Warren, R. H. (2017) · Journal of Advances in Applied Mathematics · doi:10.22606/jaam.2017.22003 · Cited by 13 · see citing works

Quantum Annealing with Anneal Path Control: Application to 2-SAT Problems with Known Energy Landscapes

Hsu, T.-J., Jin, F., Seidel, C., et al. (2019) · Communications in Computational Physics · doi:10.4208/cicp.oa-2018-0257 · Cited by 9 · see citing works

Merlinization of complexity classes above BQP

Morimae, T., & Nishimura, H. (2017) · Quantum Information and Computation · doi:10.26421/qic17.11-12-3 · Cited by 5 · see citing works

The Complexity of Quantum Disjointness

Klauck, H. (2017) · DR-NTU (Nanyang Technological University) · doi:10.4230/lipics.mfcs.2017.15 · Cited by 3 · see citing works

ZZZ coupler for native embedding of MAX-3SAT problem instances in quantum annealing hardware

Strand, J., Przybysz, A. J., Ferguson, D., et al. (2017) · Bulletin of the American Physical Society · Cited by 2 · see citing works

Measurement-driven quantum computing: Performance of a 3-SAT solverPreprint

Benjamin, S. C., Zhao, L., & Fitzsimons, J. F. (2017) · arXiv (Cornell University) · doi:10.48550/arxiv.1711.02687 · Cited by 2 · see citing works

Merlinization of complexity classes above BQPPreprint

Morimae, T., & Nishimura, H. (2017) · arXiv (Cornell University) · doi:10.48550/arxiv.1704.01514 · Cited by 1 · see citing works

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

Formula Caching in DPLL

Beame, P. W., Impagliazzo, R., Pitassi, T., et al. (2010) · ACM Transactions on Computation Theory · doi:10.1145/1714450.1714452 · Cited by 40 · see citing works

The $\mathcal{ALCN}$ Description Logic Concept Satisfiability as a SAT Problem

Meissner, A. (2011) · Studies in computational intelligence · doi:10.1007/978-3-642-23418-7_22 · Cited by 1 · see citing works

Performance Evaluation of Tsunami Evacuation Route Planning on Multiple Annealing Machines

Liu, Y., Komatsu, K., Kumagai, M., Sato, M., & Kobayashi, H. (2023) · ACM International Conference on Computing Frontiers (CF) · doi:10.1145/3587135.3592193 · Cited by 3 · see citing works

Scalable formula decomposition for propositional satisfiability

Monnet, A., & Villemaire, R. (2010) · doi:10.1145/1822327.1822333 · Cited by 5 · see citing works

Towards an Optimal Hybrid Algorithm for EV Charging Stations Placement using Quantum Annealing and Genetic Algorithms

Chandra, A., Lalwani, J., & Jajodia, B. (2022) · International Conference on Trends in Quantum Computing and Emerging Business Technologies (TQCEBT) · doi:10.1109/tqcebt54229.2022.10041464 · Cited by 13 · see citing works