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 Experiment Videos

Optimization by quantum annealing: lessons from hard satisfiability problems.

Demian A Battaglia1, Giuseppe E Santoro, Erio Tosatti

  • 1International School for Advanced Studies (SISSA), and INFM Democritos National Simulation Center, Via Beirut 2-4, I-34014 Trieste, Italy. battagli@sissa.it

Physical Review. E, Statistical, Nonlinear, and Soft Matter Physics
|August 11, 2005
PubMed
Summary
This summary is machine-generated.

Related Concept Videos

You might also read

Related Articles

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

Sort by
Same author

Frictional Unlocking and Energy-Controlled Constrained Densification in Nanoparticle Networks.

ACS nano·2025
Same author

Superlubric-Locked Transition of Twist Grain Boundaries in 3D Crystals.

Physical review letters·2025
Same author

Can Neural Networks Learn Atomic Stick-Slip Friction?

ACS applied materials & interfaces·2025
Same author

Striped Twisted State in the Orientational Epitaxy on Quasicrystals.

Physical review letters·2025
Same author

Universal moiré buckling of freestanding 2D bilayers.

Proceedings of the National Academy of Sciences of the United States of America·2024
Same author

Nonmonotonic Velocity Dependence of Atomic Friction Induced by Multiple Slips.

Physical review letters·2024
Same journal

Tension on dsDNA bound to ssDNA-RecA filaments may play an important role in driving efficient and accurate homology recognition and strand exchange.

Physical review. E, Statistical, nonlinear, and soft matter physics·2016
Same journal

Publisher's Note: Amplitude-phase coupling drives chimera states in globally coupled laser networks [Phys. Rev. E 91, 040901(R) (2015)].

Physical review. E, Statistical, nonlinear, and soft matter physics·2016
Same journal

Erratum: Shapes of sedimenting soft elastic capsules in a viscous fluid [Phys. Rev. E 92, 033003 (2015)].

Physical review. E, Statistical, nonlinear, and soft matter physics·2016
Same journal

Erratum: Attenuation of excitation decay rate due to collective effect [Phys. Rev. E 90, 022142 (2014)].

Physical review. E, Statistical, nonlinear, and soft matter physics·2016
Same journal

Publisher's Note: Role of connectivity and fluctuations in the nucleation of calcium waves in cardiac cells [Phys. Rev. E 92, 052715 (2015)].

Physical review. E, Statistical, nonlinear, and soft matter physics·2016
Same journal

Publisher's Note: Lattice Boltzmann approach for complex nonequilibrium flows [Phys. Rev. E 92, 043308 (2015)].

Physical review. E, Statistical, nonlinear, and soft matter physics·2016
See all related articles

Path integral Monte Carlo simulated quantum annealing was applied to a large random satisfiability problem. Quantum annealing showed poorer performance than classical methods, but a novel quantum cooling protocol improved short-term results.

Area of Science:

  • Computational physics
  • Quantum computing
  • Optimization algorithms

Background:

  • Combinatorial optimization problems, like random satisfiability (SAT), present significant computational challenges.
  • Quantum annealing is a metaheuristic approach that leverages quantum fluctuations to find solutions.
  • Understanding the dynamics of quantum annealing compared to classical methods is crucial for algorithm development.

Purpose of the Study:

  • To apply path integral Monte Carlo simulated quantum annealing to a large-scale SAT problem (N=10,000).
  • To compare the dynamical behavior and energy landscape exploration of quantum and classical annealing.
  • To introduce and evaluate a novel quantum cooling protocol.

Main Methods:

  • Utilized path integral Monte Carlo simulated quantum annealing.

Related Experiment Videos

  • Applied the algorithm to a large, hard instance of the random satisfiability problem.
  • Compared linear-schedule quantum annealing with classical simulated annealing and introduced a field-cycling based quantum cooling protocol.

    • Main Results:

    • Observed qualitative differences in energy landscape exploration between quantum and classical annealing.
    • Linear-schedule quantum annealing performed worse than classical annealing for this specific SAT problem.
    • The novel quantum cooling protocol demonstrated superior performance over classical simulated annealing on short timescales.

    Conclusions:

    • Quantum annealing dynamics differ significantly from classical annealing in exploring complex energy landscapes.
    • Standard linear-schedule quantum annealing is not universally superior to classical methods for all optimization problems.
    • A specialized quantum cooling protocol offers potential advantages for specific optimization tasks over short durations.