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.

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.

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

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.

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

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.

What makes qbits valuable is that they scale superlinearly the more of them you have entangled together. This means 8 individual qbits can store less information than 8 entangled qbits. Since they have to remain entangled to do valuable work, you can't physically separate them to prevent interference the way you could with classical bits. This is actually really well demonstrated in all the protocols you mention. None of those protocols operates on a bus that can send 256 bytes of data all together at once. They all chunk the data and send a small number of symbols at a time.

For example in PCIe each lane can only cary one bit at a time in each direction. In typical consumer equipment, there are at most 16 lanes of PCIe (eg a graphics card socket) meaning there can only be at most 16 bits (2 bytes) on the wire at any given time, but the bits are sent at a very high frequency allowing for high transfer rates. This only works because taking those 256 bytes and sending them one by one (or 16 by 16) over the wire doesn't lose information.

I believe there are a couple of misconceptions in your first paragraph (but it is also plausible that both of us are talking past each other due to the lack of rigor in our posts). Either way, here is my attempt at what I believe is a correction:

- Both classical probabilistic bits and qubits need exponential amount of memory to write down their full state (e.g. stochastic vectors or kets). The exponential growth, on its own, is not enough to explain the conjectured additional computational power of qubits. This is discussed quite well in the Aaronson lecture notes.

- Entanglement does not have much to do with things being kept physically in contact (or proximity), just like correlation between classical bits has little to do with bits being kept in contact.

- Nothing stops you from sending/storing entangled bits one by one, completely separate from each other. If anything, the vast majority of interesting uses of entanglement very much depend on doing interesting things to spatially separate, uncoupled, disconnected, remote qubits. Sending 1000 qubits from point A to point B does not require a bus of width 1000, you can send each qubit completely separately from the rest, no matter whether they are entangled or not.

- Not even error correction requires you to work with "big" sets of qubits at the same time. In error correcting codes, the qubits are all entangled, but you still work with qubits one by one (e.g. see Shor's syndrome measurement protocol).

- I strongly believe your first sentence is too vague and/or wrong: "What makes qbits valuable is that they scale superlinearly the more of them you have entangled together". As I mentioned, the exponential growth of the "state descriptor" is there for the classical probabilistic computers, which are believed to be no more powerful than classical deterministic computers (see e.g. derandomization and expander graphs). Moreover, Holevo's theorem does basically say that you can not extract more than n bits of information from n qubits.

- Another quote: "Since they have to remain entangled to do valuable work, you can't physically separate them to prevent interference" -- yes, you can and very much do separate them in the vast majority of interesting applications of entanglement.

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.

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

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!

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.

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.

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

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.

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)

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

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.

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.