> Huh yeah I guess I need to learn more. My layman’s assumption was that it would help with a lot of NP problems that involved recursion or backtracking algorithm would benefit from it.
Recursion is more of a property of how you write your algorithm, than of the problem.
Eg Scheme or Haskell as languages have no built-in facilities for iteration, no for-loops, no while-loops; the only thing you get is function calls. (Well, that and exceptions etc.)
However you can built for-loops as libraries in both Scheme and Haskell. But they will be built on top of recursion.
To make matters even more interesting: once you compile to native code, all the recursion (and also all the for-loops and other fancy 'structured programming' constructs) go away, and you are back to jumps and branches as assembly instructions.
None of this changes whether a given class of problems is in P or NP or (almost!) any other complexity class. Just like getting a faster computer doesn't (usually!) change the complexity class of your problems.
> I could totally see the argument that they are physically impractical and therefore not likely to be actually used vs parallelizing conventional computers.
Quantum computers are impractical now. But as far as we can tell, that's "just" an engineering problem.
In the long run one of two things will happen:
- Either engineering improves and we will be able to build good quantum computers (though perhaps still not better than classical computers for the same amount of effort)
- Or, we discover new principles of quantum mechanics.
Basically, quantum mechanics is one of our most successful physical theories, if not the most successful theory. And as far as we understand it, it allows quantum computers to be built.
So either we will eventually manage to built them, or (more excitingly!) that's not possible, and we will discover new physics that explains why. We haven't really discovered new physics like that in a while.
Recursion is more of a property of how you write your algorithm, than of the problem.
Eg Scheme or Haskell as languages have no built-in facilities for iteration, no for-loops, no while-loops; the only thing you get is function calls. (Well, that and exceptions etc.)
However you can built for-loops as libraries in both Scheme and Haskell. But they will be built on top of recursion.
To make matters even more interesting: once you compile to native code, all the recursion (and also all the for-loops and other fancy 'structured programming' constructs) go away, and you are back to jumps and branches as assembly instructions.
None of this changes whether a given class of problems is in P or NP or (almost!) any other complexity class. Just like getting a faster computer doesn't (usually!) change the complexity class of your problems.
> I could totally see the argument that they are physically impractical and therefore not likely to be actually used vs parallelizing conventional computers.
Quantum computers are impractical now. But as far as we can tell, that's "just" an engineering problem.
In the long run one of two things will happen:
- Either engineering improves and we will be able to build good quantum computers (though perhaps still not better than classical computers for the same amount of effort) - Or, we discover new principles of quantum mechanics.
Basically, quantum mechanics is one of our most successful physical theories, if not the most successful theory. And as far as we understand it, it allows quantum computers to be built.
So either we will eventually manage to built them, or (more excitingly!) that's not possible, and we will discover new physics that explains why. We haven't really discovered new physics like that in a while.