<p>The statement I made wasn't particularly well written. I was referring to a combination of the <a href="http://en.wikipedia.org/wiki/Margolus%E2%80%93Levitin_theorem">Margolus-Levitin theorem</a> (which gives the minimum time to move between two orthogonal states, and hence a lower bound on the time required to perform a gate) and the <a href="http://en.wikipedia.org/wiki/Schwarzschild_radius">Schwarzschild radius</a> (which gives the minimum radius of a system of some fixed energy before it forms a black hole). Combining the two of these leads to an upper bound on the number of gates which can be performed in a fixed region of spacetime. You can think of this as the maximum number of gates per unit time which can be performed.</p>

<p>The idea to combine the two theorems comes from Seth Lloyd, who uses such an approach to show limits on the computational power of the universe(<a href="http://prl.aps.org/abstract/PRL/v88/i23/e237901">link</a>). He also has another paper where he looks at the maximum performance that can be achieved by a 1kg computer of volume 1liter  (something he calls the ultimate laptop and which is almost exactly your question). See <a href="http://arxiv.org/abs/quant-ph/9908043">arXiv</a>. He obtains a limit of $10^{51}$ operations per second on $10^{31}$ bits.
Due to the finite age of the universe and the finite speed of light, when combined with Lloyd's results, you obtain a constant upper bound on preprocessing.</p>

CC BY-SA 2.5
2010-11-07T05:41:07.080Z
Just a caveat: these gates are in general quantum gates, so this upper bound is an upper bound for quantum circuits, which may not be simulable with a similarly sized classical circuit.
Joe Fitzsimons
CC BY-SA 2.5
2010-11-07T05:32:59.307Z
2010-11-07T23:02:59.960Z
2010-11-07T23:02:59.960Z
Joe Fitzsimons
<p>This question is a followup on <a href="https://cstheory.stackexchange.com/questions/2703/dna-algorithms-and-np-completeness">the question about DNA algorithms asked by Aadita Mehra</a>.</p>

<p>In comments there, Joe Fitzsimmons said, in part:</p>

<blockquote>
  <p>[T]he radius of the system must scale proportionately to the mass to avoid this. The computational power scales at most linearly in the mass. Thus your exponential amount of machinery has an exponential radius. Since you can't signal faster than light, a signal from one side to another takes an exponentially long time to reach the other side, and so if all the machinery contribute to the answer, it is impossible to solve the problem in less than exponential time.</p>
</blockquote>

<p>My question has two parts.</p>

<p>(1) What is the best way/ways to formalize a statement like, "The computational power scales at most linearly in the mass" ?  Is this statement really not up for debate?</p>

<p>(2) Suppose the statement is true.  Even so, could nature <em>already have done</em> an exponential amount of preprocessing that we might be able to make use of, for example evolution's creation of vision systems through "brute force randomization."</p>

<p>I've heard and read a fair number of soft (pseudoscientific) answers to questions of this sort, and I'd be grateful for any answers here, but I'm most interested in how (1) and (2) can be recast in TCS rigor.</p>

