[krastanov]

Doesn't your argument apply to classical bits too? The more interconnected a classical bit is, the more parasitic coupling it will experience. That used to be an argument used against the feasibility of classical computers in the 40s (until von Neumann published work on fault tolerant classical computing).

Both classical and quantum computers (1) can not "scale" without error correction because of analog noise (although it is less crucial on the classical side), but (2) can be build with error correction codes integrated in them to overcome that noise.

Also, you do not need all-to-all connectivity between your qubits (or bits) to build a scalable quantum (or classical) computer.

Edit: To add to your FM radio metaphor: you can have way more FM radio channels if each channel is on a separate coax cable (or in physics speak, if you multiplex not only by frequency but by spacial mode). No need to have all your qubits be controlled by the same optical or microwave mode, you can have physically separate control lines for each qubit and then eliminating cross-talk is as simple as inverting an n-by-n matrix.

[andyferris]

To add to the sibling comment, the reason our classical computers work is because the individual transistor errors in your CPU are basically zero.

We do use “error correction” on storage (and do see bit errors creep into data stored on disk and in RAM over time) but not “fault tolerance” on the compute. In fact there is no such thing as fault-tolerant classical compute - the CPU only works if it “perfect” or “near perfect” (or if you had an ancillary computer that was perfect to implement the correction). Note that occasionally computers do crash due to a bit error in your CPU, or you get a “unstable” CPU that you need to replace.

(We do create fault-tolerant distributed systems, where such faults can generally be modelled and remedied as network errors, not compute errors.)

Quantum fault tolerance relies on the fact that you can do “perfect” classical computation - which I find kind of amusing!

[blincoln]

There have actually been a surprising number of computing platforms that implement fault-tolerant processing. It's often called "lock-step" execution.

https://www.vmware.com/content/dam/digitalmarketing/vmware/e... (throughout)

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

https://www.intel.sg/content/dam/doc/product-brief/high-perf... (page 5)

[krastanov]

With the benefit of hindsight, it is easy to agree with what you say. But from the point of view of the scientists creating the first classical computers, classical fault-tolerance seemed just as difficult to them as quantum fault-tolerant computation seems to us. See von Neumann's "Probabilistic Logics and the Synthesis of Reliable Organisms from Unreliable Components" from 1952 https://static.ias.edu/pitp/archive/2012files/Probabilistic_...

Not that it is impossible for OP to be right, but the argument he is using used to be applied to classical computation and ultimately turned out to be wrong in that context.

[dboreham]

This idea that multiple redundant voting computing units would be magic to Johnny VN seems unlikely. This is because that exact scheme was used with manual "computers" (people with desk calculators) for example in code breaking and nuclear weapon simulation. You'll find descriptions of these techniques for example in Feynman talks.

[vhcr]

> Team member Raphael Some of JPL explains: "One way to use faster, consumer CPUs in space is simply to have three times as many CPUs as you need: The three CPUs perform the same calculation and vote on the result. If one of the CPUs makes a radiation-induced error, the other two will still agree, thus winning the vote and giving the correct result."

https://science.nasa.gov/science-news/science-at-nasa/2005/1...

[andyferris]

Yes. In practice it can be worthwhile doing this in distributed compute. These methods (and those from sibling comments) do rely on the error rate being low, and the data compared being much smaller than the amount of compute (eg bytes in final answer << number of CPU instructions used). AFAICT such faults can be treated much like network and storage errors.

What we can’t do is have a set of CPUs where roughly every 1000th instruction fails and hope that plugging together a bunch of computers together to check each other’s progress will work. The specific issue is that the checking is wrong so frequently that you can’t “win” to solve a problem involving trillions of instructions by adding more computers. The overhead of “checking the checkers” just blows up.

What’s interesting about quantum computation is this is exactly what is proposed - have qubit error rates of (I think) around 0.1% and lots of measurement, classical compute, and feedback control to keep the computation “on track”. The whole scheme relies on the error rate for all of that classical compute step to be negligible.

[matthewdgreen]

This isn't really accurate. Fault-tolerant classical computing absolutely does exist as a field, and plenty of work has been done there. Some of the early work was done by von Neumann [1] because early computing hardware was extremely error-prone. Over time it turned out that these techniques were not really needed due to the fact that modern solid-state hardware is extremely reliable. The field of quantum computing actually resurrected a handful of ideas that were originally developed for classical computers.

More generally, nobody needs "perfect" classical computing either to make quantum computing work. Given a (quantum or classical) processor with some degree of error, the idea behind these techniques is to "boost" that into a processor with arbitrarily small error. It just turns out that with modern classical processors the error is so small that we suffer it rather than pay the cost of using these techniques.

[1] https://www.cs.ucf.edu/~dcm/Teaching/COP5611-Spring2013/Pape...

[blueplanet200]

It does not apply to classical bits in the same way. Quantum computers derive their computational power from the qubits being in a single quantum state across the qubits (an entangled one, to use physics jargon.)

