5 ms·
There are already lots of 'practical' applications in the literature. A famous one is Shor's factorisation algorithm. But there are others - everything from doi
by foxes 8y ago
There are already lots of 'practical' applications in the literature. A famous one is Shor's factorisation algorithm. But there are others - everything from doing pagerank to simulating other quantum systems.
Many classical algorithms, which run in ~O(poly(n)) can have an 'equivalent' quantum algorithm in ~O(log(n)) - an exponential speedup. There is still debate as to how the complexity class of problems which are efficient on a quantum computer (BQP) relate to other complexity classes. Its suspected P lies entirely within BQP.
However, at least initially, I think quantum computers will be a specialized piece of equipment. Classical computing is pretty good for your average person. Quantum computers will be used for more heavy compute tasks.
- bdamm 8y agoIs Shor's an application of entanglement though?
- teraflop 8y agoYes, all non-trivial quantum computing is based on entanglement.
- zjaffee 8y agoI'd also add that the need for localized personal computing services goes down as network bandwidth increases, if there's anything that people really need quantum computers for, it's not unreasonable to suggest that they will be handled on the backend with aggregated results sent to clients as is the case for most computation today.
- moefh 8y ago> Its suspected P lies entirely within BQP. It's actually known that BQP contains P[1]. It also contains BPP. What's not known is the relationship between BQP and NP (most experts suspect there's no containment in either direction). [1] See this for an easy proof: https://people.eecs.berkeley.edu/~vazirani/f04quantum/notes/lec5/lec5.pdf https://people.eecs.berkeley.edu/~vazirani/f04quantum/notes/...
- foxes 8y agoYes sorry you are right. I found this nice example of Grover's algorithm [0]. [0] http://davidbkemp.github.io/animated-qubits/grover.html http://davidbkemp.github.io/animated-qubits/grover.html
- hrygolis 8y agohttps://www.quantamagazine.org/finally-a-problem-that-only-quantum-computers-will-ever-be-able-to-solve-20180621/ https://www.quantamagazine.org/finally-a-problem-that-only-q...
- moefh 8y agoThat's still only relative to an oracle, though (i.e., BQP^O vs NP^O). We also have oracle separations of P and NP, and that proves nothing about P vs NP without an oracle.