Submitted by **giuliomagnifico** t3_zuxy0d
in **technology**

#
**troyboltonislife**
t1_j1n1pa7 wrote

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

will this be used for machine learning at all? can these computers do the linear algebra used in machine learning?

#
**nagareteku**
t1_j1nf075 wrote

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.

#
**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.

#
**nicuramar**
t1_j1nv1yn wrote

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

#
**_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

#
**troyboltonislife**
t1_j1nlb5y wrote

is held karp an approximation or does it solve it fully?

#
**_Asparagus_**
t1_j1njvo6 wrote

No, it won't. ML applications of anything quantum are extremely limited, especially in this regime of qubit numbers.

#
**troyboltonislife**
t1_j1nllvd wrote

I guess I am not fully understanding of what calculations these computers are good for? I guess I thought they would be able to do something like linear algebra (multiplying many numbers together quickly) but it sounds like no

#
**nicuramar**
t1_j1nv8jm wrote

The are good for solving problems in a class called BQP. There is a list here: https://cstheory.stackexchange.com/questions/31139/problems-in-bqp-but-conjectured-to-be-outside-p

#
**professorDissociate**
t1_j1n60ey wrote

I feel like AI will eventually be something that really takes off thanks to QPUs.

Viewing a single comment thread. View all comments