Online research in philosophy

Dynamical activities within living eukaryotic cells are organized by microtubules, main structural components of the cytoskeleton and cylindrical polymers of the protein tubulin. Evidence and theoretical models suggest that states of tubulin may play the role of “bits” in classical microtubule computational automata. The advent of quantum information devices, key roles played by quantum processes in protein dynamics, and coherent ordering in the cell cytoplasm further suggest that microtubules may function as quantum computational devices, and that mesoscopic and macroscopic quantum states are characteristic of living systems. In this paper new results from molecular dynamics simulation based on recently obtained atomic structure of tubulin are presented which provide support for classical and quantum modes of microtubule information processing.

I describe a pedagogical scheme devised to teach efficiently to computer scientists just enough quantum mechanics to permit them to understand the theoretical developments of the last decade going under the name of ''quantum computation.'' I then note that my offbeat approach to quantum mechanics, designed to be maximally efficacious for this specific educational purpose, is nothing other than the Copenhagen interpretation.

Anesthetic gas molecules are recognized to act by van der Waals (London dispersion) forces in hydrophobic pockets of select brain proteins to ablate consciousness. Enigmatic features of consciousness have defied conventional neurophysiological exp lanations and prompted suggestions for supplemental occurrence of macroscopic quantum coherent states and quantum computation in the brain. Are these feasible? During conscious (non-anesthetic) conditions, endogenous Van der Waals London dispersion forces occur among non-polar amino acid groups in hydrophobic pockets of neural proteins and help regulate their conformation/function. London forces are weak instantaneous couplings between pairs of electron induced dipoles (e.g. between adjacent non-polar amino acid groups), and are quantum mechanical effects capable of supporting quantum superposition/computation and macroscopic quantum coherence. Quantum effects mediated by endogenous London forces in hydrophobic pockets of select neural proteins may be necessary for consciousness. The mechanism of anesthetics may be to inhibit (by exogenous London forces) the necessary quantum states.

A quantum algorithm succeeds not because the superposition principle allows ‘the computation of all values of a function at once’ via ‘quantum parallelism’, but rather because the structure of a quantum state space allows new sorts of correlations associated with entanglement, with new possibilities for information‐processing transformations between correlations, that are not possible in a classical state space. I illustrate this with an elementary example of a problem for which a quantum algorithm is more efficient than any classical algorithm. I also introduce the notion of ‘pseudotelepathic’ games and show how the difference between classical and quantum correlations plays a similar role here for games that can be won by quantum players exploiting entanglement, but not by classical players whose only allowed common resource consists of shared strings of random numbers (common causes of the players’ correlated responses in a game). *Received October 2008. †To contact the author, please write to: Department of Philosophy, University of Maryland, College Park, MD 20742; e‐mail: jbub@umd.edu.

A recent attempt to compute a (recursion‐theoretic) noncomputable function using the quantum adiabatic algorithm is criticized and found wanting. Quantum algorithms may outperform classical algorithms in some cases, but so far they retain the classical (recursion‐theoretic) notion of computability. A speculation is then offered as to where the putative power of quantum computers may come from.

Combining physics, mathematics and computer science, quantum computing has developed in the past two decades from a visionary idea to one of the most fascinating areas of quantum mechanics. The recent excitement in this lively and speculative domain of research was triggered by Peter Shor (1994) who showed how a quantum algorithm could exponentially "speed up" classical computation and factor large numbers into primes much more rapidly (at least in terms of the number of computational steps involved) than any known classical algorithm. Shor's algorithm was soon followed by several other algorithms that aimed to solve combinatorial and algebraic problems, and in the last few years theoretical study of quantum systems serving as computational devices has achieved tremendous progress. Common belief has it that the implementation of Shor's algorithm on a large scale quantum computer would have devastating consequences for current cryptography protocols which rely on the premiss that all known classical worst case algorithms for factoring take time exponential in the length of their input (see, e.g., Preskill 2005). Consequently, experimentalists around the world are engaged in tremendous attempts to tackle the technological difficulties that await the realization of such a large scale quantum computer. But regardless whether these technological problems can be overcome (Unruh 1995, Ekert and Jozsa 1996, Haroche and Raimond 1996), it is noteworthy that no proof exists yet for the general superiority of quantum computers over their classical counterparts.

The intuition guiding the de…nition of computation has shifted over time, a process that is re‡ected in the changing formulations of the Church-Turing thesis. The theory of computation began with logic and gradually moved to the capacity of …nite automata. Consequently, modern computer models rely on general physical principles, with quantum computers representing the extreme case. The paper discusses this development, and the challenges to the Church-Turing thesis in its physical form, in particular, Kieu’s quantum computer and relativistic hyper-computation. Finally, the robustness of the boundary between polynomial and exponential time complexity is considered in connection with quantum computers and quantum information theory.

The nature of quantum computation is discussed. It is argued that, in terms of the amount of information manipulated in a given time, quantum and classical computation are equally efficient. Quantum superposition does not permit quantum computers to ''perform many computations simultaneously'' except in a highly qualified and to some extent misleading sense. Quantum computation is therefore not well described by interpretations of quantum mechanics which invoke the concept of vast numbers of parallel universes. Rather, entanglement makes available types of computation processes which, while not exponentially larger than classical ones, are unavailable to classical systems. The essence of quantum computation is that it uses entanglement to generate and manipulate a physical representation of the correlations between logical entities, without the need to completely represent the logical entities themselves.

In quantum computation non classical features such as superposition states and entanglement are used to solve problems in new ways, impossible on classical digital computers.We illustrate by Deutsch algorithm how a quantum computer can use superposition states to outperform any classical computer. We comment on the view of a quantum computer as a massive parallel computer and recall Amdahls law for a classical parallel computer. We argue that the view on quantum computation as a massive parallel computation disregards the presence of entanglement in a general quantum computation and the non classical way in which parallel results are combined to obtain the final output.