Reducibility among Combinatorial Problems

New directions in cryptography

Diffie, W., & Hellman, M. (1976) · IEEE Transactions on Information Theory · doi:10.1109/tit.1976.1055638 · Cited by 14,713 · see citing works

The complexity of computing the permanent

Valiant, L. G. (1979) · Theoretical Computer Science · doi:10.1016/0304-3975(79)90044-6 · Cited by 2,705 · 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

Optimization, approximation, and complexity classes

Papadimitriou, C. H., & Yannakakis, M. (1991) · Journal of Computer and System Sciences · doi:10.1016/0022-0000(91)90023-x · Cited by 1,653 · see citing works

The Variational Quantum Eigensolver: A review of methods and best practices

Tilly, J., Chen, H., Cao, S., Picozzi, D., Setia, K., Li, Y., Grant, E., Wossnig, L., Rungger, I., Booth, G. H., et al. (2022) · Physics Reports · doi:10.1016/j.physrep.2022.08.003 · Cited by 1,031 · see citing works

Constructing optimal binary decision trees is NP-complete

Hyafil, L., & Rivest, R. L. (1976) · Information Processing Letters · doi:10.1016/0020-0190(76)90095-8 · Cited by 959 · see citing works

An Analysis of Several Heuristics for the Traveling Salesman Problem

Rosenkrantz, D. J., Stearns, R. E., & Lewis, II (1977) · SIAM Journal on Computing · doi:10.1137/0206041 · Cited by 837 · see citing works

Pseudo-Boolean optimization

Boros, E., & Hammer, P. L. (2002) · Discrete Applied Mathematics · doi:10.1016/s0166-218x(01)00341-9 · Cited by 827 · see citing works

Hybrid Quantum-Classical Algorithms and Quantum Error Mitigation

Endo, S., Cai, Z., Benjamin, S. C., & Yuan, X. (2021) · Journal of the Physical Society of Japan · doi:10.7566/jpsj.90.032001 · Cited by 566 · see citing works

Approximation Algorithms for Bin-Packing — An Updated Survey

Coffman, E. G., Garey, M. R., & Johnson, D. S. (1984) · CISM International Centre for Mechanical Sciences · doi:10.1007/978-3-7091-4338-4_3 · Cited by 433 · see citing works

A simple on-line bin-packing algorithm

Lee, C. C., & Lee, D. T. (1985) · Journal of the ACM · doi:10.1145/3828.3833 · Cited by 357 · see citing works

A systematic survey of computer-aided diagnosis in medicine: Past and present developments

Yanase, J., & Triantaphyllou, E. (2019) · Expert Systems with Applications · doi:10.1016/j.eswa.2019.112821 · Cited by 303 · see citing works

Measurement optimization in the variational quantum eigensolver using a minimum clique cover

Verteletskyi, V., Yen, T.-C., & Izmaylov, A. F. (2020) · The Journal of Chemical Physics · doi:10.1063/1.5141458 · Cited by 269 · see citing works

Variational quantum algorithms for discovering Hamiltonian spectra

Jones, T., Endo, S., McArdle, S., Yuan, X., & Benjamin, S. C. (2019) · Physical Review A · doi:10.1103/physreva.99.062304 · Cited by 256 · see citing works

Unitary Partitioning Approach to the Measurement Problem in the Variational Quantum Eigensolver Method

Izmaylov, A. F., Yen, T.-C., Lang, R. A., & Verteletskyi, V. (2020) · Journal of Chemical Theory and Computation · doi:10.1021/acs.jctc.9b00791 · Cited by 171 · see citing works

Performance of the Quantum Approximate Optimization Algorithm on the Maximum Cut Problem

Crooks, G. E. (2018) · arXiv · doi:10.48550/arxiv.1811.08419 · Cited by 158 · see citing works

Quantum Hamiltonian Complexity

Gharibian, S., Huang, Y., Landau, Z., & Shin, S. W. (2015) · Foundations and Trends® in Theoretical Computer Science · doi:10.1561/0400000066 · Cited by 144 · see citing works

On-line bin packing in linear time

Ramanan, P., Brown, D. J., Lee, C. C., & Lee, D. T. (1989) · Journal of Algorithms · doi:10.1016/0196-6774(89)90031-x · Cited by 127 · see citing works

What Works Best When? A Systematic Evaluation of Heuristics for Max-Cut and QUBO

Dunning, I., Gupta, S., & Silberholz, J. (2018) · INFORMS Journal on Computing · doi:10.1287/ijoc.2017.0798 · Cited by 128 · see citing works

Martinize2 and Vermouth provide a unified framework for molecular topology generation