This is distinct from classical computers, where you can describe a bit without needing to describe the other bits in the computer. You cannot describe a qubit (in a way that's computationally useful, at least) without describing all of them.

[krastanov]

But the exponential cost (the need to describe the "whole") is there in the classical case too.

To describe a set of classical bits completely, you need a probability distribution over the whole system (including possible classical correlations induced by the crosstalk that OP spoke about). That probability distribution is a stochastic vector that has 2^n real positive components if we have n bits.

To describe a set of qubits completely, you need at least a "quantum probability distribution", i.e. a ket that has 2^n complex components (I am skipping the discussion of density matrices).

Both the classical and quantum description of the bits requires exponentially many real numbers. This exponential behavior on its own is not enough to the explain "quantum computational advantage". The exponential behavior is well known in plenty of classical contexts (e.g. under the name "curse of dimensionality") and classically solved with Monte Carlo modeling.

Scott Aaronson's lecture notes cover that quite well.

At the end, the issue of crosstalk is modeled in a very similar way in the quantum and classical case, and if it forbids the existence of a quantum computer, it should forbid the existence of classical ones as well. In both cases it is the use of linear binary (or stabilizer) codes that solves that issue.

[MobiusHorizons]

I may be misunderstanding your argument, but it seems like you are saying that modeling faults in a classical computer also needs to take into account the states of all bits in relation to one another, and that this somehow proves that the problem of crosstalk is similar to interference in quantum computers.

If I have understood your argument correctly I don’t think the conclusion follows from the premise because crosstalk is not fundamental to classical computing. By that I mean that for a given logical cpu design, crosstalk can be (and is) minimized through physical design characteristics (eg grounding, wire spacing etc) without reducing the size of computation. The same cannot afaik be said of quantum computers, where the interaction between qbits is essential to computation

[krastanov]

I do not think I follow your last two sentences. Both for bits and for qubits, two-bit gates are required (e.g. NAND for classical and CNOT for quantum). The bits/qubits need to interact for such a gate to happen and should be isolated from one another before/after the gate. And same as with bits and grounding and wire spacing, we use various decoupling techniques for qubits.

Of course, qubits are drastically more difficult, but the principle is the same.

[MobiusHorizons]

Good point, I said computation, but I was thinking more of the storage and routing pieces of that rather than the gates, likely because I don’t understand quantum gates very well. Most of the quantum ecc I have read about was in the storage lifetime and retrieval process.

Basically what I mean is that classical computing can split things up during storage or routing to reduce coupling, but quantum can’t do this because the qbits must stay entangled to be useful

[krastanov]

WiFi, 5G, PCIe, Ethernet, QR codes, and pretty much any other classical communication protocol uses error correcting codes where classical bits need to be sent in blocks, e.g. for PCIe6, blocks of 256 physical bytes are sent, but only 242 of information is transmitted because the rest is used to enforce some classical correlation for the purposes of error correction. We can not send smaller packets of data (unless we pad). There are probably many technical details I am oblivious to here on the classical side of things, but this "can not split things up" constraint does not seem unique to quantum correlations (entanglement).

And the way we mathematically express and model classical correlations in classical error correcting codes is virtually the same as the way to model quantum correlations (entanglement) in quantum error correcting codes.

All of this with the usual disclaimer: the quantum case is much more difficult, engineeringly speaking.

[plank]

Not the parent (and gotten my PhD more then 25 years ago), but the answer is no.

Quantum mechanics is a fickly thing. Schrödingers cat has not been observed ;-) because scaling kills the quantum mechanical properties.

My (entirely theoretical) PhD project dealt with a 2 dimensional electromagnetic cavity, with one 'perfect' mirror (100% reflecting) and one 'imperfect', say 99.999999999% reflecting.

My results were that if you started with a 'squeezed' vacuum, in just a few roundtrips, the 'squeeziness' disappears, due to the bath/loss of the non-perfect mirror. My 'gut feeling' tells me that if we have enough qbits to actually factor something more then 2x2, the loss/bath effect will delete any useful use of the quantum computer.

So I am in the 'will not happen' category. (Not in 1, not in 5, not in 30 years, not in 500 years).

This is different from classical error correction: as far as I understand Schors algorithm, there is no 'get N approximate answers, combine them, and get a better answer' part in there. While classically you could do 100 measurements and get a better approximation then with just one.

[eigenket]

It doesn't change the overall point you're making but your "gut feeling" was already wrong 20 years ago. A group working for IBM factored 15 = 3x5 with a quantum computer in 2001.

You are also somewhat wrong about the combining N approximate answers and combining them. It is correct that that the "repetition code" approach (repeat the same calculation a bunch of time and average the results) does not work for quantum computers. However there are quantum error correcting codes which do appear to work, although they require sufficiently small initial error rates (so-called thresholds) in order to help.

[eigenket]

Yes. In fact the proofs that quantum error correction works as long as you're below a certain error rate (so-called "threshold theorems" are very, very similar to the same proofs that error correction works in classical computers.

[andyferris]

Yes, the same as classical error correction but distinct from classical fault tolerance. It’s fascinating (to me) how these are different!