[goatlover]

> Your answer doesn’t actually explain what we can do on a quantum computer that we can’t on a traditional computer.

Why would there be anything you could compute on a quantum computer that you can't compute on a classical one (provided the classical one is powerful enough or given enough time for certain algorithms quantum computers are more efficient at).

Is there speculation that a quantum computer could be used for hypercomputing?

[drdeca]

They meant due to practical limitations on the speed of the computer and/or the amount of time you can afford to wait for the answer.

They were not saying that there may be computations that can be done with finite space and finite time on a quantum computer that cannot be done in any finite space and finite time on a classical computer.

They were talking about computational complexity, not computability.

[btilly]

The fundamental observation behind quantum computing is that an irreversible bit flip releases a minimum amount of heat, while a reversible one releases none. See https://en.wikipedia.org/wiki/Landauer%27s_principle for the theoretical limits to classical computing based on this. But there are, to the best of our current knowledge, no theoretical limits to how much computation can happen reversibly.

However the requirement that the operations all be completely reversible is very strict. For example logic operations like "and" and "or" are off the table. BUT when physicists like Richard Feynman looked into, what DOES happen is that your computation can progress in a quantum superposition of states. And there is no upper limit to how many states are in the quantum superposition.

So in essence what you get should be a very hard to program but unbelievably parallel computer with no upper limit on computational speed.

The first demonstration that this could be useful for problems that people care about was https://en.wikipedia.org/wiki/Shor%27s_algorithm for factoring integers. The fact that we do not know how to factor integers quickly is an underpinning of public key cryptography algorithms like RSA. However we know how to solve that if we had a quantum computer. And this is just engineering, right?

Everyone recognizes that it is a very hard engineering problem. But the minority opinion laid out in this article is that the engineering problem is not just a practical problem, but the physics makes it intrinsically hard in a way that cannot ever be worked around. No matter how well a quantum computer works in theory, it is physically impossible for us to build and operate one that does better than the classical computers that we already know how to build.

[deepnotderp]

Okay, first of all, we are no where near Landauer's Limit right now, and will likely never reach that point because we'll run into thermal noise "danger zones" far before then.

Second of all, there are plenty of (and probably the primary ) forms of non-quantum reversible logic.

In the slightly less exotic category there is also adiabatic computing which can actually be done in standard CMOS in most flavors.

[pdpi]

"Solve problem x in polynomial time". AIUI, BQP is thought to be a superset of P and to include some stuff from outside NP. Specific problems that are part of BQP but that we expect are not in P is the interesting response here.

An example of such a problem is integer factorisation (see: Shor's Algorithm), which means that RSA and similar schemes might become vulnerable once suitably large quantum computers are available.