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

Quantum adiabatic optimization and combinatorial landscapes.

V N Smelyanskiy1, S Knysh, R D Morris

  • 1NASA Ames Research Center, MS 269-3, Moffett Field, California 94035-1000, USA. Vadim.N.Smelyanskiy@nasa.gov

Physical Review. E, Statistical, Nonlinear, and Soft Matter Physics
|November 5, 2004
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

Removing leakage-induced correlated errors in superconducting quantum error correction.

Nature communications·2021
Same author

Diabatic Gates for Frequency-Tunable Superconducting Qubits.

Physical review letters·2019
Same author

[CORRELATION OF INDIVIDUAL AND JOINT INTEREST WITHIN MEDICAL LEGAL RELATIONS (REVIEW)].

Georgian medical news·2019
Same author

[STRENGTHENING OF CONTRACTUAL PRINCIPLES WITHIN LEGAL RELATIONS BETWEEN A PATIENT AND A MEDICAL INSTITUTION WHILE REFORMING THE HEALTH CARE SYSTEM IN UKRAINE].

Georgian medical news·2019
Same author

Fluctuations of Energy-Relaxation Times in Superconducting Qubits.

Physical review letters·2018
Same author

Absorption of wireless radiation in the child versus adult brain and eye from cell phone conversation or virtual reality.

Environmental research·2018
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

The Quantum Adiabatic Evolution algorithm faces a dynamic threshold in solving random graph satisfiability problems. Beyond this threshold, finding solutions becomes exponentially harder, impacting algorithm performance.

Area of Science:

  • Quantum computing
  • Statistical mechanics
  • Computer science

Background:

  • The satisfiability problem is a fundamental challenge in computer science.
  • Quantum Adiabatic Evolution (QAE) is a quantum algorithm with potential for solving complex problems.
  • Analyzing QAE performance on random graph instances is crucial for understanding its scalability.

Purpose of the Study:

  • To analyze the performance of the Quantum Adiabatic Evolution algorithm on a variant of the satisfiability problem.
  • To investigate the impact of the clause-to-variable ratio (gamma) on algorithm efficiency.
  • To identify and characterize a dynamic threshold affecting solution times.

Main Methods:

  • Formulating the problem as a statistical mechanics problem, focusing on the smallest eigenvalue and excitation gap.

Related Experiment Videos

  • Employing an annealing approximation with a refinement using macroscopic variables.
  • Introducing macroscopic parameters (landscapes) and a universality ansatz for random bit flips.

    • Main Results:

    • Demonstrated the existence of a dynamic threshold (gamma_d) for the QAE algorithm.
    • Showed that beyond this threshold, the algorithm's runtime increases exponentially.
    • Obtained tight upper bounds on the satisfiability transition by mapping random graphs to ensembles with reduced fluctuations.

    Conclusions:

    • The study identifies a critical threshold impacting the efficiency of Quantum Adiabatic Evolution for satisfiability problems.
    • The findings suggest limitations on QAE's practical applicability for certain problem instances.
    • The developed methods provide new insights into quantum algorithm performance and statistical mechanics of random systems.