Quantum Computational Equivalence
I recently heard Wolfram present his notion of "computational equivalence", and I asked about quantum computers because it seemed like a worm hole through his logic… but he seemed to dismiss the possibility of QCs instead.
The abstract summary of my understanding of computational equivalence is that many activities, from thinking to evolution to cellular signaling, can be represented as a computation. A physical experiment and a computation are equivalent. For an iterative system, like a cellular automata, there is no formulaic shortcut for the interesting cases. The simulation is as complex as “running the experiment” and will consume similar computational resources.
Quantum computers can perform accurate simulations of any physical system of comparable complexity. The type of simulation that a quantum computer does results in an exact prediction of how a system will behave in nature — something that is literally impossible for any traditional computer, no matter how powerful. Professor David Deutsch of Oxford summarizes: “Quantum computers have the potential to solve problems that would take a classical computer longer than the age of the universe.”
So I wonder what the existence of quantum computers would say about computational equivalence? How might this “shortcut through time” be employed in the simulation of molecular systems? Does it prove the existence of parallel universes (as Deutsch concludes in Fabric of Reality) that entangle to solve computationally intractable problems? Is there a “quantum computational equivalence” whereby a physical experiment could be a co-processor for a quantum simulation? Is it a New New Kind of Science?