5 ms·

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 t

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

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