5 ms·
A quantum computer is not "infinitely parallel" and though it's still an open problem, it's considered unlikely that that quantum computers can solve NP-complet
by sweis 5y ago
A quantum computer is not "infinitely parallel" and though it's still an open problem, it's considered unlikely that that quantum computers can solve NP-complete problems in polynomial time.
- sova 5y ago>A quantum computer is not "infinitely parallel" Explain
- bawolff 5y agoI mean that's pretty much it. You can't use a quantum computer like a classical computer with a huge (infinite) number of compute cores. Its not a gpu. That's not how it works. If you use the metaphor that superposition is like computing many things in paralell, the problem comes in that when you measure. The superposition collapses to a single answer at random (with probability related to the amplitude of each possibility) which will usually not be the answer you're interested in.
- dvdkhlng 5y agoMy take on it: you get "infinitely parallel" computation, generating "inifinetly parallel" results that are in superposition. Problem is, at the end you can only access your "infinitely parallel" result via a classical measurement, involving a wave function collapse [1]. For some problems, people have found ways to extract useful information via classical measurements, e.g. Shor's algorithm (in theory breaking RSA/DSA/ECDSA/DH/ECDH style public-key algorithms [1]). However in the general case this does not work (so AES and hash algorithms are safe for now). [1] https://en.wikipedia.org/wiki/Wave_function_collapse https://en.wikipedia.org/wiki/Wave_function_collapse [2] https://en.wikipedia.org/wiki/Shor%27s_algorithm#Quantum_part:_period-finding_subroutine https://en.wikipedia.org/wiki/Shor%27s_algorithm#Quantum_par...