Jove
Visualize
Contact Us
JoVE
x logofacebook logolinkedin logoyoutube logo
ABOUT JoVE
OverviewLeadershipBlogJoVE Help Center
AUTHORS
Publishing ProcessEditorial BoardScope & PoliciesPeer ReviewFAQSubmit
LIBRARIANS
TestimonialsSubscriptionsAccessResourcesLibrary Advisory BoardFAQ
RESEARCH
JoVE JournalMethods CollectionsJoVE Encyclopedia of ExperimentsArchive
EDUCATION
JoVE CoreJoVE BusinessJoVE Science EducationJoVE Lab ManualFaculty Resource CenterFaculty Site
Terms & Conditions of Use
Privacy Policy
Policies

Related Concept Videos

Optimization Problems01:26

Optimization Problems

Optimization problems often involve identifying maximum or minimum values under specific constraints. A well-known example is determining the longest horizontal pipe that can be moved around a right-angled corner, where a 3-meter-wide hallway meets a 2-meter-wide hallway. This scenario, common in architectural design and industrial transport, can be understood conceptually through geometric and trigonometric reasoning.To visualize the problem, consider the pipe as a straight line that touches...
Mechanistic Models: Compartment Models in Algorithms for Numerical Problem Solving01:29

Mechanistic Models: Compartment Models in Algorithms for Numerical Problem Solving

Mechanistic models play a crucial role in algorithms for numerical problem-solving, particularly in nonlinear mixed effects modeling (NMEM). These models aim to minimize specific objective functions by evaluating various parameter estimates, leading to the development of systematic algorithms. In some cases, linearization techniques approximate the model using linear equations.
In individual population analyses, different algorithms are employed, such as Cauchy's method, which uses a...
Maxwell-Boltzmann Distribution: Problem Solving01:20

Maxwell-Boltzmann Distribution: Problem Solving

Individual molecules in a gas move in random directions, but a gas containing numerous molecules has a predictable distribution of molecular speeds, which is known as the Maxwell-Boltzmann distribution, f(v).
This distribution function f(v) is defined by saying that the expected number N (v1,v2) of particles with speeds between v1 and v2 is given by
Adiabatic Processes for an Ideal Gas01:18

Adiabatic Processes for an Ideal Gas

When an ideal gas is compressed adiabatically, that is, without adding heat, work is done on it, and its temperature increases. In an adiabatic expansion, the gas does work, and its temperature drops. Adiabatic compressions actually occur in the cylinders of a car, where the compressions of the gas-air mixture take place so quickly that there is no time for the mixture to exchange heat with its environment. Nevertheless, because work is done on the mixture during the compression, its...
Statically Indeterminate Problem Solving01:16

Statically Indeterminate Problem Solving

Statically indeterminate problems are those where statics alone can not determine the internal forces or reactions. Consider a structure comprising two cylindrical rods made of steel and brass. These rods are joined at point B and restrained by rigid supports at points A and C. Now, the reactions at points A and C and the deflection at point B are to be determined. This rod structure is classified as statically indeterminate as the structure has more supports than are necessary for maintaining...
Ampere-Maxwell's Law: Problem-Solving01:17

Ampere-Maxwell's Law: Problem-Solving

A parallel-plate capacitor with capacitance C, whose plates have area A and separation distance d, is connected to a resistor R and a battery of voltage V. The current starts to flow at t = 0. What is the displacement current between the capacitor plates at time t? From the properties of the capacitor, what is the corresponding real current?
To solve the problem, we can use the equations from the analysis of an RC circuit and Maxwell's version of Ampère's law.
For the first part of the problem,...

You might also read

Related Articles

Articles linked to this work by shared authors, journal, and citation graph.

Sort by
Same author

Quantum annealing with manufactured spins.

Nature·2011
Same author

Consistency of the adiabatic theorem.

Physical review letters·2009
Same author

Probing noise in flux qubits via macroscopic resonant tunneling.

Physical review letters·2008
Same author

Effect of local minima on adiabatic quantum optimization.

Physical review letters·2008
Same author

Macroscopic resonant tunneling in the presence of low frequency noise.

Physical review letters·2008
Same author

Thermally assisted adiabatic quantum computation.

Physical review letters·2008
Same journal

Erratum: Bacterial Turbulence at Compressible Fluid Interfaces [Phys. Rev. Lett. 136, 138301 (2026)].

Physical review letters·2026
Same journal

Unveiling Light-Quark Yukawa Flavor Structure via Dihadron Fragmentation at Lepton Colliders.

Physical review letters·2026
Same journal

Adaptable Route to Fast Coherent State Transport via Bang-Bang-Bang Protocols.

Physical review letters·2026
Same journal

Topological Transition and Emergence of Elasticity of Dislocation in Skyrmion Lattice: Beyond Kittel's Magnetic-Polar Analogy.

Physical review letters·2026
Same journal

Pound-Drever-Hall Method for Superconducting-Qubit Readout.

Physical review letters·2026
Same journal

Coupling a ^{73}Ge Nuclear Spin to an Electrostatically Defined Quantum Dot in Silicon.

Physical review letters·2026
See all related articles

Related Experiment Video

Updated: Jun 3, 2026

Large Scale Energy Efficient Sensor Network Routing Using a Quantum Processor Unit
05:30

Large Scale Energy Efficient Sensor Network Routing Using a Quantum Processor Unit

Published on: September 8, 2023

Does adiabatic quantum optimization fail for NP-complete problems?

Neil G Dickson1, M H S Amin

  • 1D-Wave Systems, Inc., 100-4401 Still Creek Drive, Burnaby, British Columbia, V5C 6G9, Canada.

Physical Review Letters
|March 17, 2011
PubMed
Summary
This summary is machine-generated.

Adiabatic quantum optimization may not fail for NP-complete problems. Researchers found specific paths for the maximum independent set problem, avoiding performance-hindering energy gaps. Proving failure requires showing such paths are impossible to find.

Related Experiment Videos

Last Updated: Jun 3, 2026

Large Scale Energy Efficient Sensor Network Routing Using a Quantum Processor Unit
05:30

Large Scale Energy Efficient Sensor Network Routing Using a Quantum Processor Unit

Published on: September 8, 2023

Area of Science:

  • Quantum Computing
  • Computational Complexity Theory
  • Optimization Algorithms

Background:

  • Adiabatic quantum optimization (AQO) is a quantum computation approach.
  • Concerns exist that AQO may fail for NP-complete problems due to small energy gaps.
  • These gaps arise from local minima crossings near the end of adiabatic evolution.

Purpose of the Study:

  • To analytically investigate the potential failure of AQO for NP-complete problems.
  • To determine if specific adiabatic paths can avoid performance-limiting energy gaps.
  • To clarify the conditions under which AQO might be proven ineffective.

Main Methods:

  • Utilized perturbation expansion for analytical investigation.
  • Focused on the NP-hard maximum independent set problem.
  • Examined the behavior of energy levels of the final Hamiltonian during adiabatic evolution.

Main Results:

  • Demonstrated the existence of adiabatic paths for the maximum independent set problem.
  • Showed that these paths avoid problematic crossings of local and global minima.
  • Found that energy gaps do not necessarily become exponentially small along these paths.

Conclusions:

  • The argument that AQO fails for NP-complete problems due to small gaps is not universally proven.
  • For the maximum independent set problem, suitable adiabatic paths exist.
  • Proving AQO's failure requires demonstrating the impossibility of finding such paths in polynomial time.