[wyager]

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

The answer: we don’t know. We don’t even know if BQP is actually any bigger than P.

However, we’ve figured out how to do some things quickly on quantum computers that we haven’t ever figured out how to do quickly on classical computers, like certain mathematically useful operations on abelian groups.

One specific example is that you can do Fourier transforms in O(log(n)log(log(n))) rather than O(n log(n)), which is pretty cool. If your vector space is too big to even represent in classical memory, you might still be able to work with it on a quantum computer.

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

[jcranmer]

> If your vector space is too big to even represent in classical memory, you might still be able to work with it on a quantum computer.

Quantum computers don't have any space advantage, I thought?

[wyager]

Your question is too simple to have a correct answer.

You can represent any unit vector in a vector space with 2^n basis elements using only n qubits.

Constructing an arbitrary vector might not be more efficient than doing it on a classical computer, but constructing certain vectors that would probably be very large and/or unwieldy on a classical computer is possible. For example, it’s easy to represent any single standard basis vector in a vector space with size 2^64 on a classical computer; just use a list of (64-bit word to describe which basis vector you’re talking about and a weight). Now go ahead and try to use that same representation for a Fourier transform, and you’re out of luck. But this is no problem on a quantum computer. You just end up with a 64-qubit system that has a non-zero value for all of those 2^64 basis states (using only 64 qubits). You can also construct the circuit required to do the Fourier transform with ~64log(64) gates.

So for this problem, there’s definitely a space advantage. The trouble is that most of these advantages don’t generalize in any obvious way. Maybe there’s even a representation on classical computers that’s equally efficient and we just haven’t found it yet.

And as you mention below, this isn’t useful for arbitrary linear operations (many of them seem to be just as expensive on a quantum computer as on a classical computer) but there are certain known-to-be-useful linear operations that are extremely cheap to represent compared to what we know how to do on a classical computer.

[jcranmer]

The essential problem with a quantum computer, as I understand is it, is that you can't actually read out the state you've created. Sure I can create a state which is an equal admixture of all 2^64 basis vectors, but if I try to look at it, I'm going to randomly end up with only one of the basis vectors.

[lmm]

Sure, but you might be able to perform some computation that involves those 2^64 possible states that ends up with some determined state that you can reliably measure. So while you can't store 2^64 classical values in one quantum bit, nor can you necessarily simulate that quantum bit exactly with even 2^64 classical values.

[wyager]

That’s why quantum algorithms try to bring the final result down to (mostly) a combination of only a few standard basis states.

[codekilla]

Imagine you have a classical bit string 0101, there are 2^4 possible different configurations of this string, and the classical computer will always exist in ONE of them.

A quantum computer, with a qubit register 0101, can be put into a superposition state between all 4 qubits, where the state of the qubit register is ALL 2^4 different configurations simultaneously....now scale that up to 50-100-1000 qubits and you get the idea. The quantum computer has a ridiculous advantage in terms of holding state spaces.

[jcranmer]

That argument is patently wrong: it's the quantum bullshit fallacy.

The point of the space argument I was making was that, if you need N bits of space to represent the input/output in classical computers, you should still need (I'm not sure if it's the case, but I don't see why it's not) Ω(N) qubits to do the same representation in a quantum computer.

The quantum bullshit fallacy is that, since an entangled N-qubit is represented as a 2^N-dimension vector with complex arguments, it's really a computation on 2^N elements in O(1) time. The first sign that this is fallacious is that the basis here isn't of size 2^N but of size 2^N - 1. We're still only capable of reading N bits of information out of an N-qubit register; the fact that classical simulation requires a much larger state space to compute the probability doesn't mean that there's an inherent ability to freely vary through all of those states to represent the entire state space.

[codekilla]

Honestly, I don't understand the point you are making. If you can explain to me how the Deutsch-Joza algorithm works without making reference to the fact that a function evaluation happens on a qubit in superposition(and thus an expanded state-space, as the simplest example), sure. I sincerely don't understand your points about classical simulation, or input/output in classical computers.

[smallnamespace]

As you say, N qubits can be thought of as a distribution over its possible 2^N values, but you can't ignore the starting distribution, which may be very far from the set of classical bits that you want to operate over (and therefore may take an exponential number of quantum operations to realize).

So one very simplified model to think of what quantum computation is that you can do parallel operations to a distribution over your 2^N vector of classical bits, but you don't get to specify an arbitrary starting distribution, you can only start with relatively 'simple' distributions.

This restriction is what makes the claim 'you can compute over 2^N values simultaneously' at best very incomplete — yes, you can do that, as long as you're fine not being able to start from arbitrary starting values. But this is a big restriction!

[codekilla]

What do you mean exactly by starting distribution? I'm definitely not saying you get the answer to every problem in a single evaluation step, no one ever said that.

[jcranmer]

If you have an N-bit classical computer in a black box, you get at most 2^N possible outputs. If you have an N-qubit quantum computer in a black box, you can get at most 2^N possible outputs, not 2^2^N. We write the N-qubit registers as a vector of 2^2^N elements to make the math work, but measurement means we still can only distinguish between 2^N possible values.

[monktastic1]

Well, only in the same sense that the vector (1, 1) is "both (1, 0) and (0, 1) simultaneously." It's still a single vector in a 2^N dimensional space. It just happens to be expressed in terms of a basis that makes it look complicated.