Kroon, P. C., Grünewald, F., Barnoud, J., van Tilburg, M., Brasnett, C., Souza, P. C., Wassenaar, T. A., & Marrink, S. J. (2025) · eLife · doi:10.7554/elife.90627 · Cited by 124 · see citing works

Applications of near-term photonic quantum computers: software and algorithms

Bromley, T. R., Arrazola, J. M., Jahangiri, S., Izaac, J., Quesada, N., Gran, A. D., Schuld, M., Swinarton, J., Zabaneh, Z., & Killoran, N. (2020) · Quantum Science and Technology · doi:10.1088/2058-9565/ab8504 · Cited by 128 · see citing works

Benchmarking Advantage and D-Wave 2000Q quantum annealers with exact cover problems

Willsch, D., Willsch, M., Gonzalez Calaza, C. D., Jin, F., De Raedt, H., Svensson, M., & Michielsen, K. (2022) · Quantum Information Processing · doi:10.1007/s11128-022-03476-y · Cited by 114 · see citing works

Detecting outlying properties of exceptional objects

Angiulli, F., Fassetti, F., & Palopoli, L. (2009) · ACM Transactions on Database Systems · doi:10.1145/1508857.1508864 · Cited by 88 · see citing works

Counterfactual Explanations for Multivariate Time Series

Ates, E., Aksar, B., Leung, V. J., & Coskun, A. K. (2021) · 2021 International Conference on Applied Artificial Intelligence (ICAPAI) · doi:10.1109/icapai49758.2021.9462056 · Cited by 88 · see citing works

Tertiary alphabet for the observable protein structural universe

Mackenzie, C. O., Zhou, J., & Grigoryan, G. (2016) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.1607178113 · Cited by 72 · see citing works

A quantum walk-assisted approximate algorithm for bounded NP optimisation problems

Marsh, S., & Wang, J. B. (2019) · Quantum Information Processing · doi:10.1007/s11128-019-2171-3 · Cited by 50 · see citing works

Towards large-scale quantum optimization solvers with few qubits

Sciorilli, M., Borges, L., Patti, T. L., García-Martín, D., Camilo, G., Anandkumar, A., & Aolita, L. (2025) · Nature Communications · doi:10.1038/s41467-024-55346-z · Cited by 47 · see citing works

Evaluating Quantum Approximate Optimization Algorithm: A Case Study

Shaydulin, R., & Alexeev, Y. (2019) · 2019 Tenth International Green and Sustainable Computing Conference (IGSC) · doi:10.1109/igsc48788.2019.8957201 · Cited by 55 · see citing works

Algorithm for DNA sequence assembly by quantum annealing

Nałęcz-Charkiewicz, K., & Nowak, R. M. (2022) · BMC Bioinformatics · doi:10.1186/s12859-022-04661-7 · Cited by 37 · see citing works

On the Solution of the Steiner Tree NP-Hard Problem via Physarum BioNetwork

Caleffi, M., Akyildiz, I. F., & Paura, L. (2015) · IEEE/ACM Transactions on Networking · doi:10.1109/tnet.2014.2317911 · Cited by 35 · see citing works

Lower bounds on circuit depth of the quantum approximate optimization algorithm

Herrman, R., Ostrowski, J., Humble, T. S., & Siopsis, G. (2021) · Quantum Information Processing · doi:10.1007/s11128-021-03001-7 · Cited by 35 · see citing works

Analysis of Quantum Approximate Optimization Algorithm under Realistic Noise in Superconducting Qubits

Alam, M., Ash-Saki, A., & Ghosh, S. (2019) · arXiv · doi:10.48550/arxiv.1907.09631 · Cited by 33 · see citing works

Max-independent set and the quantum alternating operator ansatz

Saleem, Z. H. (2020) · International Journal of Quantum Information · doi:10.1142/s0219749920500112 · Cited by 28 · see citing works

Foundations for Workflow Application Scheduling on D-Wave System

Tomasiewicz, D., Pawlik, M., Malawski, M., & Rycerz, K. (2020) · Lecture Notes in Computer Science · doi:10.1007/978-3-030-50433-5_40 · Cited by 11 · see citing works

Proteome Coverage Prediction for Integrated Proteomics Datasets

Claassen, M., Aebersold, R., & Buhmann, J. M. (2011) · Journal of Computational Biology · doi:10.1089/cmb.2010.0261 · Cited by 8 · see citing works

Understanding Agent Complexity Through Affordances

Baker, B., & Roberts, S. (2025) · Minds and Machines · doi:10.1007/s11023-025-09748-7