I read something about that locating our space in the multitude of multidimensional spaces of M-theory (and so identifying particular particles which we can measure with particular strings) is a too hard problem for us to solve; so we cannot experimentally verify M-theory.

I have also heard that quantum computers can solve some NP problems.

May quantum computers help us to locate our space in M-theory?

What is our hope to verify M-theory?

  • 7
    $\begingroup$ Quantum computers are not known to be able to solve NP-hard problems. $\endgroup$ – Norbert Schuch Aug 24 '15 at 22:34
  • $\begingroup$ @NorbertSchuch I asked once whether quantum computers would break Internet encryptions (namely HTTPS and PGP) and received an affirmative answer. So, I am unsure whether to believe you or them $\endgroup$ – porton Aug 24 '15 at 22:35
  • 3
    $\begingroup$ Many encryption schemes are based on factoring, which (i) can be solved by a quantum computer but (ii) is not known to be an NP-hard problem (and most likely isn't). $\endgroup$ – Norbert Schuch Aug 24 '15 at 22:36
  • $\begingroup$ @porton You're probably getting confused between a problem being in NP and in NP-hard. NP-hard means that the problem is at least as hard as the hardest problem in NP. Or to put it another way: any NP problem may be reduced to an NP-hard problem with a polynomial overhead. Quantum computers can solve some problems in NP in polynomial time but have not been shown to be able to solve (and probably can't) any NP-hard problem in polynomial time. $\endgroup$ – or1426 Aug 24 '15 at 22:38
  • $\begingroup$ @or1426 Yes, I confused these two classes of problems $\endgroup$ – porton Aug 24 '15 at 22:39

The immediate problem with locating our space in the string theory landscape today, is that even if you pick just one definite background geometry (definite shape for the extra dimensions, etc), you will not be able to calculate particle masses and other measurable quantities. The calculations are too difficult and there are too many unknown aspects of the theory.

At this time, when people look for string "vacua" that might be the real world, they first filter the possibilities through qualitative constraints. An elementary example of such a constraint, is that we observe three dimensions of space. But what the professional physicists actually want, is something that will give the symmetry groups and particle multiplets that have been observed in high-energy physics.

The governing paradigm here is "grand unification", the identification of a single symmetry group which has the symmetries of the known forces as subgroups. This was already the mainstream of particle physics before the modern wave of string theory (beginning in 1984). So realistic string-theory model-building consists of identifying string vacua in which the strings become matter fields interacting according to unified gauge forces like SU(5) or SO(10), that can then be broken to the standard model forces by Higgs effects.

There would be thousands of string vacua known which satisfy that description, I think. But to really test them, either you need some completely new effect, like a new particle state with nonstandard charges, or you need to be able to calculate e.g. the exact masses of the particles in these vacua which are analogous to the electron, the top quark, and so on - so as to determine whether they are the electron, top quark, etc of the real world.

And that is simply not achievable at this point. People get excited e.g. if they have a model in which one of the "quarks" is much heavier than all the others (resembling the relationship of the top quark to the other quarks in the real world). You might demonstrate that by showing that in this model, the coupling of the "top quark" to the electroweak Higgs field is approximately 1, and that the couplings of the other "quarks" are approximately 0. Even that much can require sophisticated algebraic and geometric reasoning, and it can be easy to miss an interaction effect that would spoil those numbers.

I think we can expect this situation to improve, in a way it improves every year as new conceptual and calculational discoveries are made in the field, but we never know ahead of time how big those advances will be. Progress in string cosmology might single out part of the landscape as the place to look. Some special feature of the standard model might turn out to have very restrictive implications, again implying that only a very narrow set of vacua are worth considering. New branches of string theory might be discovered, expanding the landscape. Progress in higher mathematics might dramatically simplify the task of calculating the predicted masses to high precision.

So it's hard to say what is the real computational complexity of "searching the string landscape for the real world". At the moment, we don't have a proper algorithm for doing so, except at the qualitative level - people do write programs to search a section of the landscape for vacua containing promising grand unified models. If we knew the full extent of the landscape, and if we knew how to derive the detailed predictions for a specified vacuum, then looking for the real world could be fully automated. But string theory still contains many open problems, the solution to which could dramatically affect the difficulty of such a search.

Despite the highly unfinished nature of the theory, a few string theorists have written papers trying to guess how hard the search for the real world is. Those papers are probably the source of the idea that the search is NP-hard. But it's just a guess. There are many problems in computer science where your first idea of how to solve it is computationally very expensive, but then there's some much better algorithm that is much more efficient. Then there are problems which do appear to be intractable for all practical purposes. To say that the search for the real world in the string landscape is in the second category, is just a guess, and in my opinion not a very convincing one, because we still have a lot to learn about the math of string theory, and because we haven't yet applied all the facts we know about the real world, in order to narrow down the search space of vacua.


Now we have the confusion about complexity classes sorted out (at least somewhat). Do you have any reason to suggest that the problems or M-theory have an algorithmic solution which is either NP, NP-hard or any complexity class you like? I seriously doubt there exists any algorithm which would be able to "locate our space in m-theory".

Additionally it may be worth pointing out that those algorithms where quantum computation provides a speed up over classical generally have a very "nice" mathematical structure to them. Prime factorisation of natural numbers is the prime example here which (in addition to Shor's famous algorithm) has a huge amount of beautiful number theory around it and prime numbers in general.

  • $\begingroup$ Quantum computing provides a speedup for almost all types of problems at least quadratically through Grover's search. $\endgroup$ – user168013 Sep 11 '18 at 12:44

Not the answer you're looking for? Browse other questions tagged or ask your own question.