4 ms·

Quantum Error Correction Goes FOOM

70 points by EvgeniyZh 10mo ago

sparedwhistle 10mo ago
What the hell is FOOM?
- MattPalmer1086 10mo ago
  Usually refers to a sudden increase in AI intelligence to super intelligence, i.e. the singularity. Basically an exponential increase in capability.
  - austinjp 10mo ago
    It may also be a reference to the (comparatively ancient) "Pentium go F00F" bug. https://en.wikipedia.org/wiki/Pentium_F00F_bug https://en.wikipedia.org/wiki/Pentium_F00F_bug
  - nineteen999 10mo ago
    Usually? How many times has that happened?
- AlexCoventry 10mo ago
  Explosive ignition of a fire.
- cubefox 10mo ago
  It was Yudkowsky's colloquial term for hard takeoff: https://www.lesswrong.com/posts/tjH8XPxAnr6JRbh7k/hard-takeoff https://www.lesswrong.com/posts/tjH8XPxAnr6JRbh7k/hard-takeo...
- layer8 10mo ago
  https://en.wiktionary.org/wiki/foom#English https://en.wiktionary.org/wiki/foom#English
amluto 10mo ago
I'm amused by the burying of the non-lede until half way through the paper. I, too, can maintain a 59-bit repetition code for over two hours on my quantum laptop (it's just a normal laptop, but it definitely obeys the laws of quantum mechanics): Initialize the coded bit, using a 59-qubit repetition code that corrects bit flips but not phase errors, in IPython: In [1]: A = 59 * (False,) Write a decoder: In [2]: def decode(physbits): ...: return sum(physbits) > len(physbits)/2.0 Wait two hours [0]. I'll be lazy and only decode at the end of the two hours, but if I wanted error correction to get the full advantage, I would periodically run the error correction algorithm and fix detected errors. Now decode it: In [3]: decode(A) Out[3]: False Holy cow, it worked! I'm being rather tongue-in-cheek here, of course. But it's genuinely impressive that my laptop can stick 59 bits into DRAM cells containing a handful of electrons each, and all of them are just fine after several hours. And it's really really impressive that this research group got their superconducting qubits to store classical states well enough that their rather fancy error correcting device could keep up and preserve the logical state for two hours. [1] But this isn't quantum error correction going FOOM, per se. It's classical. A bit-flip-corrected but not phase-flip-corrected qubit is precisely a classical bit, no more, no less. The authors did also demonstrate that they could do the same trick correcting phase flips and not bit flips, but that's a tiny bit like turning the experiment on its side and getting the same result. Combining both demonstrations is impressive, though -- regardless of whether you look at the DRAM cells in my laptop as though the level is the Z basis or the X basis, they only work in one single basis. You cannot swap the role of level and phase in DRAM and get it to still work. But the researchers did pull that off on their two-hour-half-life device, and I find that quite impressive, and the fact that it worked strongly suggests that their device is genuinely 59 qubits, whereas no one could credibly argue that my laptop contains giga-qubits of DRAM. Fundamentally, you can do classical repetition using a repetition code, but you cannot do quantum computation with it. You need fancier, and more sensitive-to-errors, codes for this, and that's what the second half of the article is about. [0] I didn't actually wait two hours. But I could have waited a week and gotten the same result. [1] The researchers' qubits are nowhere near as good as my DRAM. They had to run their error correction a billion times or so during the course of their two hours. (My DRAM refreshes maybe ten thousand times over the course of two hours, and one can look at DRAM refreshes as correcting something a bit like a repetition code.)
Havoc 10mo ago
Does quantum speed even matter? I would have thought a wide enough array of qubits could functionally do "anything" in one shot
- tsimionescu 10mo ago
  They most certainly can't, not even close to it. They can do a very limited subset of problems, and not at all in one shot - just far far far less shots than a classical computer. But even if you reduce and O(e^n) problem to an O(n) or O(n²) problem, that's not instantaneous, and the speed with which you perform these n or n² operations still matters.
- Strilanc 10mo ago
  Yes, speed matters. No, quantum computers can't do everything instantly even with unbounded qubits. A well studied example is that it's impossible to parallelize the steps in Grover's algorithm. To find a preimage amongst N possibilities, with only black box access, you need Ω(sqrt(N)) sequential steps on the quantum computer [1]. Another well known case is that there's no known way to execute a fault tolerant quantum circuit faster than its reaction depth (other than finding a rewrite that reduces the depth, such as replacing a ripple carry adder with a carry lookahead adder) [2]. There's no known way to make the reaction depth small in general. Another example is GCD (greatest common divisor). It's conjectured to be an inherently sequential problem (no polylog depth classical circuit) and there's no known quantum circuit for GCD with lower depth than the classical circuits. [1]: https://arxiv.org/abs/quant-ph/9711070 https://arxiv.org/abs/quant-ph/9711070 [2]: https://arxiv.org/abs/1210.4626 https://arxiv.org/abs/1210.4626
- tbrownaw 10mo ago
  There is a complexity class called BQP, which is more or less the things that quantum computers are good at. This includes P which is more or less the things they normal computers are good at. Things that quantum computers are better at would more or less be one minus the other. One interesting point is that BQP probably doesn't include all of the rather famous NP class.
- moffkalast 10mo ago
oh_my_goodness 10mo ago
Look at the last plot.
joelthelion 10mo ago
Realistically, in the best case scenario, what can we expect from quantum computing? Which real world applications will benefit from it?
- nineteen999 10mo ago
  Right now, quantum computing is highly useful as a form of employment for quantum computing researchers.
- hershkumar 10mo ago
  simulation of quantum systems: quantum chemistry, nuclear physics, high energy physics, condensed matter physics, to name the most promising ones off the top of my head.
  - joelthelion 10mo ago
    Thank you, that's a good one indeed!

