Viewing a single comment thread. View all comments

nagareteku t1_j1nf075 wrote

Reply to comment by troyboltonislife in An IBM Quantum Computer Will Soon Pass the 1,000-Qubit Mark by giuliomagnifico

Nobody knows what would happen in the future, but I would guess that in very niche use cases such as the Travelling Salesman problem (TSP). For classical computers the most commonly used is the Held-Karp algorithm that solves the TSP in just O(n^(2)2^(n)) compared to the naive (n!). The best quantum exact algorithm is Ambaninis algorithm at O(1.728^(n)) found in 2019.

Quantum chips can be used to accelerate machine learning for pathfinding AI that may face the TSP, such as for location app servers and self driving cars.

15

noideaman t1_j1ngjvs wrote

Notice, you didn’t reduce complexity to polynomial switching to quantum. We still don’t know if NP-Complete problems can be solved in polynomial time on a quantum computer. If I recall, the top theoreticians think no.

8

nicuramar t1_j1nv1yn wrote

Yeah, BQP (the problem class solved by quantum computers) is generally believed to be disjunct from NPC.

2

_Asparagus_ t1_j1nkwct wrote

Ambanini's algorithm will almost certainly never be used practically. It relies on Grover search to achieve its speedup, which has been basically shown to not be practical in the foreseeable future (see here for example. Held-Karp isn't used in practice either, since the exponential complexity is detrimental very quickly, and instead heuristics are used (this usually for example what popular software like Gurobi does). So extremely unlikely that TSP will be something quantum will help us with

3