Computing in Science & Engineering

The physical limits of computing

Michael P. Frank

Published May 1, 2002• 84 citations

Abstract

Many of the fundamental limits on information processing, from thermodynamics, relativity, and quantum mechanics, are only a few decades away. Novel physically motivated computing paradigms, such as reversible computing and quantum computing, may help in certain ways, but even they remain subject to some basic limits. One can arrive at several firm conclusions regarding upper bounds on the limits of computing. In this article, the author only reviews the fundamental technology-independent limits.

DOI: 10.1109/5992.998637

Related papers

Quantum mechanical computers with single atom and photon fields

Kazuhiro Igeta, Y. Yamamoto

The physical foundation of a computer, specifically, the thermodynamic and quantum mechanical limits, has been an interesting theoretical subject for many years. The uncertainty relation between information and energy, exemplified by Maxwell’s demon1), suggests that there exists a fundamental limit on minimum energy cost per unit of information processing. The most important development in this field in the last ten years has been a reversible logic proposed by Fredkin and Toffoh2).

Jul 18, 19887 citations

Quantum mechanical computation

James D. Brasher

The physics and the mathematics of computation are examined to provide a foundation and perspective for the investigation of the quantum mechanics of computation. Our purpose is to explore the fundamental limits and constraints imposed on computation by Nature through the laws of physics and the mathematics of computational complexity. Inasmuch as information storage and transmission are an integral part of computation, their physical bounds are considered. The computer is viewed both physically and mathematically as a dynamical system, and is depicted in terms of the basic Turing machine paradigm. Three fundamental classes of the Turing machine are defined; the deterministic, stochastic and quantum Turing machines. Hamiltonian models and physical realizations of quantum computing are described. Quantum computers can perform some tasks which have no classical analogue, but they cannot compute functions that are non-computable by classical means. Some classically intractable problems can be solved with quantum computers.

Proceedings of SPIE, the International Society for Optical Engineering/Proceedings of SPIEMar 1, 19940 citations

Limits on Efficient Computation in the Physical World

Scott Aaronson

More than a speculative technology, quantum computing seems to challenge our most basic intuitions about how the physical world should behave. In this thesis I show that, while some intuitions from classical computer science must be jettisoned in the light of modern physics, many others emerge nearly unscathed; and I use powerful tools from computational complexity theory to help determine which are which.

arXiv:quant-ph/0412143Dec 20, 200425 citations

Implementing the Asynchronous Reversible Computing Paradigm in Josephson Junction Circuits.

Michael P. Frank

An important figure of merit for practical computing systems is energy-delay efficiency, which characterizes the number of operations a given device can perform per unit energy dissipated, per unit time taken for the operation.This efficiency metric appears to be limited in existing superconducting logic styles, motivating the search for novel, potentially more efficient forms of superconducting logic.One path to improving efficiency might be if we could remove the need for external control driven by slow clocks that is present in existing adiabatic SCE logic styles such as AQFP/RQFP.The Asynchronous Ballistic Reversible Computing (ABRC) paradigm offers an alternative model for ballistic, data-driven reversible computation.In an ongoing project at Sandia, we are attempting to demonstrate how the ABRC model can be implemented using Josephson junction circuits, while minimizing the energy-delay product.In this talk, we review the progress that has been made to date in this effort.An interesting direction for future research is to design physical mechanisms that explicitly invoke quantum processes exhibiting superadiabaticity (a.k.a."shortcuts to adiabaticity") to improve energy-delay efficiency in concrete computing technologies.We briefly review what is known about the potential applicability and limits of this approach.Dissipation-delay Efficiency (DdE) Sandia National Laboratories • The key motivating Figure of Merit (FOM) in the present study.• For a single primitive transition of the digital state of a system between two distinct informational states, consider:• The energy dissipation D incurred by that transition process.Relates to costs associated with supply of energy and cooling.• The delay d, defined as the time interval from start to end of process.Relates to costs associated with achieving a given level of parallel performance.• Then define the dissipation-delay product DdP = D • d.• Note that since refers specifically to energy dissipation, not to energy invested in the signal, in reversible processes, it is not subject to the "quantum speed limit" (QSL) lower bound of -h!No fundamental lower bound to DDP is yet known!-In fact, it would be identically zero for any perfectly-known unitary time-evolution.• Of even more general interest than DdP per se is dissipation as a function of delay, D(d), considered over a range of practical (tolerable) delay values... We'd like to extend the pareto frontier of this function within the useful range.• Dissipation-delay efficiency (DdE) of a computing technology just refers to the reciprocal of DdP, r/Dd = (Dd)-i.

Jul 29, 20201 citation

Quantum computers

David Deutsch

Abstract A number of research programs with widely different motivations have, during the last few years been coming to a conclusion that is startling to some, and which others say they have suspected all along: that the theory of computation is connected at many levels, including the most fundamental, to physics. In particular it has connections with our deepest and most powerful physical theory, quantum theory.

ITNOWJun 1, 19870 citations

The nonequilibrium cost of accurate information processing

Giulio Chiribella, Fei Meng, Renato Renner +1 more

Accurate information processing is crucial both in technology and in nature. To achieve it, any information processing system needs an initial supply of resources away from thermal equilibrium. Here we establish a fundamental limit on the accuracy achievable with a given amount of nonequilibrium resources. The limit applies to arbitrary information processing tasks and arbitrary information processing systems subject to the laws of quantum mechanics. It is easily computable and is expressed in terms of an entropic quantity, which we name the reverse entropy, associated to a time reversal of the information processing task under consideration. The limit is achievable for all deterministic classical computations and for all their quantum extensions. As an application, we establish the optimal tradeoff between nonequilibrium and accuracy for the fundamental tasks of storing, transmitting, cloning, and erasing information. Our results set a target for the design of new devices approaching the ultimate efficiency limit, and provide a framework for demonstrating thermodynamical advantages of quantum devices over their classical counterparts.

arXiv:2203.09369Nature CommunicationsNov 22, 202219 citations