Realizable Circuit Complexity: Embedding Computation in Space-Time

• URL: http://arxiv.org/abs/2509.19161v3
• Date: Fri, 07 Nov 2025 21:36:10 GMT
• Title: Realizable Circuit Complexity: Embedding Computation in Space-Time
• Authors: Benjamin Prada, Ankur Mali,
• Abstract summary: We introduce the family of realizable circuit classes $mathbfRC_d$, embedded in physical $d$-dimensional space.<n>Within this framework, we show that algorithms with $nd/(d-1))$ cannot scale to inputs of $nd/(d-1))$.<n>By unifying geometry, causality, and information flow, $mathbfRC_d$ extends circuit into the physical domain.
• Score: 0.2750124853532831
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Classical circuit complexity characterizes parallel computation in purely combinatorial terms, ignoring the physical constraints that govern real hardware. The standard classes $\mathbf{NC}$, $\mathbf{AC}$, and $\mathbf{TC}$ treat unlimited fan-in, free interconnection, and polynomial gate counts as feasible -- assumptions that conflict with geometric, energetic, and thermodynamic realities. We introduce the family of realizable circuit classes $\mathbf{RC}_d$, which model computation embedded in physical $d$-dimensional space. Each circuit in $\mathbf{RC}_d$ obeys conservative realizability laws: volume scales as $\mathcal{O}(t^d)$, cross-boundary information flux is bounded by $\mathcal{O}(t^{d-1})$ per unit time, and growth occurs through local, physically constructible edits. These bounds apply to all causal systems, classical or quantum. Within this framework, we show that algorithms with runtime $\omega(n^{d/(d-1)})$ cannot scale to inputs of maximal entropy, and that any $d$-dimensional parallel implementation offers at most a polynomial speed-up of degree $(d-1)$ over its optimal sequential counterpart. In the limit $d\to\infty$, $\mathbf{RC}_\infty(\mathrm{polylog})=\mathbf{NC}$, recovering classical parallelism as a non-physical idealization. By unifying geometry, causality, and information flow, $\mathbf{RC}_d$ extends circuit complexity into the physical domain, revealing universal scaling laws for computation.

Related papers

• $\mathsf{QAC}^0$ Contains $\mathsf{TC}^0$ (with Many Copies of the Input) [0.9023122463034333]
  $mathsfQAC0$ is the class of constant-depth quantum circuits constructed from arbitrary single-qubit gates and generalized Toffoli gates.<n>We show that $mathsfQAC0$ circuits are significantly more powerful than their classical counterparts.
  arXiv  Detail & Related papers  (2026-01-06T18:40:44Z)
• Spectral Small-Incremental-Entangling: Breaking Quasi-Polynomial Complexity Barriers in Long-Range Interacting Systems [2.911917667184046]
  Key challenge in quantum complexity is how entanglement structure emerges from dynamics.<n>We introduce Spectral-Entangling Strength, measuring the structural entangling power of an operator.<n>We prove a Spectral SIE theorem: a universal limit for R'enyi entanglement growth at $alpha ge 1/2$, revealing a robust $1/s2$ tail in the entanglement spectrum.
  arXiv  Detail & Related papers  (2025-09-15T14:56:40Z)
• A Quantum Computational Perspective on Spread Complexity [0.0]
  We establish a direct connection between spread complexity and quantum circuit complexity by demonstrating that spread complexity emerges as a limiting case of a circuit complexity framework built from two fundamental operations: time-evolution and superposition.<n>Our approach leverages a computational setup where unitary gates and beam-splitting operations generate target states, with the minimal cost of synthesis yielding a complexity measure that converges to spread complexity in the infinitesimal time-evolution limit.
  arXiv  Detail & Related papers  (2025-06-08T19:04:42Z)
• Time and Memory Trade-off of KV-Cache Compression in Tensor Transformer Decoding [30.769940410718558]
  The key-value cache in the tensor version of transformers presents a significant bottleneck during inference.<n>Our work generalizes the space complexity barriers result to tensor attention version.<n>Overall, our work provides a theoretical foundation for us to understand the time-memory tradeoff of KV-Cache compression in tensor attention decoding.
  arXiv  Detail & Related papers  (2025-03-14T06:01:42Z)
• Learning and Computation of $Φ$-Equilibria at the Frontier of Tractability [85.07238533644636]
  $Phi$-equilibria is a powerful and flexible framework at the heart of online learning and game theory.<n>We show that an efficient online algorithm incurs average $Phi$-regret at most $epsilon$ using $textpoly(d, k)/epsilon2$ rounds.<n>We also show nearly matching lower bounds in the online setting, thereby obtaining for the first time a family of deviations that captures the learnability of $Phi$-regret.
  arXiv  Detail & Related papers  (2025-02-25T19:08:26Z)
