22
$\begingroup$

This question is a followup on the question about DNA algorithms asked by Aadita Mehra.

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.

$\endgroup$
  • 2
    $\begingroup$ A possibly related question by Lance Fortnow: what is the volume of information? $\endgroup$ – Kaveh Nov 7 '10 at 5:35
  • 1
    $\begingroup$ 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 puhep1.princeton.edu/~mcdonald/examples/QM/… $\endgroup$ – Yaroslav Bulatov Nov 7 '10 at 5:43
17
$\begingroup$

The statement I made wasn't particularly well written. I was referring to a combination of the Margolus-Levitin 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 (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). 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. 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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Joe Fitzsimons Nov 7 '10 at 5:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.