What is the next step beyond quantum computation?

Question

Assuming we develop quantum computers one day, what would be theoretically the next step? Would it be string-theory based computers? How would these computers differ performance-wise (ie what can they possibly do that Quantum Machines cannot)

Answer 1

Although in one sense this question and answer is altogether beyond physics, (as discussed below) there would seem to be a very natural answer to this question, to wit:

Beyond Quantum Computers are computers than can overcome the Church-Turing thesis (See the Wikipedia page with this name) and, more generally, can compute the truth value of propositions that are undecidable by a finite computation, or, equivalently, underivable in a finite number of steps from a fixed axiom system. The latter are commonly (and somewhat cheekily, IMO) called "Oracles" (see the Wikipedia page for "Oracle Machine") by computer scientists, logicians and other researchers into the foundations of mathematics.

The Position of Mainstream Physics on Oracle Machines

As far as I know, there is as yet no serious question as to whether the class of problems solvable by quantum computers might be bigger than the class solvable by deterministic, Turing machines. Indeed it seems that mainstream physics believes that computers transcending the CT thesis are likely to be outside physics (see this Physics SE question Church-Turing hypothesis as a fundamental law of physics). I think most workers in this field would believe, on the evidence so far that quantum computers will not overcome the Church-Turing thesis, i.e. that no algorithm "implemented in any physical computer" can compute anything that a classical Turing machine cannot in principle (the bit in quotes is my addition to the wonted statement of the CT thesis). Note that I say in principle: the serial sequences of Turing state machine states that make up many computations are so fantastically long that no classical computer could do them in the life span of a physical universe complying with known physical laws. Quantum computers may change all that and bring many computations formerly thought forbiddingly complex for any practical solution into the doable realm. So the factors that may set quantum computers apart from classical ones are:

1. Massive storage arising from the tensor product of quantum states: an $N$ qubit state lives in a vector space of $2^N$ quantum basis vectors, so even if we use only two digital levels of superposition weight for each separate basis vector in a general quantum superposition, the finite state space stores $2^N$ bits or has $2^{2^N}$ distinguishable states;
2. Extremely low power consumption: quantum state evolutions are unitary therefore reversible therefore do not consume energy by Landauer's principle, although there will be energy required to initialize qubits when the computer first powers up, in accordance with Landauer's principle;
3. Massive speed arising from massive parallelism inherent in the evolution of quantum state-represented computation space;

But transcending the Church-Turing thesis so far does not seem to be an attribute of quantum computing.

Speculative Futures Grounded on Yet-To-Be-Discovered Physics

Now, mainstream physics has no concept of how an oracle machine - effectively something that can do an infinite number of computing steps in a finite time - might be implemented, so in this sense your question is altogether beyond physics. However, if the standpoint taken by strong mathematical platonists such as Gödel was is the right one (a more extreme view still is Mark Tegmark's Mathematical Universe Hypothesis) then it is conceivable (but still not needful, mind you) that such oracles are physically realizable in some as yet unknown physics. To give some idea of how fantastical that is: if we indeed developed such technology, the observation of true infinities in the laboratory would become a commonplace, everyday idea!

What Current Physics has to say about the limits of Oracle Machines

Even if this thinks about yet to be discovered (if at all valid) physics, there are a few things we can say about an oracle machine or other computer transcending the Church-Turing thesis, mainly grounded on thermodynamics and Landauer's principle:

1. It would have to be contained in a finite memory space: the initialization of $N$ bits of memory (whether classical or qubit) calls for, in accordance with Landauer's principle, the expenditure of useful work $N\,k_B\,T\,\log 2$. So if our speculative physics is still constrained by present thermodynamics, the oracle machine must have finite energy needs and therefore it must be contained in a bounded memory;
2. Interestingly, once we have initialized this memory, the running of an infinite number of reversible steps on such a computer may not need an infinite amount of energy. Contrapositively, any non-reversible oracle algorithm cannot be implemented because its energy needs would be infinite owing to the need to erase memory and Landauer principle attendant need for energy each time an irreversible erasing happened.

Of course, in General Relativity there is no global energy conservation, so there may even be speculative speculative physics not subject to the above restrictions!

Examples of Undecidable Propositions, i.e. Those Needing Oracles for Decision

Since you ask this question, I assume that the idea of undecidable and unncomputable propositions is unwonted to you. So begin by looking up:

1. The Halting Problem on Wikipedia: the proof is simple and given there: it can be proven impossible to decide with a Turing machine whether any general computer program will end normally or get stuck in an infinite loop;
2. The computation of Kolmogorov Complexity: again see this one, with proof of the following statement, on Wikipedia: roughly: there is no algorithm that can decide whether a full specification of an object might be made smaller and still be a full specification. This is a mathematically rigorous variation on the Berry Paradox.
3. Gödel undecidable propositions: roughly: that there are always relationships between the natural numbers whose truth or falsehood cannot be decided by a Turing machine.
4. One that I like (more in keeping with what I would think of as my background) is the Novikov–Boone theorem that one cannot decide by Turing machine whether two words in a finite group presentation are talking about the same group element or not;
5. Chaitin's constant and uncomputable numbers and undefinable real numbers (that's "most" of them, insofar that the computable ones are countable!) in general.

