4 ms·

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 a

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.

eigenket 3y ago
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 3y ago
  Yes, the same as classical error correction but distinct from classical fault tolerance. It’s fascinating (to me) how these are different!
blueplanet200 3y ago
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 3y ago
  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 3y ago
    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 3y ago
      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.
andyferris 3y ago
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!
- krastanov 3y ago
  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_Logics.pdf 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 3y ago
    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 3y ago
  > 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/18nov_eaftc https://science.nasa.gov/science-news/science-at-nasa/2005/1...
plank 3y ago
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 3y ago
  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 3y ago

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 3y ago
Yes, the same as classical error correction but distinct from classical fault tolerance. It’s fascinating (to me) how these are different!

blueplanet200 3y ago

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 3y ago
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 3y ago
  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 3y ago
    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.

andyferris 3y ago

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!

krastanov 3y ago
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_Logics.pdf 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 3y ago
  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 3y ago
> 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/18nov_eaftc https://science.nasa.gov/science-news/science-at-nasa/2005/1...

plank 3y ago

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 3y ago
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.