[reaperducer]

Problems that are waiting to be solved by it are very large and of huge impact

I know virtually nothing about quantum computing, so can you give some examples? Whenever I've asked anyone who seemed to know anything about the field, all they can come up with is weather forecasting and simulating nuclear explosions. Not exactly "general use," as you put it.

In the back of my mind, I know that quantum computing is a big deal, and we're in ENIAC days with it. But I don't have a good understanding of where it goes or why.

[adrianN]

Quantum computers are extremely useful for simulating chemistry. They can do it exponentially faster than classical computers. Cheap useful quantum computers can revolutionize biology and materials science.

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

[techbio]

Protein folding and gene research. Cure malaria, cancer, feed the world etc.

[kart23]

Doesn't basically all encryption become meaningless with quantum computers? Remember how they always said 'it would take a billion years to crack this encryption with a computer'? Well soon we are going to have computers that don't play by the rules.

[chrisweekly]

ENIAC?

[SimbaOnSteroids]

One of the first computers.

https://en.wikipedia.org/wiki/ENIAC