[foxes]

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.

[moefh]

> 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/...

[foxes]

Yes sorry you are right. I found this nice example of Grover's algorithm [0].

[0] http://davidbkemp.github.io/animated-qubits/grover.html

[hrygolis]

https://www.quantamagazine.org/finally-a-problem-that-only-q...

[moefh]

That'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.

[zjaffee]

I'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.

[bdamm]

Is Shor's an application of entanglement though?

[teraflop]

Yes, all non-trivial quantum computing is based on entanglement.