Understanding NP-complete problems is a central topic in computer science (NP stands for nondeterministic polynomial time). This is why adiabatic quantum optimization has attracted so much attention, as it provided a new approach to tackle NP-complete problems using a quantum computer. The efficiency of this approach is limited by small spectral gaps between the ground and excited states of the quantum computer's Hamiltonian. We show that the statistics of the gaps can be analyzed in a novel way, borrowed from the study of quantum disordered systems in statistical mechanics. It turns out that due to a phenomenon similar to Anderson localization, exponentially small gaps appear close to the end of the adiabatic algorithm for large random instances of NP-complete problems. This implies that unfortunately, adiabatic quantum optimization fails: The system gets trapped in one of the numerous local minima.
Download full-text PDF |
Source |
|---|---|
| http://www.ncbi.nlm.nih.gov/pmc/articles/PMC2906561 | PMC |
| http://dx.doi.org/10.1073/pnas.1002116107 | DOI Listing |
Publication Analysis
Top Keywords
Similar Publications
Stereodynamics of cold HD and D2 collisions with He.
J Chem Phys
March 2025
Department of Chemistry and Biochemistry, University of Nevada, Las Vegas, Nevada 89154, USA.
We present a comprehensive quantum mechanical study of stereodynamic control of HD + He and D2 + He collisions that have been probed experimentally by Perreault et al. [J. Phys.
View Article and Find Full Text PDFQuantum Chemical and Trajectory Surface Hopping Molecular Dynamics Study of Iodine-Based BODIPY Photosensitizer.
J Comput Chem
March 2025
J. Heyrovský Institute of Physical Chemistry of the Czech Academy of Sciences, Prague 8, Czech Republic.
A computational study of I-BODIPY (2-ethyl-4,4-difluoro-6,7-diiodo-1,3-dimethyl-4-bora-3a,4a-diaza-s-indacene) has been carried out to investigate its key photophysical properties as a potential triplet photosensitizer capable of generating singlet oxygen. Multireference CASPT2 and CASSCF methods have been used to calculate vertical excitation energies and spin-orbit couplings (SOCs), respectively, in a model (mono-iodinated BODIPY) molecule to assess the applicability of the single-reference second-order algebraic diagrammatic construction, ADC(2), method to this and similar molecules. Subsequently, time-dependent density functional theory (TD-DFT), possibly within the Tamm-Dancoff approximation (TDA), using several exchange-correlation functionals has been tested on I-BODIPY against ADC(2), both employing a basis set with a two-component pseudopotential on the iodine atoms.
View Article and Find Full Text PDFDeciphering the Luminescence Spectral Shape of an Oxyluciferin Analogue through a Mixed Quantum-Classical Approach.
J Phys Chem B
March 2025
Istituto di Chimica dei Composti OrganoMetallici (ICCOM-CNR), Area della Ricerca, Via G. Moruzzi 1, Pisa I-56124, Italy.
In this contribution, we present a computational study on the absorption and emission spectra of the anion in water, an analogue of the firefly oxyluciferin phenolate keto form. This compound displays a broad absorption spectrum and a large Stokes shift, two features that remain elusive to computational approaches, preventing a complete understanding of the photophysics behind this molecule. Here we attempt a fully first-principles computation of both absorption and emission spectral shapes and positions, explicitly including the effect of soft molecular flexible modes and of the stiff vibrational motions as well as those of the solvent.
View Article and Find Full Text PDFContinuous Transition between Bosonic Fractional Chern Insulator and Superfluid.
Phys Rev Lett
February 2025
The University of Hong Kong, Department of Physics and HK Institute of Quantum Science and Technology, Pokfulam Road, Hong Kong.
The properties of fractional Chern insulator (FCI) phases and the phase transitions between FCIs and Mott insulators in bosonic systems are well studied. The continuous transitions between FCI and superfluids (SFs), however, despite the inspiring field theoretical predictions [M. Barkeshli and J.
View Article and Find Full Text PDFCalculation of ion-ion mutual neutralization rate constants using Landau-Zener theory coupled with trajectory simulations for Ar+-Cl-, Br-, I.
J Chem Phys
March 2025
Department of Mechanical Engineering, The University of Memphis, Memphis, Tennessee 38152, USA.
In this computational study, we self-consistently calculate the rate constants of mutual neutralization reactions by incorporating the electron transfer probability, using Landau-Zener state transition theory with inputs derived from ab initio quantum chemistry calculations, into classical trajectory simulations. Electronic structure calculations are done using correlation consistent basis sets with multi-reference configuration interaction to map all the molecular electronic states below the ion-dissociation limit as a function of the distance between the reacting species. Our electronic structure calculations have been significantly improved from our previous work [Liu et al.
View Article and Find Full Text PDFWant AI Summaries of new PubMed Abstracts delivered to your In-box?
Enter search terms and have AI summaries delivered each week - change queries or unsubscribe any time!