Generalized Zurek's bound on the cost of an individual classical or quantum computation

• URL: http://arxiv.org/abs/2301.06838v3
• Date: Sun, 3 Sep 2023 09:14:37 GMT
• Title: Generalized Zurek's bound on the cost of an individual classical or quantum computation
• Authors: Artemy Kolchinsky
• Abstract summary: Zurek proposed that this cost was given by $K(xvert y)$, the conditional Kolmogorov complexity of $x$ given $y$. We show that $K(xvert y)$ is a minimal cost of mapping $x$ to $y$ that must be paid using some combination of heat, noise, and protocol complexity.
• Score: 0.8806033070373618
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We consider the minimal thermodynamic cost of an individual computation, where a single input $x$ is mapped to a single output $y$. In prior work, Zurek proposed that this cost was given by $K(x\vert y)$, the conditional Kolmogorov complexity of $x$ given $y$ (up to an additive constant which does not depend on $x$ or $y$). However, this result was derived from an informal argument, applied only to deterministic computations, and had an arbitrary dependence on the choice of protocol (via the additive constant). Here we use stochastic thermodynamics to derive a generalized version of Zurek's bound from a rigorous Hamiltonian formulation. Our bound applies to all quantum and classical processes, whether noisy or deterministic, and it explicitly captures the dependence on the protocol. We show that $K(x\vert y)$ is a minimal cost of mapping $x$ to $y$ that must be paid using some combination of heat, noise, and protocol complexity, implying a tradeoff between these three resources. Our result is a kind of "algorithmic fluctuation theorem" with implications for the relationship between the Second Law and the Physical Church-Turing thesis.

Related papers

• Settling the Sample Complexity of Online Reinforcement Learning [92.02082223856479]
  We show how to achieve minimax-optimal regret without incurring any burn-in cost. We extend our theory to unveil the influences of problem-dependent quantities like the optimal value/cost and certain variances.
  arXiv  Detail & Related papers  (2023-07-25T15:42:11Z)
• Quantum Resources Required to Block-Encode a Matrix of Classical Data [56.508135743727934]
  We provide circuit-level implementations and resource estimates for several methods of block-encoding a dense $Ntimes N$ matrix of classical data to precision $epsilon$. We examine resource tradeoffs between the different approaches and explore implementations of two separate models of quantum random access memory (QRAM) Our results go beyond simple query complexity and provide a clear picture into the resource costs when large amounts of classical data are assumed to be accessible to quantum algorithms.
  arXiv  Detail & Related papers  (2022-06-07T18:00:01Z)
• Non-local computation of quantum circuits with small light cones [0.0]
  Port-based teleportation costs much less entanglement when done only on a small number of qubits at a time. We give an explicit class of unitaries for which our protocol's entanglement cost scales better than any known protocol.
  arXiv  Detail & Related papers  (2022-03-18T18:00:06Z)
• Classical Verification of Quantum Computations in Linear Time [2.3465488122819123]
  We give a new CVQC protocol with complexity $O(poly(kappa)|C|)$, which is significantly faster than existing protocols. Our protocol is secure in the quantum random oracle model [arXiv:1008.0931] assuming the existence of noisy trapdoor claw-free functions. We also give a new classical channel remote state preparation protocol for states in $|+thetarangle=frac1sqrt2(|0rangle+eithetapi/4|1rangle):
  arXiv  Detail & Related papers  (2022-02-28T18:05:53Z)
• A lower bound on the space overhead of fault-tolerant quantum computation [51.723084600243716]
  The threshold theorem is a fundamental result in the theory of fault-tolerant quantum computation. We prove an exponential upper bound on the maximal length of fault-tolerant quantum computation with amplitude noise.
  arXiv  Detail & Related papers  (2022-01-31T22:19:49Z)
• Causality Constraint on Circuit Complexity from $COSMOEFT$ [1.5643170704979468]
  We study the behaviour of the circuit complexity measures and entanglement entropy with respect to the scale factor and $c_s$. We find various interesting unexplored features within the window, $0.024leq c_sleq 1$, which is supported by both causality and cosmological observation.
  arXiv  Detail & Related papers  (2021-11-22T19:09:51Z)
• Affine Quantization of the Harmonic Oscillator on the Semi-bounded domain $(-b,\infty)$ for $b: 0 \rightarrow \infty$ [0.0]
  We study the transformation of a classical system into its quantum counterpart using it affine quantization (AQ) Fantoni and Klauder (arXiv:2109.13447,Phys. Rev. D bf 103, 076013 (2021) We numerically solve this problem for $b rightarrow infty$, confirming the results of Gouba ( arXiv:2005.08696,J. High Energy Phys., Gravitation Cosmol.
  arXiv  Detail & Related papers  (2021-11-20T22:52:45Z)
• Annihilating Entanglement Between Cones [77.34726150561087]
  We show that Lorentz cones are the only cones with a symmetric base for which a certain stronger version of the resilience property is satisfied. Our proof exploits the symmetries of the Lorentz cones and applies two constructions resembling protocols for entanglement distillation.
  arXiv  Detail & Related papers  (2021-10-22T15:02:39Z)
• Permutation Compressors for Provably Faster Distributed Nonconvex Optimization [68.8204255655161]
  We show that the MARINA method of Gorbunov et al (2021) can be considered as a state-of-the-art method in terms of theoretical communication complexity. Theory of MARINA to support the theory of potentially em correlated compressors, extends to the method beyond the classical independent compressors setting.
  arXiv  Detail & Related papers  (2021-10-07T09:38:15Z)
• Lower Bounds for XOR of Forrelations [7.510385608531827]
  We study the XOR of $k$ independent copies of the Forrelation function. We also show that any constant-depth circuit of quasipolynomial size has quasipolynomially small advantage over a random guess.
  arXiv  Detail & Related papers  (2020-07-07T17:05:09Z)
• Quantum Communication Complexity of Distribution Testing [114.31181206328276]
  Two players each receive $t$ samples from one distribution over $[n]$. The goal is to decide whether their two distributions are equal, or are $epsilon$-far apart. We show that the quantum communication complexity of this problem is $tildeO$(tepsilon2))$ qubits when distributions have low $l$-norm.
  arXiv  Detail & Related papers  (2020-06-26T09:05:58Z)

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.