Semiclassical Gravity Efficiently Solves $\mathsf{NP}$-Complete Problems

• URL: http://arxiv.org/abs/2606.14806v1
• Date: Thu, 11 Jun 2026 23:42:07 GMT
• Title: Semiclassical Gravity Efficiently Solves $\mathsf{NP}$-Complete Problems
• Abstract summary: We show that the weak-field dynamics of a massive and non-relativistic problem can be used to solve an $mathsf$NP-complete problem in time.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Assuming the gravitational field is classical and that it couples to quantum fields via the semiclassical Einstein field equations, we show that the weak-field dynamics of a massive and non-relativistic qubit can in principle be used to solve an $\mathsf{NP}$-complete problem in polynomial time. We attribute this vast computational power to the non-linear dynamics afforded by the semiclassical Einstein field equations. Consequently, the above two assumptions entail a violation of the Physical Extended Church--Turing Thesis, which we regard as evidence for the quantization of gravity.

Related papers

• Probing the limits of the semiclassical Einstein equation [0.0]
  Einstein equation is often invoked when backreaction of quantum matter/fields on the spacetime is at stake.<n>We propose a new way to probe the limits of this approximation by exploiting peculiar nonlinearities of gravity.<n>We construct a controlled, analytically tractable setting where the incoherent mixture of weak-gravity states drives the system into a strong-gravity regime.
  arXiv  Detail & Related papers  (2026-05-22T18:07:21Z)
• Quantum optomechanics of lossy bodies: general approach and structured squeezed vacuum effects [51.56484100374058]
  We investigate the overall optomechanical force experienced by a macroscopic lossy object in free space under external quantum illumination.<n>By driving the scattering field with an anisotropic, multimode squeezed vacuum state, the spatial profile of the electromagnetic quantum fluctuations can be engineered to exhibit broken rotational symmetry.<n>We establish a general formalism for macroscopic quantum optomechanics that operates beyond the constraints of thermal equilibrium.
  arXiv  Detail & Related papers  (2026-04-07T13:25:43Z)
• Hybrid quantum-classical simulations of semiclassical gravity [39.146761527401424]
  We propose a hybrid quantum-classical algorithm for the simulation of real-time dynamics in interacting quantum field theories coupled to classical fields.<n>By discretizing space and time, we construct an iterative protocol that simulates the Trotterized dynamics of the quantum fields subject to the classical fields.<n>Our work paves the way for future experiments exploring other non-tractable regimes, including non-perturbative interactions of the quantum fields.
  arXiv  Detail & Related papers  (2026-03-06T17:48:21Z)
• Quantum simulation of massive Thirring and Gross--Neveu models for arbitrary number of flavors [40.72140849821964]
  We consider the massive Thirring and Gross-Neveu models with arbitrary number of fermion flavors, $N_f$, discretized on a spatial one-dimensional lattice of size $L$.<n>We prepare the ground states of both models with excellent fidelity for system sizes up to 20 qubits with $N_f = 1,2,3,4$.<n>Our work is a concrete step towards the quantum simulation of real-time dynamics of large $N_f$ fermionic quantum field theories models.
  arXiv  Detail & Related papers  (2026-02-25T19:00:01Z)
• Quantum neural ordinary and partial differential equations [38.77776626953413]
  We present a unified framework that brings the continuous-time formalism of classical neural ODEs/PDEs into quantum machine learning and quantum control.<n>We define QNODEs as the evolution of finite-dimensional quantum systems, and QNPDEs as infinite-dimensional (continuous-variable) counterparts.
  arXiv  Detail & Related papers  (2025-08-24T18:43:44Z)
• Classical-quantum scattering [0.0]
  We find that we can define and calculate probabilities scattering which are Lorentz-covariant.<n>We comment on lessons learned for attempts to couple quantum matter to non-quantum'' gravity.
  arXiv  Detail & Related papers  (2024-12-06T08:14:50Z)
• Classical Algorithms for Hamiltonian Dynamics Mean Value and Guided Local Hamiltonian Problem [9.550310003133555]
  We introduce an efficient classical algorithm for simulating the short-time dynamics of arbitrary local quantum systems.<n>We also present a tailored quantum algorithm that efficiently solves the guided local Hamiltonian (GLH) problem to constant additive error.
  arXiv  Detail & Related papers  (2024-09-06T09:59:12Z)
• Real-time dynamics of false vacuum decay [49.1574468325115]
  We investigate false vacuum decay of a relativistic scalar field in the metastable minimum of an asymmetric double-well potential. We employ the non-perturbative framework of the two-particle irreducible (2PI) quantum effective action at next-to-leading order in a large-N expansion.
  arXiv  Detail & Related papers  (2023-10-06T12:44:48Z)
• Lagrangian trajectories and closure models in mixed quantum-classical dynamics [0.0]
  We present a fully Hamiltonian theory of quantum-classical dynamics that appears to be the first to ensure a series of consistency properties. Based on Lagrangian phase-space paths, the model possesses a quantum-classical Poincar'e integral invariant as well as infinite classes of Casimir functionals.
  arXiv  Detail & Related papers  (2023-03-03T18:55:15Z)
• Coupling Quantum Matter and Gravity [0.0]
  We consider the question how the Hamiltonian of a composite two-particle system in an external gravitational field can be computed in a systematic post-Newtonian setting without backreaction. We consider the question of how quantum matter may act as source for classical gravitational fields via the semiclassical Einstein equations.
  arXiv  Detail & Related papers  (2022-07-11T17:31:30Z)
• Entanglement dynamics of spins using a few complex trajectories [77.34726150561087]
  We consider two spins initially prepared in a product of coherent states and study their entanglement dynamics. We adopt an approach that allowed the derivation of a semiclassical formula for the linear entropy of the reduced density operator.
  arXiv  Detail & Related papers  (2021-08-13T01:44:24Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.