Quantum Computational Equivalence

6 responses to “Quantum Computational Equivalence”

1. 

   Anonymous

   Aug 23, 2004 at 11:03 am

   Steve,

   Your comment about quantum computing and Wolfram's Principle of Computational Universality is actually quite astute. It ties in with a more general limitation of Wolfram's principle, which I have described in a section of my review of his book. Check out the section on "Strong and Weak Computational Universality" in

   http://www.goertzel.org/dynapsyc/2002/WolframReview.htm

   Basically, the fatal flaw in his universality principle is that he doesn't consider issues of computational efficiency (in either the space or the time domains). So what if a CA can display every possible complex phenomenon that a brain, if it takes a billion years and a CA the size of Andromeda to do so? So what if the brain can in principle display every complex phenomenon that a superhuman AI can — if it will take 47 times longer than the expected countdown to the Big Crunch to do so, and will require an external memory source 98.6 times larger than the size of the universe?

   Deutsch showed that quantum computers can't compute anything going beyond ordinary Turing computable functions — but they can compute some things a lot faster. This means that, in principle, a classical computer — or a brain, or a CA, or whatever — could display the same funky complex patterns as a quantum computer. But it might take, oh, 10^777 times longer and require 888^888 times more memory 😉 Does this make a difference to you? It seems not to make a difference to Wolfram.

   One perspective is to dismiss concerns about efficiency as quibbles, but in fact I think they're central. In my view the assessment of simplicity in space and time is just about the most basic thing in the metaphysics of intelligence — as well as obviously being critical from a practical perspective. As Eric Baum has argued in his recent book "What Is Thought?" (which I also have some problems with, but which is significantly more sensible, though less inventive, than Wolfram's book), it's the principle of Occam's Razor that allows minds with limited physical resources to achieve reasonable amounts of intelligence. Occam's Razor is all about making estimates of computational efficiency.

   As a somewhat related aside, I have been very entertained lately by Saul Youssef's papers on quantum probability theory. It seems that you can derive basic quantum mechanics from the sole assumption that probability values are not real numbers but rather complex numbers. Funky, huh? Alas, my practical work trying to create a thinking machine and decode cell dynamics and so forth doesn't leave me time to do so, but I think it would be possible to create a new theory of *probabilistic reasoning* using complex-valued probabilities rather than the ordinary real-valued ones. This would be very interesting, and might be a way of formalizing the "logic" that would be used by a quantum-computing-based intelligent mind (unlike Penrose and some others, I don't believe that the human brain is a quantum computer in any strong sense, although I do think it's possible that macroscopic quantum effects have some effect on brain dynamics).

   Well, I think I rambled on a bit here — sorry, it's early morning and my brain is still partially in the zone of dreams — but I believe I've answered your question, at least by pointing you to my prior review that addressed a similar point 😉

   Cheers,
   Ben Goertzel
   ben@goertzel.org

   Reply
2. 

   Antoine Vekris

   Aug 25, 2004 at 9:55 am

   My genome may be smaller then Microsoft Office, and more important, my cells nuclei are much smaller then the CD where my genome could be stored, if someone had the opportunity to sequence it.
   But if the variants of expression per differentiated cell type I have all over my body, and those specialized cells in my thymus playing combinatorial molecular biology to ensure the availability of convenient antibodies should be store in a CD-like physical support you should use a fortune to pay for them, even using a strong compression algorithm.
   If you expand the "genetic material" to RNAs, then you will need some more space to take in account RNA splicing and editing. Then at the protein level, where most of the genetic material express itself the data to be stored are just HUGE. I wonder what would be the volume of DVDs necessary to store proteins configuration changes following chemical alterations, maturation/activation by cleavage etc.
   And this is the point where I would stop and compare with a software suite. Not just the code vs DNA.

   Reply
3. 

   Steve Jurvetson

   Aug 27, 2004 at 2:21 am

   Good to see you here Old Cola.

   If you include the extra genetic code (mitochondrial DNA and even symbionts like E.Coli), the size comparison still holds since they are relatively tiny. I think your comment hits at the core of the Your Genome is Smaller than Microsoft Office post.

   It seems to me that the physical instantiation and the unpacked complexity are central to the original question: “What does this tell us about complex systems development in general?” I think the code compactness and degree of code (and subsystem) reuse across diverse organisms draws a sharp contrast between the seed vs. feed developmental approaches.

   The code alone does not begin to explain the complexity of regulatory gene feedback, protein interactions, metabolism, or the iterative application of physical, chemical and electrical feedback in “expanding” the code.

   It’s like the Mandelbrot fractal sets or , cellular automata rule 30. Each are uniquely captured in a single line of code (or a single number), and each unpack with an iterative interpreter into a visual display of beauty. Applying each rule a trillion times to create a visual display of a trillion pixels could be said to be a trillion bits of code. They are different levels of instantiation and different levels of abstraction. In these systems, a single line of code can iterate into massive “data sets” when looked at from the end product perspective.

   Our software traditions are very different. Microsoft Office is more likely to include a space-hogging library of clip art than the seed code to create beauty.

   Reply
4. 

   Dimitar Vesselinov

   Sep 13, 2004 at 7:30 pm

   Stephen Wolfram: A New Kind of Science

   "For three centuries scientists have looked to mathematics to understand how nature works — and to create the foundations for technology. But based on his surprising discoveries about simple computer programs, Stephen Wolfram, creator of Mathematica and author of A New Kind of Science, has developed a radically new approach. From the IT Conversations and SDForum Distinguished Speaker Series."

   http://www.itconversations.com/shows/detail202.html

   Reply
5. 

   Anonymous

   Sep 3, 2007 at 3:44 am

   I am not versed in computer science, let alone, quantum computing. Notwithstanding, please allow me these thoughts. "Quantum computers can perform accurate simulation of any physical system of comparable complexity," if and only if that physical system can be reduced to precise mathematical representations. Some physical systems can be easily represented. Others cannot not. Perhaps quantum computers initial task should be to characterize these very complex physical systems in order to predict how they behave in nature. Moreover, if algorithms can be derived from this process, than perhaps classical computers, can indeed, solve such questions. I do not believe quantum physics and classical physics are mutually exclusively. Until we establish that relationship, quantum computing may be genuinely limited. The questions that are being proposed, the existence of parallel universes, and such, surely do not, merely exist, if in fact they do exist, only in the quantum realm of understanding. As such, I am suggesting that quantum computers, must, of necessity work synchronously with classical computers in order to model reality and predict how physical systems operate in nature.

   Reply
6. 

   Anonymous

   Sep 3, 2007 at 3:52 am

   I am not versed in computer science, let alone, quantum computing. Notwithstanding, please allow me these thoughts. "Quantum computers can perform accurate simulation of any physical system of comparable complexity," if and only if that physical system can be reduced to precise mathematical representations. Some physical systems can be easily represented. Others cannot. Perhaps quantum computers initial task should be to characterize these very complex physical systems in order to predict how they behave in nature. Moreover, if algorithms can be derived from this process, than perhaps classical computers, can indeed, solve such questions. I do not believe quantum physics and classical physics are mutually exclusively. Until we establish that relationship, quantum computing may be genuinely limited. The questions that are being proposed, the existence of parallel universes, and such, surely do not, merely exist, if in fact they do exist, only in the quantum realm of understanding. As such, I am suggesting that quantum computers, must, of necessity work synchronously with classical computers in order to model reality and predict how physical systems operate in nature.

   Reply