You're probably confusing physical qubits (inside the actual physical device) and logical qubits (on which the platonic ideal calculation takes place). If we had 1000 logical qubits, we could indeed do useful things, but real-world implementations require huge amounts of error correction, which is much tricker on quantum computers than classical ones. Asymptotically the ratio of physical to logical qubits can approach 1 (just polylog overhead), but for early calculations the ratio will literally be more than a factor of a thousand. (This is true for all concrete proposals to date; people have speculated that there might be something useful to do with 1000 physical qubits for certain problems if the error could be small enough to be ignored and not corrected, but no one has actually shown explicitly how to do this, or produced the components with the quality that would be necessary.)

Yes, I was certainly confused. When IBM announced they are building a 7x7 = 49 qubit machine, I naturally assumed they meant logical qubits, not physical ones. Using surface codes, they can probably get one logical bit. But what confuses me are past records where they used Shor's algorithm to factor small integers on a quantum computer. How is this possible if we haven't even built a single logical qubit yet? It's surely necessary to have ~2N logical qubits to factor an integer of N bits.

I have an idea that might help though: if logical qubits are so difficult to build and require thousands of times more physical qubits, and physical qubits are also difficult to build, perhaps we can simulate physical qubits with thousands of times more "ultra-physical" qubits.

Two excellent questions.

Regarding claims of factoring small numbers: First note that error correction becomes exponentially more important for longer computations. Second, see this

https://arxiv.org/abs/1301.7007

Regarding building a tower of ever less noisy qubits: it turns out there is something called a threshold theorem which requires a certain minimal level of noise before concatenating error correction schemes makes things better rather than worse.

https://en.m.wikipedia.org/wiki/Quantum_threshold_theorem

Reaching this threshold for physical qubits in the laboratory is perhaps the primary goal of experimental quantum computing.

That first article you cite certainly puts the whole thing in perspective. I was tempted to put an article on Arxiv announcing a new architecture for billions of "super-physical" qubits, but you've convinced me that not only would the real experts see right through this, but that it might bring me down to the level of some of the qubit measuring contests currently on display from the likes of IBM, Google and Microsoft. Thanks for the genuinely interesting answers, especially to the not completely serious question!

When I took a course on quantum computing in 2007 with a standford prof, he said that things would get interesting after we get to 128 qubits :)

I guess someone will eventually introduce some kind of terminology like, "qubit equivalent". But I think that if you could build an error free 128 qubit machine, this would be interesting. But the main reason I see for that is if you can build one with 128 qubits, almost certainly someone with a lot more money than you, with a black budget, can build one much larger. The basic thrust of the article, and the paper, seems to be that if you can engineer a large enough quantum computer than doesn't really work, you can simulate one that doesn't exist. It's truly great if they are right, but I can't find a single statement about this paper on the entire web by an expert that is enthused about this announcement. The paper is short enough that there should be some comment by now.

Someone has already done that:

https://www.research.ibm.com/ibm-q/resources/quantum-volume....

That's a very specific number, do you know what the relevance of 128 is?

No I don't think it was specific. I believe he was just guesstimating the exponential power required to do anything more interesting than basic math. We were all rather young students at the time so I don't think he had a specific application in mind. It was all rather new back then anyways, hard to imagine all the applications.

He is probably referencing the 128 bit security threshold most crypto systems seek to achieve. However this doesn’t really line up with the number of qubits needed to break said crypto, which is typically much larger (thousands of qubits, plus error correction to survive millions of operations).

Edit: less than a doubling. Eg from 128 to 192 or from 256 to 384. I meant to say a doubling is sufficient.

> Thousands will already solve interesting problems that no classical computer can currently solve, e.g. factoring RSA moduli.

With hundreds you can already speed-up chemistry simulations, what will have a much larger impact than breaking RSA.

> With hundreds you can already speed-up chemistry simulations

You can? How?

You need an exponential increase in performance (power of N) to simulate an increasing number of molecules, while for quantum computers you may need only a polynomial increase in performance (power of 2).

So it's possible to simulate 25-qubit-level chemistry with a laptop, 50-qubit-level chemistry with a supercomputer, and 100-qubit-level simulation with a supercomputer is impossible and will be impossible for a very long time.

But going from a 50-qubit quantum computer to a 100-qubit one may take just 2 years (or 4, it doesn't really matter), and then another 2 years to get to 200 qubits, and so on. Quantum computers will solve chemistry problems in minutes that would otherwise have taken 100 years to simulate.

So what I'm asking is how does a quantum computer solve quantum chemistry problems? To make it concrete, say I want to calculate the band structure of a crystal using a quantum computer? What do I do? What kind of algorithms can the QC run that solves this problem faster/better than, say, a DFT code?

I don't think it's a given that just because I want to simulate a quantum mechanical system in some way, that a quantum computer is a useful tool. Or it might be, I don't know. I just don't think it's enough justification that there happens to be the word "quantum" in both the problem description and in the name of the computer.

Simulating quantum chemistry was one of the original motivations for quantum computers.

See this paper for an overview https://arxiv.org/pdf/1203.1331.pdf

Thank you, exactly what I was looking for!