Most of these problems involve computing something by the Cantor slash procedure (the procedure used to show that $\mathbb{R}$ is uncountable) so I'll give a flavor of them as follows by showing the existence of uncomputable function (the proof of uncomputability of Kolmogorov complexity stands out as a little different from this technique - see the Wiki page). Suppose we have a computer language. Now we list all syntactically valid programs in order of their Gödel number (we can take this to be the code's "value" as a string of ASCII digits). This list is clearly in one-to-one onto correspondence with the positive integers. We then pick the programs that compute one integer function of one integer variable and put these in a condensed list: these too are clearly a list that can be put into bijective correspondence with the positive integers. Then we throw out all the ones that do not halt (we cannot actually do this by the unsolvability of the halting problem but the countable list exists) so we are left with a countable list $\{f_i:\mathbb{N}\to\mathbb{N}\}_{i=1}^\infty$ of computable, integer valued integer functions. These include every such function that can be computed in that particular computer language. So now we consider the function:

$$f:\mathbb{N}\to\mathbb{N}:\;f(x) = f_x(x) + 1$$

and readily show that it is not on the list ($f_x(x) \neq f_x(x)+1 = f(x)$). So we would have to extend our computer language to compute this function. But then our new language would also have uncomputable functions, by precisely the same argument.

Answer 2

You might be interested in this paper, NP-complete problems and Physical Reality, by Scott Aaronson. It doesn't discuss the next step "after quantum computers" per se, but compares the computational power of various physical theories. It surveys newtonian physics, nonrelativistic quantum mechanics, nonlinear corrections to QM, hidden variable theories, special relativity, quantum gravity, general relativity, and the many-world interpretation.

For example, section 5 (on page 7) examines what happens if quantum mechanics were not strictly linear (answer: if we could perform computations without errors, we could solve NP-complete problems in polynomial time; whether this can be done in a fault-tolerant manner is unknown).

The idea is to implement something like Grover's search algorithm. Suppose we are given a black-box function $f : {0,1}^n \to {0,1}$ and we want to find an input $x$ such that $f(x) = 1$. Using $n$ qubits we can form a superposition over all $2^n$ input states and evaluate $f$ on it so we have the state $\sum_x |x\rangle |f(x)\rangle$; the problem now is that the "answer states" we want, where the last qubit $|f(x)\rangle$ has value $1$, might be in superposition with about $2^n$ "non-answer states". Grover's algorithm amplifies the difference between these states in $O(2^{n/2})$ steps, but this is the best we can do because time evolution in QM preserves the angle between states. In non-linear QM, this restriction is removed and we can potentially amplify the difference much faster.

Section 8 discusses the computational power of closed timelike curves, or time travel, which after all satisfy all the laws of general relativity. Specifically, some people have tried to resolve the grandfather paradox by saying that only consistent histories are allowed; then the idea is to arrange matters so that finding a consistent history, which the universe does for us "for free", also happens to solve a very hard problem, for instance $\text{3SAT}$.

The part that addresses your question most directly is the section on quantum gravity, but unfortunately, it is also the section that contains the least number of concrete results.

Answer 3

This issue is considered, directly or indirectly, in other questions in physics.SE.

The question Church-Turing hypothesis as a fundamental law of physics is nearly the converse of the question asked here and my answer raises the possibility that physics could allow other computational models, oracle machines being one of them.

Then answering Final theory in Physics: a mathematical existence proof?, I raise the issue that, precisely for computational reasons, it is not obvious to know what could be a Theory of Everything (covering all of physics). I tried to pursue this point by asking myself the question What is a Theory of Everything (TOE)?.

Similar points wre also adressed in an older question Does Gödel preclude a workable ToE?.

There is actually technical research trying to assess the physical limits of calculability. For example,

several researchers [...] have pointed out that quantum theory does not forbid, in principle, that some evolutions would break the physical Church-Turing thesis.

I will not repeat the detailed content of the other answers. It seems that a major issue limiting computability is the denumerable character of our mental activities and theories, all based on language, on syntax. We can talk about non denumerable entities, like real numbers, but we cannot show them, except for some of them through denumerable devices ("it is the root of this equation"), and that has limitations.

Some of the research has gone into assessing what property of the physical universe could impose a similar limit on computability. One such property would be a limitation of information density in space-time, which they seem to believe compatible with existing physics. Various devices may be considered to make the equations of physics compatible with denumerability, such as the use of computable reals, that allow developing a form of calculus with denumerable numbers, though noy without limitations.

There is also the possibility that physics will allow going beyond the Church-Turing limitation. This in itself may have deep implication on our way of developping the theories. Axiomatic mathematics that are used to build physical theories are fundamentally based on denumerability. From the axioms, we can enumerate theorems, essentially with a Turing machine. Could it be that more powerful models of computation would open the door to a different approach at formalizing mathematics and physics. Another way of seeing it is the Curry-Howard isomorphism that associates theorem proofs and computer programs. If new computing models existed, would they correspond to new ways of proving mathematical resualts.

Or conversely, could it be the case that our confinement in denumerable discourse would prevent us from perceiving alternatives existing in the physical world.

On a less ambitious scale, there is the possibility that some physical phenomenon could move the complexity barriers, as quantum computing seems able to do it. This in itself is a feat that would be hard to dream of if we did not know quantum mechanics. So physics may have other surprises in store.