• The Sample Complexity of Online Reinforcement Learning: A Multi-model Perspective [55.15192437680943]
  We study the sample complexity of online reinforcement learning in the general setting of nonlinear dynamical systems with continuous state and action spaces.<n>Our algorithm achieves a policy regret of $mathcalO(N epsilon2 + mathrmln(m(epsilon)/epsilon2)$, where $epsilon$ is the time horizon.<n>In the special case where the dynamics are parametrized by a compact and real-valued set of parameters, we prove a policy regret of $mathcalO(sqrt
  arXiv  Detail & Related papers  (2025-01-27T10:01:28Z)
• The Space Complexity of Approximating Logistic Loss [11.338399194998933]
  We prove a general $tildeOmega(dcdot mu_mathbfy(mathbfX))$ space lower bound when $epsilon$ is constant.<n>We also refute a prior conjecture that $mu_mathbfy(mathbfX)$ is hard to compute.
  arXiv  Detail & Related papers  (2024-12-03T18:11:37Z)
• On the Computational Power of QAC0 with Barely Superlinear Ancillae [10.737102385599169]
  We show that any depth-$d$ $mathrmQAC0$ circuit requires $n1+3-d$ ancillae to compute a function with approximate degree $ta(n)$.<n>This is the first superlinear lower bound on the super-linear sized $mathrmQAC0$.
  arXiv  Detail & Related papers  (2024-10-09T02:55:57Z)
• Surrogate Constructed Scalable Circuits ADAPT-VQE in the Schwinger model [0.0]
  We develop a new approach, (SC)$2$-ADAPT-VQE, to further advance the simulation of periodic systems on quantum computers. Our approach builds an ansatz from a pool of coordinate-invariant operators defined for arbitrarily large, though not arbitrarily small, volumes. Our method uses a classically tractable Surrogate Constructed'' method to remove irrelevant operators from the pool, reducing the minimum size for which the scalable circuits are defined.
  arXiv  Detail & Related papers  (2024-08-22T18:00:00Z)
• Recurrent Complex-Weighted Autoencoders for Unsupervised Object Discovery [62.43562856605473]
  We argue for the computational advantages of a recurrent architecture with complex-valued weights. We propose a fully convolutional autoencoder, SynCx, that performs iterative constraint satisfaction.
  arXiv  Detail & Related papers  (2024-05-27T15:47:03Z)
• Provably learning a multi-head attention layer [55.2904547651831]
  Multi-head attention layer is one of the key components of the transformer architecture that sets it apart from traditional feed-forward models. In this work, we initiate the study of provably learning a multi-head attention layer from random examples. We prove computational lower bounds showing that in the worst case, exponential dependence on $m$ is unavoidable.
  arXiv  Detail & Related papers  (2024-02-06T15:39:09Z)
• Parity vs. AC0 with simple quantum preprocessing [0.0]
  We study a hybrid circuit model where $mathsfAC0$ operates on measurement outcomes of a $mathsfQNC0$ circuit. We find that while $mathsfQNC0$ is surprisingly powerful for search and sampling tasks, that power is "locked away" in the global correlations of its output.
  arXiv  Detail & Related papers  (2023-11-22T20:27:05Z)
• Learning a Single Neuron with Adversarial Label Noise via Gradient Descent [50.659479930171585]
  We study a function of the form $mathbfxmapstosigma(mathbfwcdotmathbfx)$ for monotone activations. The goal of the learner is to output a hypothesis vector $mathbfw$ that $F(mathbbw)=C, epsilon$ with high probability.
  arXiv  Detail & Related papers  (2022-06-17T17:55:43Z)
• Threshold Phenomena in Learning Halfspaces with Massart Noise [56.01192577666607]
  We study the problem of PAC learning halfspaces on $mathbbRd$ with Massart noise under Gaussian marginals. Our results qualitatively characterize the complexity of learning halfspaces in the Massart model.
  arXiv  Detail & Related papers  (2021-08-19T16:16:48Z)
• Instance-optimality in optimal value estimation: Adaptivity via variance-reduced Q-learning [99.34907092347733]
  We analyze the problem of estimating optimal $Q$-value functions for a discounted Markov decision process with discrete states and actions. Using a local minimax framework, we show that this functional arises in lower bounds on the accuracy on any estimation procedure. In the other direction, we establish the sharpness of our lower bounds, up to factors logarithmic in the state and action spaces, by analyzing a variance-reduced version of $Q$-learning.
  arXiv  Detail & Related papers  (2021-06-28T00:38:54Z)
• Quantum learning algorithms imply circuit lower bounds [7.970954821067043]
  We establish the first general connection between the design of quantum algorithms and circuit lower bounds. Our proof builds on several works in learning theory, pseudorandomness, and computational complexity.
  arXiv  Detail & Related papers  (2020-12-03T14:03:20Z)
• An Optimal Separation of Randomized and Quantum Query Complexity [67.19751155411075]
  We prove that for every decision tree, the absolute values of the Fourier coefficients of a given order $ellsqrtbinomdell (1+log n)ell-1,$ sum to at most $cellsqrtbinomdell (1+log n)ell-1,$ where $n$ is the number of variables, $d$ is the tree depth, and $c>0$ is an absolute constant.
  arXiv  Detail & Related papers  (2020-08-24T06:50:57Z)
• On Gradient Descent Ascent for Nonconvex-Concave Minimax Problems [86.92205445270427]
  We consider non-con minimax problems, $min_mathbfx max_mathhidoty f(mathbfdoty)$ efficiently.
  arXiv  Detail & Related papers  (2019-06-02T03:03:45Z)

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.