Related Experiment Video
Updated: Jul 4, 2026
12:11
Computation of Atmospheric Concentrations of Molecular Clusters from ab initio Thermochemistry
Published on: April 8, 2020
Effect of local minima on adiabatic quantum optimization.
1D-Wave Systems Inc., 100-4401 Still Creek Drive, Burnaby, British Columbia, V5C 6G9, Canada.
Physical Review Letters
|June 4, 2008
Summary
Adiabatic quantum computation faces challenges with problems having many local minima. The spectral gap shrinks exponentially, increasing computation time and limiting quantum advantage for these specific problem types.
Area of Science:
- Quantum Computing
- Computational Complexity
- Quantum Optimization
Background:
- Adiabatic quantum computation (AQC) is a promising paradigm for solving complex problems.
- Estimating the spectral gap is crucial for determining AQC performance.
- The energy landscape of a problem Hamiltonian dictates the computation's feasibility.
Purpose of the Study:
- To develop a perturbative method for estimating the spectral gap in AQC.
- To analyze the impact of problem Hamiltonian structure on spectral gap size.
- To identify problem classes unsuitable for AQC.
Main Methods:
- Perturbative analysis of energy level structures.
- Focus on Hamiltonians with numerous local minima near the global minimum.
- Evaluation of spectral gap scaling with problem size.
Main Results:
- A method to estimate the spectral gap based on Hamiltonian energy levels.
- Demonstration that problems with many local minima lead to exponentially small spectral gaps.
- Identification of a correlation between small spectral gaps and exponentially long computation times.
Conclusions:
- Problems with numerous local minima near the global minimum are not suitable for standard AQC.
- Quantum advantage may only be accessible via local adiabatic evolution, requiring strict phase coherence.
- Understanding the energy spectrum is key to assessing AQC applicability.
Related Concept Videos
01:31Local Maximum and Minimum Values
In multivariable calculus, a function of two variables can exhibit local maximum or minimum values at certain points on its surface. A local maximum occurs when the function's value at a point is greater than at all nearby points, while a local minimum occurs when the function’s value is less than at all nearby locations. These points are referred to as local extrema and are of central importance in optimization problems.Local extrema are found at critical points, where the surface becomes...
01:18Adiabatic 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...
01:27Pressure and Volume in an Adiabatic Process
Free expansion of a gas is an adiabatic process. However, there are few differences between free expansion and adiabatic expansion. During free expansion, no work is done, and there is no change in internal energy. But, for an adiabatic expansion, work is done, and there is a change in internal energy. During an adiabatic process, the relation between the pressure and volume is obtained from the condition for the adiabatic process, that is,
01:20Work Done in an Adiabatic Process
Consider the adiabatic compression of an ideal gas in the cylinder of an automobile diesel engine. The gasoline vapor is injected into the cylinder of an automobile engine when the piston is in its expanded position. The temperature, pressure, and volume of the resulting gas-air mixture are 20 °C, 1.00 x 105 N/m2, and 240 cm3 , respectively. The mixture is then compressed adiabatically to a volume of 40 cm3. Note that, in the actual operation of an automobile engine, the compression is not...
01:28Methods of Medium Optimization
Optimizing growth media enhances microbial proliferation and maximizes product yield. Statistical experimental design methodologies provide structured and reproducible approaches, offering progressively higher levels of robustness and efficiency.The One-Factor-at-a-Time (OFAT) MethodThe One-Factor-at-a-Time (OFAT) method involves adjusting a single variable while keeping all others constant. However, it cannot detect interactions between variables, often leading to suboptimal outcomes when...
01:20Maxwell-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
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