CC BY-SA 4.0
2020-05-06T12:24:05.183Z
I have recollection reading about a proof or a line of reasoning regarding to computational complexity and computer volume in cubic meter... maybe I have read it in the Italian translation of Бахвалов Н. С. Численные методы, 2 изд. М. 1975. i.e. "Metodi numerici" by Nikolaj S. Bachvalov . Anyone here have recollection like mine?
Alessandro Jacopson
CC BY-SA 2.5
2010-11-07T05:35:08.737Z
A possibly related question by Lance Fortnow: [what is the volume of information?](http://cstheory.stackexchange.com/questions/1593/what-is-the-volume-of-information)
Kaveh
CC BY-SA 2.5
2010-11-07T05:43:25.000Z
Seth Lloyd defines maximum computational power as the maximum number of basic quantum logic operations per second that laws of thermodynamics allow for a computer of given weight and volume. In addition to Joe's papers, here's a popular science account http://puhep1.princeton.edu/~mcdonald/examples/QM/lloyd_nature_406_1047_00.pdf
Yaroslav Bulatov
<cc.complexity-theory><quantum-computing><ne.neural-evol><physics><natural-computing>
How much computational power fits into a cubic centimeter?
Aaron Sterling
# How much computational power fits into a cubic centimeter?

(Asked by: username_0 on 2010-11-07)

This question is a followup on [the question about DNA algorithms asked by Aadita Mehra](https://cstheory.stackexchange.com/questions/2703/dna-algorithms-and-np-completeness).

In comments there, Joe Fitzsimmons said, in part:

> [T]he radius of the system must scale proportionately to the mass to avoid this. The computational power scales at most linearly in the mass. Thus your exponential amount of machinery has an exponential radius. Since you can't signal faster than light, a signal from one side to another takes an exponentially long time to reach the other side, and so if all the machinery contribute to the answer, it is impossible to solve the problem in less than exponential time.

My question has two parts.

(1) What is the best way/ways to formalize a statement like, "The computational power scales at most linearly in the mass" ? Is this statement really not up for debate?

(2) Suppose the statement is true. Even so, could nature *already have done* an exponential amount of preprocessing that we might be able to make use of, for example evolution's creation of vision systems through "brute force randomization."

I've heard and read a fair number of soft (pseudoscientific) answers to questions of this sort, and I'd be grateful for any answers here, but I'm most interested in how (1) and (2) can be recast in TCS rigor.

**Tags:** cc.complexity-theory, quantum-computing, ne.neural-evol, physics, natural-computing

> **Comments:**
> **username_2**: A possibly related question by Lance Fortnow: [what is the volume of information?](http://cstheory.stackexchange.com/questions/1593/what-is-the-volume-of-information)  
> **username_3**: Seth Lloyd defines maximum computational power as the maximum number of basic quantum logic operations per second that laws of thermodynamics allow for a computer of given weight and volume. In addition to Joe's papers, here's a popular science account http://puhep1.princeton.edu/~mcdonald/examples/QM/lloyd_nature_406_1047_00.pdf  
> **username_1**: I have recollection reading about a proof or a line of reasoning regarding to computational complexity and computer volume in cubic meter... maybe I have read it in the Italian translation of Бахвалов Н. С. Численные методы, 2 изд. М. 1975. i.e. "Metodi numerici" by Nikolaj S. Bachvalov . Anyone here have recollection like mine?  

---

## 1 answers

### Answer by username_4 on 2010-11-07. Score: 17 | Accepted answer

The statement I made wasn't particularly well written. I was referring to a combination of the [Margolus-Levitin theorem](http://en.wikipedia.org/wiki/Margolus%E2%80%93Levitin_theorem) (which gives the minimum time to move between two orthogonal states, and hence a lower bound on the time required to perform a gate) and the [Schwarzschild radius](http://en.wikipedia.org/wiki/Schwarzschild_radius) (which gives the minimum radius of a system of some fixed energy before it forms a black hole). Combining the two of these leads to an upper bound on the number of gates which can be performed in a fixed region of spacetime. You can think of this as the maximum number of gates per unit time which can be performed.

The idea to combine the two theorems comes from Seth Lloyd, who uses such an approach to show limits on the computational power of the universe([link](http://prl.aps.org/abstract/PRL/v88/i23/e237901)). He also has another paper where he looks at the maximum performance that can be achieved by a 1kg computer of volume 1liter (something he calls the ultimate laptop and which is almost exactly your question). See [arXiv](http://arxiv.org/abs/quant-ph/9908043). He obtains a limit of $10^{51}$ operations per second on $10^{31}$ bits.
Due to the finite age of the universe and the finite speed of light, when combined with Lloyd's results, you obtain a constant upper bound on preprocessing.

> **Comments:**
> **username_4**: Just a caveat: these gates are in general quantum gates, so this upper bound is an upper bound for quantum circuits, which may not be simulable with a similarly sized classical circuit.  

---