70 points by EvgeniyZh 10mo ago

sparedwhistle 10mo ago

What the hell is FOOM?

MattPalmer1086 10mo ago
Usually refers to a sudden increase in AI intelligence to super intelligence, i.e. the singularity. Basically an exponential increase in capability.
- austinjp 10mo ago
  It may also be a reference to the (comparatively ancient) "Pentium go F00F" bug. https://en.wikipedia.org/wiki/Pentium_F00F_bug https://en.wikipedia.org/wiki/Pentium_F00F_bug
- nineteen999 10mo ago
  Usually? How many times has that happened?
AlexCoventry 10mo ago
Explosive ignition of a fire.
cubefox 10mo ago
It was Yudkowsky's colloquial term for hard takeoff: https://www.lesswrong.com/posts/tjH8XPxAnr6JRbh7k/hard-takeoff https://www.lesswrong.com/posts/tjH8XPxAnr6JRbh7k/hard-takeo...
layer8 10mo ago
https://en.wiktionary.org/wiki/foom#English https://en.wiktionary.org/wiki/foom#English

amluto 10mo ago

I'm amused by the burying of the non-lede until half way through the paper. I, too, can maintain a 59-bit repetition code for over two hours on my quantum laptop (it's just a normal laptop, but it definitely obeys the laws of quantum mechanics): Initialize the coded bit, using a 59-qubit repetition code that corrects bit flips but not phase errors, in IPython: In [1]: A = 59 * (False,) Write a decoder: In [2]: def decode(physbits): ...: return sum(physbits) > len(physbits)/2.0 Wait two hours [0]. I'll be lazy and only decode at the end of the two hours, but if I wanted error correction to get the full advantage, I would periodically run the error correction algorithm and fix detected errors. Now decode it: In [3]: decode(A) Out[3]: False Holy cow, it worked! I'm being rather tongue-in-cheek here, of course. But it's genuinely impressive that my laptop can stick 59 bits into DRAM cells containing a handful of electrons each, and all of them are just fine after several hours. And it's really really impressive that this research group got their superconducting qubits to store classical states well enough that their rather fancy error correcting device could keep up and preserve the logical state for two hours. [1] But this isn't quantum error correction going FOOM, per se. It's classical. A bit-flip-corrected but not phase-flip-corrected qubit is precisely a classical bit, no more, no less. The authors did also demonstrate that they could do the same trick correcting phase flips and not bit flips, but that's a tiny bit like turning the experiment on its side and getting the same result. Combining both demonstrations is impressive, though -- regardless of whether you look at the DRAM cells in my laptop as though the level is the Z basis or the X basis, they only work in one single basis. You cannot swap the role of level and phase in DRAM and get it to still work. But the researchers did pull that off on their two-hour-half-life device, and I find that quite impressive, and the fact that it worked strongly suggests that their device is genuinely 59 qubits, whereas no one could credibly argue that my laptop contains giga-qubits of DRAM. Fundamentally, you can do classical repetition using a repetition code, but you cannot do quantum computation with it. You need fancier, and more sensitive-to-errors, codes for this, and that's what the second half of the article is about. [0] I didn't actually wait two hours. But I could have waited a week and gotten the same result. [1] The researchers' qubits are nowhere near as good as my DRAM. They had to run their error correction a billion times or so during the course of their two hours. (My DRAM refreshes maybe ten thousand times over the course of two hours, and one can look at DRAM refreshes as correcting something a bit like a repetition code.)

Havoc 10mo ago

Does quantum speed even matter? I would have thought a wide enough array of qubits could functionally do "anything" in one shot

tsimionescu 10mo ago
They most certainly can't, not even close to it. They can do a very limited subset of problems, and not at all in one shot - just far far far less shots than a classical computer. But even if you reduce and O(e^n) problem to an O(n) or O(n²) problem, that's not instantaneous, and the speed with which you perform these n or n² operations still matters.
Strilanc 10mo ago
Yes, speed matters. No, quantum computers can't do everything instantly even with unbounded qubits. A well studied example is that it's impossible to parallelize the steps in Grover's algorithm. To find a preimage amongst N possibilities, with only black box access, you need Ω(sqrt(N)) sequential steps on the quantum computer [1]. Another well known case is that there's no known way to execute a fault tolerant quantum circuit faster than its reaction depth (other than finding a rewrite that reduces the depth, such as replacing a ripple carry adder with a carry lookahead adder) [2]. There's no known way to make the reaction depth small in general. Another example is GCD (greatest common divisor). It's conjectured to be an inherently sequential problem (no polylog depth classical circuit) and there's no known quantum circuit for GCD with lower depth than the classical circuits. [1]: https://arxiv.org/abs/quant-ph/9711070 https://arxiv.org/abs/quant-ph/9711070 [2]: https://arxiv.org/abs/1210.4626 https://arxiv.org/abs/1210.4626
tbrownaw 10mo ago
There is a complexity class called BQP, which is more or less the things that quantum computers are good at. This includes P which is more or less the things they normal computers are good at. Things that quantum computers are better at would more or less be one minus the other. One interesting point is that BQP probably doesn't include all of the rather famous NP class.
moffkalast 10mo ago

oh_my_goodness 10mo ago

Look at the last plot.

joelthelion 10mo ago

Realistically, in the best case scenario, what can we expect from quantum computing? Which real world applications will benefit from it?

nineteen999 10mo ago
Right now, quantum computing is highly useful as a form of employment for quantum computing researchers.
hershkumar 10mo ago
simulation of quantum systems: quantum chemistry, nuclear physics, high energy physics, condensed matter physics, to name the most promising ones off the top of my head.
- joelthelion 10mo ago
  Thank you, that's a good one indeed!