Related Experiment Video
Updated: Jun 24, 2026

Large Scale Energy Efficient Sensor Network Routing Using a Quantum Processor Unit
Published on: September 8, 2023
A quantum adiabatic evolution algorithm applied to random instances of an NP-complete problem
E Farhi1, J Goldstone, S Gutmann
1Center for Theoretical Physics, Massachusetts Institute of Technology, Cambridge, MA 02139, USA. farhi@mit.edu
Abstract:
A quantum system will stay near its instantaneous ground state if the Hamiltonian that governs its evolution varies slowly enough. This quantum adiabatic behavior is the basis of a new class of algorithms for quantum computing. We tested one such algorithm by applying it to randomly generated hard instances of an NP-complete problem. For the small examples that we could simulate, the quantum adiabatic algorithm worked well, providing evidence that quantum computers (if large ones can be built) may be able to outperform ordinary computers on hard sets of instances of NP-complete problems.
Related Concept Videos
Random Sampling Method
Random Variables
Uppercase letters such as X or Y denote a random variable. Lowercase letters like x or y denote the value of a random variable. If X is a random variable, then X is written in words, and x is given as a number.
For example, let X = the...
Randomized Experiments
Simple randomization
Simple...
Mechanistic Models: Compartment Models in Algorithms for Numerical Problem Solving
In individual population analyses, different algorithms are employed, such as Cauchy's method, which uses a...
Application of Nonlinear Inequalities
Lagrange Multipliers: Problem Solving
