Related Experiment Video
Updated: Mar 28, 2026
05:39
Scalable Quantum Integrated Circuits on Superconducting Two-Dimensional Electron Gas Platform
Published on: August 2, 2019
10.5K
Undecidability of the spectral gap
Toby S Cubitt1,2, David Perez-Garcia3,4, Michael M Wolf5
1Department of Computer Science, University College London, Gower Street, London WC1E 6BT, UK.
Nature
|December 15, 2015
Summary
The spectral gap problem in quantum many-body physics is undecidable. This means no general algorithm can determine if a quantum system is gapped or gapless, impacting fundamental physics research.
Area of Science:
- Quantum Many-Body Physics
- Computational Complexity Theory
Background:
- The spectral gap, the energy difference between ground and excited states, is crucial for understanding quantum systems.
- Many significant problems in physics, including the Haldane conjecture and topological phases, revolve around spectral gaps.
Purpose of the Study:
- To determine the decidability of the spectral gap problem for quantum many-body systems.
- To investigate the implications of undecidability for other low-energy properties.
Main Methods:
- Construction of quantum spin systems on a 2D lattice with specific interaction types.
- Utilizing Hamiltonian complexity and aperiodic tilings.
- Encoding a quantum phase-estimation algorithm and a universal Turing machine within the system's ground state.
Main Results:
- The spectral gap problem for quantum spin systems with translationally invariant, nearest-neighbor interactions is proven to be undecidable.
- This undecidability extends to other low-energy properties like ground-state correlation decay.
- The spectral gap's determination is linked to the halting problem's outcome.
Conclusions:
- There is no universal algorithm to ascertain if an arbitrary quantum model is gapped or gapless.
- Certain quantum models exhibit spectral gap properties independent of mathematical axioms.
Related Concept Videos
01:19Limits with Oscillating Discontinuities
619
An oscillating discontinuity is a type of discontinuity in which a function’s values fluctuate infinitely often as the input approaches a particular point. Unlike jump discontinuities, where the function suddenly shifts between two values, or infinite discontinuities, where the function diverges without bound, an oscillating discontinuity arises from rapid back-and-forth variation. Because the function never stabilizes toward a single value, no finite limit exists at that point.One of the...
619
01:20Separable Differential Equations
257
A separable differential equation is a type of first-order differential equation where the derivative dy/dx can be expressed as a product of two functions: one that depends only on x and another that depends only on y. This allows for the rearrangement of the equation so that all terms involving y are on one side, and all terms involving x are on the other. This process, known as the separation of variables, simplifies the process of solving the equation by enabling the integration of both...
257
01:04¹³C NMR: ¹H–¹³C Decoupling
2.1K
The probability of having two carbon-13 atoms next to each other is negligible because of the low natural abundance of carbon-13. Consequently, peak splitting due to carbon-carbon spin-spin coupling is not observed in spectra. However, protons up to three sigma bonds away split the carbon signal according to the n+1 rule, resulting in complicated spectra.
A broadband decoupling technique is used to simplify these complex, sometimes overlapping, signals. Broadband decoupling relies on a...
A broadband decoupling technique is used to simplify these complex, sometimes overlapping, signals. Broadband decoupling relies on a...
2.1K
02:32The de Broglie Wavelength
34.6K
In the macroscopic world, objects that are large enough to be seen by the naked eye follow the rules of classical physics. A billiard ball moving on a table will behave like a particle; it will continue traveling in a straight line unless it collides with another ball, or it is acted on by some other force, such as friction. The ball has a well-defined position and velocity or well-defined momentum, p = mv, which is defined by mass m and velocity v at any given moment. This is the typical...
34.6K
01:19Routh-Hurwitz Criterion II
1.2K
In the application of the Routh-Hurwitz criterion, two specific scenarios can arise that complicate stability analysis.
The first scenario occurs when a singular zero appears in the first column of the Routh table. This situation creates a division by zero issues. To resolve this, a small positive or negative number, denoted as epsilon (∈), is substituted for the zero. The stability analysis proceeds by assuming a sign for ∈. If ∈ is positive, any sign change in the first...
The first scenario occurs when a singular zero appears in the first column of the Routh table. This situation creates a division by zero issues. To resolve this, a small positive or negative number, denoted as epsilon (∈), is substituted for the zero. The stability analysis proceeds by assuming a sign for ∈. If ∈ is positive, any sign change in the first...
1.2K
01:20Downsampling
777
When considering a sampled sequence with zero values between sampling instants, one can replace it by taking every N-th value of the sequence. At these integer multiples of N, the original and sampled sequences coincide. This process, known as decimation, involves extracting every N-th sample from a sequence, thereby creating a more efficient sequence.
The Fourier transform of the decimated sequence reveals a combination of scaled and shifted versions of the original spectrum. This...
The Fourier transform of the decimated sequence reveals a combination of scaled and shifted versions of the original spectrum. This...
777