Q: Which kind of biological system would make a good candidate for a quantum computing element and why?
Chris Fields: It is useful to pause and spend some time on what is meant by “quantum computing.” To start with, what is meant by classical computing? What Turing (1936) showed in his famous paper introducing the Turing Machine was that numbers that could be computed by any finite means, and hence values of mathematical functions that could be computed by any finite means, could be computed using one particular finite means, the Turing Machine. The Church-Turing thesis is the claim that any “computable” function can be computed using a Turing Machine. “Computable” here refers to an intuitive idea of starting with a problem, executing a finite – but maybe very large – number of well-defined operations, and reaching an answer. But what is a “problem,” what is a “well-defined operation” and what is an “answer”? These are, themselves, intuitive ideas that a theory of computability must in some sense take for granted.
One approach to the question of what “counts as” computation is to think about arbitrary physical systems and their dynamics, that is, how they change with time. Suppose you start with some system – call it S – in some well-defined state. Call that state ‘S(0)’. Now let the system behave however it behaves for some period of time, making measurements of its state every second. Call these states S(1) … S(N), where N is the numbers of seconds during which you watched the system behave. You can think of each state transition S(i) -> S(i+1) as an “operation.” Perhaps some of these operations appear to be identical; for example, perhaps the system often moves 1 cm to the left. Perhaps they all appear to be different. What counts is that there are only N – some finite number – of them.
You are now in a position to play a mischievous trick on your friends. All you need to do is to put your system S into a box, look up a table of functions that can be computed in less than or equal to N steps by a Turing machine, and then write down, for each of these functions, your own table associating Turing-machine states, in order, with the states S(1) … S(N) of S. You can now “interpret” the behavior of S, starting from S(0), as computing each of the functions that can be computed by a Turing Machine in less than or equal to N steps. To play your trick, you just need to add to S a device that reads the name of a function, consults your tables to determine the mapping from states of S to Turing Machine states for that function, starts S off in S(0), and writes on a piece of paper the ordered sequence of Turing Machine states that correspond, in your table, to the unfolding states S(1) … S(N) of S. Call S with this addition ‘S+’. You can now invite your friends to interact with the box containing S+ by giving it functions to compute and watching it compute them.
The question of interest here is: is your box-containing-S+ really computing any functions? It looks, to your friends, as if it is. They might even use it to compute functions they need computed (we’re assuming here that they aren’t very technologically sophisticated!). From your friends’ points of view, if the box-containing-S+ acts like a computer, and particularly if it is useful as a computer, then it is a computer. Your friends don’t know that the “software” inside – the tables and the “addition” that reads function names and looks up Turing Machine states – is fairly trivial. All that counts for them is whether your box-containing-S+ gets the right answer – or at least, an answer that they think looks right – and how fast it does it.
The software in your laptop is more sophisticated than the software inside the box-containing-S+, but the basic idea is similar. Your laptop’s operating system (Apple OS, Windows, Linux) enables an interpretation of physical state changes in the hardware as logical or mathematical operations in the computation of some function. Your laptop’s compiler and interpreter software (the C++ compiler, the Python interpreter, your favorite web browser) enable functions written in multiple programming languages to be so interpreted. Your laptop’s user interface software does the interpretation for you. All you have to do is type in a question, and it gives you an answer. What’s important to you is that your laptop produces answers that look right to you. You can seldom check to see if they really are right. It’s too hard.
With this understanding of classical computing, what is quantum computing? As discussed above, there are no distinct “quantum” and “classical” worlds (at least in my view). Understanding your laptop in detail – at the level of how the individual transistors work – requires quantum theory. So your laptop is a quantum system that behaves, to your eyes, as a classical computer.
Formally, a quantum computer is a computer in which Turing’s “well-defined operations” are well-defined quantum-theoretic operators. All quantum systems evolve through time under the action of well-defined quantum-theoretic operators, so all quantum systems – and hence all physical systems, to the extent that we need quantum theory to understand their behavior – are quantum computers. Indeed it has been shown that only four well-defined quantum operators are needed to define all possible quantum computations (see Nielsen and Chuang (2000), a standard textbook, for this and other details), and hence all possible behaviors of all possible quantum systems.
If all physical systems are quantum computers, how can we tell what they are computing? In some models of quantum computation, you must leave the computer alone during the entire computation; no “intermediate states” can be observed without disrupting the process. In other models, observations at specific times are permitted and hence some intermediate states can be inspected. Not surprisingly given these restrictions, quantum computation is generally viewed as useful in practice only for problems, such as factoring large numbers or searching large databases, for which the correctness of the answers can easily be checked. One still has the problem of defining, in physical terms, what counts as the “problem” – the initial state from which the quantum computer starts working – and what counts as the “answer.” How to define these in specific cases is a matter of on-going research.
What, then, makes quantum computing special? Why is it a billion-dollar business? The answer is speed. A quantum process, like an electron, simultaneously follows all possible paths from here to there. One way to think of this is that a quantum computer runs all possible algorithms in parallel to get an answer. Another way to think about it, due to Castagnoli (2016), is that a quantum computer simultaneously runs both forward in time from the problem statement and backwards in time from the answer. However you think about it, though, the benefits of quantum computing have been demonstrated – even theoretically demonstrated – for only a handful of problems, mainly problems interpretable in terms of factoring large numbers or searching large databases.
Now, finally, we are in a position to ask what kinds of biological system would make a good candidate for a quantum computing element and why? All biological systems are quantum systems, so all biological systems are quantum computers. Engel et al. (2007), for example, explicitly describe electrons moving through PS II during photosynthesis as executing Grover’s algorithm, the standard quantum algorithm for fast database search. The real question, therefore, is when is it useful to regard some biological process as quantum computation? In what circumstances does it help us to understand what a system is doing to regard it as a quantum computer? Is it useful to think of electron transport during photosynthesis as quantum computation? Is it useful to regard what enzymes or microtubules or DNA molecules are doing as quantum computation? The fairest answer right now is: maybe. No one really knows.
