HN Debrief

Semiclassical Gravity Efficiently Solves NP-Complete Problems

  • Computing Theory
  • Physics
  • Quantum Computing

The paper claims that if you couple quantum matter to classical gravity in the usual semiclassical way, the resulting dynamics become nonlinear enough to separate quantum states that are exponentially close together. That is exactly the kind of move that earlier complexity work used to show you could solve NP-complete and even counting problems in polynomial time. So the headline result is really an indirect argument against semiclassical gravity: either accepted complexity assumptions about physical computation fail, or this hybrid gravity model does.

Treat this as a complexity-theory attack on semiclassical gravity, not as evidence that NP-complete problems are about to become easy. If your work leans on claims about exotic physics enabling computation, the useful question is whether the model sneaks in nonlinear behavior that complexity theory already flags as suspicious.

Discussion mood

Interested but skeptical. People liked the paper as a neat complexity-theory argument against semiclassical gravity, but many pushed back on the headline, the strength of the physical assumptions, and the use of a simplified gravitational model rather than full semiclassical gravity.

Key insights

  1. 01

    Why this points toward quantum gravity

    The useful reading is not “gravity computes NP-complete problems” but “a classical gravity plus quantum matter hybrid seems to imply absurd computational power.” Once you cast it that way, the result becomes one more reason to think gravity cannot stay classical at the bottom. Several comments made the same jump the paper is making: if the physical extended Church-Turing thesis is a constraint you trust, then semiclassical gravity is the thing under pressure, not complexity theory.

    If you follow physics-adjacent compute claims, ask whether the result is really proposing a computer or using computation as a consistency test for a theory. In this case the business-relevant conclusion is about which physical models look implausible, not about new hardware roadmaps.

      Attribution:
    • QuesnayJr #1
    • api #1
    • tancop #1
  2. 02

    Quantum speedups do not rescue the claim

    The comments drew a hard line between ordinary quantum advantage and what this paper needs. Shor matters for factoring, but factoring is not known to be NP-hard. Grover only gives a square-root improvement for search. The paper instead relies on the kind of nonlinear state separation discussed in Abrams and Lloyd, where tiny amplitude differences get blown up into macroscopically measurable ones. That is a much more radical resource than standard quantum computing.

    Do not lump this result in with familiar quantum-computing progress. If a proposal depends on nonlinear quantum evolution or exponentially sensitive state discrimination, evaluate it as exotic physics, not as an extension of mainstream BQP results.

      Attribution:
    • xdertz #1
    • tromp #1
    • mofeing #1
  3. 03

    The simplified gravity model may be the real culprit

    The sharpest technical objection was that the argument seems to use the Newton-Schrödinger equation rather than the full semiclassical Einstein equation. That weakens the headline because the simplified equation may inject the dangerous nonlinearity on its own. The same comment also notes that actual semiclassical gravity calculations are often only handled perturbatively, so sweeping claims about full self-consistent dynamics are on shakier ground than the paper title suggests.

    Read this as a result about a particular modeling choice until experts confirm the reduction to full semiclassical gravity. If you cite the paper, be precise about which equations the computation actually uses.

      Attribution:
    • machina_ex_deus #1
  4. 04

    Aaronson’s lens is the right one

    A pointer to Scott Aaronson’s survey on NP-completeness and physical reality gave the right context for the whole discussion. The paper fits into a long-running program that treats computational complexity as a sanity check on physical theories. In that frame, impossible-looking computation is not a feature to celebrate. It is often evidence that the theory has wandered into unphysical territory.

    For teams exploring analog, optical, or physics-based computing, complexity theory is not just about algorithms. It is also a filter for ruling out models that hide unrealistic assumptions about precision, measurement, or dynamics.

      Attribution:
    • hiddencost #1

Against the grain

  1. 01

    Physical systems can sort only by smuggling in resources

    The spaghetti-sort aside pushed back on naive claims that a physical process beating an abstract algorithm automatically refutes complexity intuitions. The reply makes the real point: once you count transport, handling, precision, and parallel hardware, the magic disappears into the cost model. That is exactly the kind of accounting exotic-computation papers often understate.

    When someone says a physical setup computes faster than a Turing machine, inspect where the cost moved. Precision, material manipulation, and parallel apparatus often carry the complexity bill.

      Attribution:
    • advisedwang #1
    • DroneBetter #1
  2. 02

    Complexity assumptions are not settled physics

    A few comments resisted treating the physical extended Church-Turing thesis as firm enough to arbitrate fundamental physics. Oracle separations and the open status of P versus NP leave more room for surprise than the headline implies. One commenter even noted the possibility that quantum mechanics could run into deeper computational limits than standard theory suggests, which would be a physics discovery in its own right rather than a clean win for current complexity assumptions.

    Do not treat complexity conjectures as experimentally established laws. If you use them to attack a physical theory, present the result as suggestive pressure, not a knockout proof.

      Attribution:
    • jerf #1
    • IsTom #1
  3. 03

    The title oversells a conditional argument

    Several readers objected that the title sounds like a direct computational breakthrough when the abstract is explicitly conditional and “in principle.” That criticism changes how a nonexpert will read the paper. The actual content is an implication chain under assumptions, not a demonstrated construction of a usable solver.

    If you share or cite papers like this internally, rewrite the headline for your audience. The safe summary is “this model would imply implausible computational power,” not “this model solves NP-complete problems.”

      Attribution:
    • einpoklum #1 #2

In plain english

factoring ↩
The problem of breaking an integer into prime factors, which is believed hard classically but is not known to be NP-hard.
Newton-Schrödinger equation ↩
A nonlinear model that couples a quantum wavefunction to its own gravitational potential in a Newtonian approximation.
nonlinear quantum mechanics ↩
A hypothetical modification of quantum mechanics where state evolution is not linear, which often leads to unusual and very powerful computational consequences.
NP ↩
The class of problems whose proposed solutions can be checked in polynomial time by a standard computer.
NP-complete ↩
A class of decision problems believed to be very hard, where an efficient solution to any one of them would give efficient solutions to a large set of other hard problems.
NP-hard ↩
At least as hard as the hardest problems in NP, and not necessarily itself a decision problem in NP.
oracle ↩
A hypothetical black-box subroutine used in complexity theory to study what algorithms could do if they had access to answers for another problem instantly.
P ↩
The class of problems that a standard computer can solve in polynomial time, which is usually taken as the formal notion of efficiently solvable.
physical extended Church-Turing thesis ↩
The idea that any computation achievable by a realistic physical process can be simulated efficiently by a standard computational model, up to polynomial overhead.
semiclassical Einstein equation ↩
An equation that sets spacetime curvature from the quantum expectation value of the stress-energy tensor, combining classical general relativity with quantum matter.
semiclassical gravity ↩
A hybrid physics model where matter is treated with quantum mechanics but gravity is treated as a classical field rather than a quantum one.
Shor’s algorithm ↩
A quantum algorithm that can factor integers efficiently, which is important for cryptography but does not show efficient solutions to NP-complete problems.

Reference links

Background on complexity and physical computation

Quantum complexity references

Books and informal references

  • The New Turing Omnibus
    Mentioned as the source of the spaghetti-sort example used in a side discussion about physical cost models.