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. From some quick googling it seems like they have already designed QC algorithms for traveling salesman etc. Isn’t that sort of meaningful or am I missing something?
I could totally see the argument that they are physically impractical and therefore not likely to be actually used vs parallelizing conventional computers.
Well they are physically impractical now, but they might get practical in the future.
But no, I'm fairly sure that QC in general isn't known to be able to solve NP problems. And since Traveling Salesman is NP complete (iirc), I don't think there's a QC alg to solve traveling salesman in P (otherwise that would imply QC would solve all of NP in P, which I know isn't true). Where did you see indication otherwise?
FWIW, my favorite CS blogger is Scott Aaronson, and the subtitle of his blog has always been: "If you take nothing else from this blog: quantum computers won't
solve hard problems instantly by just trying all solutions in parallel." This reflects the very common misunderstanding of how QC works.
Hah ok point taken. Here’s the paper I found about traveling salesman - looks like a version of Grover’s algorithm so I think that means it provides a speed-up but not polynomial time? Paper is paywalled: https://link.springer.com/article/10.1134/S1063776123080095#....
> 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.
I could totally see the argument that they are physically impractical and therefore not likely to be actually used vs parallelizing conventional computers.