News for hackers. Stuff that matters.

A comment on New silicon structure opens the gate to quantum computers. Parent comment

Re:New silicon structure opens the gate to quantum computers by visarga on Wednesday December 13, 2017 @05:01AM (#15913258)
> The traveling salesman problem is NP-complete and therefore not known to be solvable in less time on a quantum computer.

That's only a problem if you need the exact solution. If you're OK with 99.9% quality, approximate solutions are much cheaper. So the question is, is it necessary to invest into that 1%?

[ Parent | on HN ]
Re:New silicon structure opens the gate to quantum computers by monob on Wednesday December 13, 2017 @05:20AM (#15913328)
Do you have a paper on approximating NP complete problems and the bounds on the error in the solution?
[ Parent | on HN ]
Re:New silicon structure opens the gate to quantum computers by CJefferson on Wednesday December 13, 2017 @05:15AM (#15913307)
It's unclear a quantum computer can find you an approximate solution any faster either.
[ Parent | on HN ]
Re:New silicon structure opens the gate to quantum computers by jcoffland on Wednesday December 13, 2017 @12:56PM (#15915944)
That has nothing to do with quantum vs. classical.
[ Parent | on HN ]
Re:New silicon structure opens the gate to quantum computers by visarga on Wednesday December 13, 2017 @11:51PM (#15920020)
Approximate solutions have to do with solving problems with limited resources and scaling up. Quantum computers will be fast at solving certain types of problems, while approximate solutions are fast at solving practical problems.
[ Parent | on HN ]