Computational Complexity and Physical Law

Seth Lloyd

Jincheng Zhang

This paper introduces Quantum Computing Optimization via Physical Laws (QCOP), a novel algorithm designed to leverage the inherent parallelism of quantum computing and the fundamental relationships within physical laws for optimization problems. The core mechanism involves translating an optimization challenge into a quantum mechanical system governed by the Schrödinger equation. Crucially, the algorithm incorporates conservation laws derived from physical principles as constraints, aiming to enhance both efficiency and accuracy. QCOP's novelty lies in the direct integration of quantum computing with established physical laws, offering a potentially transformative approach to optimization. The proposed methodology offers a distinct pathway compared to traditional quantum optimization algorithms, capitalizing on the unique properties of quantum systems to solve complex problems. The framework presented here provides a theoretical foundation for future research and development in this burgeoning field. We outline the key elements of the QCOP algorithm and discuss its potential applications.

Fabio Benatti

As already emphasized in Chap. 4 information is physical and the limits to information processing tasks are ultimately set by the underlying physical laws. For instance, the standing models of computation are based on the physics of deterministic and/or stochastic classical processes; instead, quantum computation theory [84, 90, 156, 198, 266] studies the new possibilities offered by a model of computation based on quantum mechanical laws. The birth of such a theory finds a technological motivation in the high pace at which chip miniaturization proceeds.

changzheng zhou, ZIQING zhou

This paper starts from two fundamental principles—Information Conservation(A1) and Finite-Step Computability (A2)—to argue the mechanism for the naturalemergence of inherent lower bounds of computational complexity in physically realizable computational processes. Research shows that core concepts of computationalcomplexity (such as polynomial-time upper bounds, circuit depth lower bounds) arenot mere mathematical abstractions but are quantitative laws that must be followedby physical systems when performing information transformations under fundamental constraints such as energy, time, and information conservation. Specifically, thequantum speed limit together with Axiom A2 jointly sets a polynomial-time upperbound for any finite-energy physical system; while the Information Conservationaxiom (A1) combined with the principle of minimal physical realization complexity(A3) ensures that the logical difficulty of a computational task is inevitably reflected in the topological complexity of the spatiotemporal structure of its physicalrealization. This sets a lower bound for the circuit depth determined by topological invariants, and in quantum many-body systems, it directly manifests asvolume-law growth of entanglement entropy, whose coefficient is determined by theunderlying hardware architecture. To test this theoretical framework, this paperdesigns two cross-scale experimental paths: at the microscopic level, using superconducting quantum processors to precisely measure the volume-law coefficient ofentanglement in random quantum circuits; at the macroscopic cosmological level,inferring the “computational complexity” growth information of the early-universeinflationary process by detecting the phase coherence of the primordial gravitationalwave background. These schemes aim to place foundational issues of computationalcomplexity within the domain of empirically testable physical science.