Strilanc

> I have not seen even a theoretical framework allowing both to be increased simultaneously.

The threshold theorem [1], showing this can be done in principle, was proven more than a decade ago.

But you don't have to believe the theory anymore, there's experiments now! Last month the google quantum computing team published an experiment [2] showing memory error rates (including decoherence) getting twice as good as a surface code was grown from distance 3 to distance 5, and twice as good again going from distance 5 to distance 7. The logical qubit's coherence time was longer than the coherence times of the physical qubits it was built out of.

[1]: https://en.wikipedia.org/wiki/Threshold_theorem

[2]: https://arxiv.org/abs/2408.13687

The threshold is where you transition from needing infinite qubits to make an error corrected logical qubit, to needing a mere finite number. So... somewhere between 1 and infinity (exclusive).

Actually, because "in theory there's no difference between theory and practice but in practice there is", the number is probably still infinity. Like, if you look at figure 4 of their paper [0], you can see one device of the three is well above threshold at 1.5% error. They need sufficient quality more consistently before a large system built out of the pieces they are benchmarking would be below threshold.

[1]: https://www.nature.com/articles/s41567-024-02614-w/figures/4

It's impossible produce a result incompatible with classical mechanics in a single constant-sized observation, because the classical players can get any result by just playing randomly.

The advantage that GHZ has, similar to the Mermin-Peres magic square game, is that the quantum players should win 100% of the time while classical players win less than 90% of the time. This gives much faster Bayesian updates away from classical mechanics towards quantum mechanics as you collect samples (compared to CHSH). But you do still need multiple samples.

On the other hand, seeing the GHZ game fail would be instant total loss for quantum mechanics. If the win rate is supposed to be 100%, and you see a loss (that you can't attribute to noise or something), then in that case a single test would have caused you to totally discount quantum mechanics.

If you want to try your hand at violating Bell inequalities, there are widgets in [1] that allow you to input strategies (as javascript) for Alice and Bob. It continuously performs Monte Carlo sampling of the strategies and presents their success rate.

There's a classical-only widget, that goes through quite some contortions behind the scenes to prevent cheating via writing to global variables, and a quantum-allowed widget where that kind of cheating is possible due to the underlying implementation cheating in precisely that using-globals way in order to correctly simulate the quantum mechanics.

Anyways, I've had a few people tell me playing around with the widgets helped them understand the inequality.

[1]: https://algassert.com/quantum/2015/10/11/Bell-Tests-vs-No-Co...

When I went to the APS March Meeting earlier this year, I talked with the editor of a scientific journal and asked them if they were worried about LLM generated papers. They said actually their main worry wasn't LLM-generated papers, it was LLM-generated reviews.

LLMs are much better at plausibly summarizing content than they are at doing long sequences of reasoning, so they're much better at generating believable reviews than believable papers. Plus reviews are pretty tedious to do, giving an incentive to half-ass it with an LLM. Plus reviews are usually not shared publicly, taking away some of the potential embarrassment.

No, that's not true at all.

For example, a chemistry simulation can be done in first quantization; where the state is a list of superposed 2s-complement integers indicating the positions of the electrons (as opposed to a more direct one-qubit=one-position mapping). And the list is initialized in a way that satisfies the Pauli exclusion principle by using a sorting network [1]. This is presumably not at all how Nature does it.

Another example is factoring. Shor's factoring algorithm is not at all like behaving analogous to a physical system. It's about modular exponentiation and Fourier transforms; math things not physics things.

Yet another example is Hamming weight phasing. If you need to rotate many qubits by a common angle around the Z axis, you can achieve that effect more cheaply by temporarily computing their Hamming weight (under superposition) and then rotating the first qubit of the Hamming weight register by the angle, the second by twice the angle, the third by four times the angle, etc. And actually that various-rotation-angles operation can then also be replaced by an addition into a special reusable phase gradient state; this achieves the desired effect by phase kickback [2]. Adding the Hamming weight of their spins into a helper state is probably not how Nature goes about precessing electrons in a uniform magnetic field.

[1]: https://arxiv.org/abs/1711.10460

[2]: https://arxiv.org/abs/1709.06648

Quantum/classical is orthogonal to the analog/digital distinction. There are analog quantum computers and digital quantum computers.

Analog quantum computers (like annealers) are simpler to make, and they have a lot more play w.r.t. their building blocks when trying to make interesting effects... but ultimately they are limited by noise. Digital quantum computers restrict themselves to finite gate sets, often requiring expensive decompositions to do basic operations (e.g. [1]), but those gates are compatible with error correction so noise can be suppressed arbitrarily (e.g. [2]). It's very similar to how an analog classical computer can do addition with two resistors and a junction, but the accuracy is limited by the precision of the resistance. Whereas a digital classical computer will decompose the addition problem into bits and gain more precision by adding bits so that increasing precision becomes about increasing quantity instead of quality.

[1]: https://www.mathstat.dal.ca/~selinger/newsynth/

[2]: https://arxiv.org/abs/1208.0928

Not unless you can isolate the computer from environmental noise exponentially well. Otherwise you'll need to spend exponential energy on entropy removal / error correction (e.g. keeping the dilution fridge running).

Ah, but the ternary operator solution requires repeating the name of the variable twice. And obviously, since you're writing in Java, your variable name will be at least 50 characters long. Thus making `Objects.requireNonNullElse` shorter.

It's very strange to me that the teacher would push the students from the correct solution using a loop, towards an incorrect solution using a logarithm. A logarithm could work in a language like C where ints can't get too large, but Python has arbitrary precision integers so any solution using floating point numbers is doomed. For example, the code given in the post returns 16 instead of 15 for 999_999_999_999_999.

Yeah that's roughly it. In classical computers all errors can be simplified as being bit flip errors (0 instead of 1, 1 instead of 0). Like, power loss is a lot of bit flip errors that happened to target the bits that should have been 1. In quantum computers this simplification does not work, there is another type of error called a phase flip. Measurements cause phase flip errors. You can exchange the phase flip and bit flip bases by using a gate called the Hadamard gate. So if you surround measurements with Hadamard gates, you will see bit flip errors. The existence of gates like Hadamard is what makes it possible to see these kinds of things at all, and correspondingly its availability can be thought of as the thing that makes a quantum computer a quantum computer, instead of a classical computer.

If you have a more modern estimate I'll take it. Very interesting about the CMOS sensors distinguishing +- 2 electrons (40K / 2^14).

Yeah, I agree it's unusual to describe "increased brightness" as "bigger distance repetition code". But I think it'll be a useful analogy in context, and I'd of course explain that.

It's because unintended measurement is a type of error in a quantum computer. Like, if an electron passing near your qubit would get pushed left if your qubit was 0 and right if was 1, then you will see errors when electrons pass by. Repeating the 0 or 1 a thousand times just means there's 1000x more places that electrons passing by would cause a problem. That kind of redundancy makes that kind of error mechanism worse instead of better.

There are ways of repeating quantum information that protect against accidental measurement errors. For example, if your logical 0 is |000> + |110> + |011> + |101> and your logical 1 is |111> + |001> + |100> + |010> then can recover from one accidental measurement. And there are more complex states that protect against both bitflip errors and accidental measurements simultaneously. They're just more complicated to describe (and implement!) than "use 0000000 instead of 0 and 1111111 instead of 1".

I think you're picturing a different level of the network stack than I had in mind. Yes, above the physical level they will be explicitly using very sophisticated codes. But I think physically it is the case that messages are transmitted using pulses of photons, where a pulse will contain many photons and will lose ~5% of its photons per kilometer when travelling through fiber (which is why amplifiers are needed along the way). In this case the "repetition code" is the number of photons in a pulse.

Wasn't expecting my question to hit top of HN. I guess I'll give some context for why I asked it.

I work in quantum error correction, and was trying to collect interesting and quantitative examples of repetition codes being used implicitly in classical systems. Stuff like DRAM storing a 0 or 1 via the presence or absence of 40K electrons [1], undersea cables sending X photons per bit (don't know that one yet), some kind of number for a transistor switching (haven't even decided on the number for that one yet), etc.

A key reason quantum computing is so hard is that by default repetition makes things worse instead of better, because every repetition is another chance for an unintended measurement. So protecting a qubit tends to require special physical properties, like the energy gap of a superconductor, or complex error correction strategies like surface codes. A surface code can easily use 1000 physical qubits to store 1 logical qubit [2], and I wanted to contrast that with the sizes of implicit repetition codes used in classical computing.

1: https://web.mit.edu/rec/www/dramfaq/DRAMFAQ.html

2: https://arxiv.org/abs/1208.0928

Another danger is some sort of bug in Lean itself. This isn't unprecedented in theorem provers [1][2]. These might be hard to hit by accident... but there are larger and larger collaborations where arbitrarily people fill in steps (like [3]). Someone trolling one of these efforts by filling a step in using a bug they found might become worth worrying about.

[1]: https://inutile.club/estatis/falso/

[2]: https://www.youtube.com/watch?v=sv97pXplxf0

[3]: https://terrytao.wordpress.com/2023/11/18/formalizing-the-pr...

Wasn't the exponential increase in data and compute always part of the scaling hypothesis? That's my memory of it from reading [1] years ago. Most of the field thought scaling would hurt, openai thought you'd get logarithmic benefit from it, and openai won that bet.

1: https://gwern.net/scaling-hypothesis

I would describe classical correlations as downgraded entanglement. Correlation is what's left when entanglement decoheres / undergoes uncontrolled phase noise. Things you should be able to do, like win the Mermin-Peres magic square game 100% of the time, aren't possible when the entangled qubits you'd use to do it aren't protected from phase noise.

Decoherence is sort of analogous to air. It's so ubiquitous in your life that you don't really think about it, but you'd notice immediately if it was removed. Being steeped in air your whole life has twisted your physical intuitions. That's why Aristotle thought "objects come to rest" when actually objects move at constant speed unless acted upon by a force. Similarly, being steeped in decoherence has twisted your physical intuitions. Like thinking "adding more ways for something to happen must make it more likely" or "a particle's position is independent of its momentum" or "I can measure an object without affecting it". But actually different paths can interfere, and momentum is the Fourier transform of position, and measurements apply phase noise.

Decoherence is so ubiquitous that it's a huge challenge to engineer systems that suppress it. This is why quantum computers are so hard to make, and why quantum error correction has so much more overhead compared to classical error correction. Classical error correction only has to fix bit flips, and it can do so by making phase flips worse (which it does). Quantum error correction has to simultaneously fix bit flips and phase flips.

When two particles are entangled, rotating one around the X axis by an angle A and the other by an angle B and then measuring produces measurement results that agree with probability cos^2(A-B). Same as the probability of a photon with polarization angle A passing through a polarizing filter with angle B. Decohere the entanglement before the rotations, and the measurements will instead agree with probability cos^2(A)cos^2(B) + sin^2(A)sin^2(B). Note that cos^2(A-B) = cos^2(A)cos^2(B) + sin^2(A) sin^2(B) + 2 cos(A) cos(B) sin(A) sin(B), meaning decoherence is taking away the 2 cos(A) cos(B) sin(A) sin(B) interference term. That's the downgrade. That's what makes your best possible CHSH win rate drops from 85% to 75%. If entanglement allowed sending messages, the initial CHSH win rate would be 100% instead of 85%.

"Thinking, Fast and Slow" was written before the replication crisis was found. I wouldn't call it "debunked", but some of the research it used didn't replicate. For example, see https://replicationindex.com/2020/12/30/a-meta-scientific-pe... :

> It is likely that Kahneman’s book, or at least some of his chapters, would be very different from the actual book, if it had been written just a few years later. However, in 2011 most psychologists believed that most published results in their journals can be trusted. [...]

> Kahneman also started to wonder whether some of the results that he used in his book were real. A major concern was that implicit priming results might not be replicable. [...]

Anyways, just google "thinking fast and slow replication crisis" to get a bunch of information about this topic.

I maintain that Dyakonov's arguments are completely missing the mark. I predict this will be experimentally obvious, instead of just theoretically obvious from linearity, within 5 years (due to the realization of logical qubits with lifetimes thousands of times better than their parts).

That paper[1] is a joke.

The main argument it makes is based on counting amplitudes, and noting there are far too many to ever control:

> The hypothetical quantum computer is a system with an unimaginable number of continuous degrees of freedom - the values of the 2^N quantum amplitudes with N ~ 10^3–10^5 . [...] Now, imagine a bike having 1000 (or 2^1000 !) joints that allow free rotations of their parts with respect to each other. Will anybody be capable of riding this machine? [...] Thus, the answer to the question in title is: As soon as the physicists and the engineers will learn to control this number of degrees of freedom, which means - NEVER.

The reason this is a joke is because it fundamentally misunderstands what is required for a quantum computation to succeed. Yes, if you needed fine control over every individual amplitude, you would be hosed. But you don't need that.

For example, consider a quantum state that appears while factoring a 2048 bit number. This state has 2^2048 amplitudes with sorta-kinda-uniform magnitudes. Suppose I let you pick a million billion trillion of those amplitudes, and give you complete control over them. You can apply any arbitrary operation you want to those amplitudes, as long it's allowed by the postulates of quantum mechanics. You can negate them, merge them, couple them to an external system, whatever. If you do your absolute worst... it will be completely irrelevant.

Errors in quantum mechanics are linear, so changing X% of the state can only perturb the output by X%. The million billion trillion amplitudes you picked will amount to at most 10^-580 % of the state, so you can reduce the success of the algorithm by at most 10^-580 %. You are damaging the state, but it's such an irrelevantly negligible damage that it doesn't matter. (In fact, it's very strange to even talk about affecting 1 amplitude, or a fraction of the amplitudes, because rotating any one qubit affects all the amplitudes.)

To consistently stop me from factoring, you'd need to change well more than 10% of the amplitudes by rotations of well more than 10 degrees. That's a completely expected amount of error to accumulate over a billion operations if I'm not using error correction. That's why I need error correction. But Dyakonov argues like you'd only need to change 0.0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001% of the amplitudes to stop me from factoring. He's simply wrong.

[1]: https://ebooks.iospress.nl/pdf/doi/10.3233/APC200019

For quantum computers to break RSA2048, the current quality of physical qubits needs to go up 10x and the quantity needs to go up 10000x. These are rough numbers.

The next major milestone to watch for is a logical qubit with fidelity 1000x better than the physical qubits making it up. That will signal the physical qubits are good enough that you could start only scaling quantity.

When you apply a statistical test, the various outcomes cause Bayesian updates that correspond to adding or subtracting fixed bits of evidence. When you repeat the test (and the repetitions are independent), the amount of bits of evidence you add or subtract remain the same. In other words, focusing on bits of evidence shows Bayesian updates behave like a biased random walk under repetition of a test and allow you to compute the properties of that walk.

For example, suppose you are trying to estimate how much rounding errors in a pseudo random number generator betray that it is not a true exact representation of the random process. One way to quantify this is to compute the expected bits of evidence revealed per call to the RNG.

Search "decibels" in https://www.yudkowsky.net/rational/bayes for the explanation.

I think you're just wrong about needing everything to be in the form X:1 or 1:X. When I compute the ratio of 1000000:1 divided by 1:20 it gives 1000000:(1/20) then scaling both sides by the same factor gives 20000000:1.

A log-odds of b bits means an odds of 2^b : 1 which means a probability of p = 2^b / (2^b + 1).

In the original comment, the evidence update was stated as going from 20:1 to 1:1000000 and it was claimed this was approximately 24 bits of evidence. The update is from 2^4.3:1 to 2^-19.9:1. Subtracting the exponents you get 4.3 - -19.9 = 24.2 which is approximately 24 as claimed. The "20" in 20:1 is correctly accounted for by the ~4 additional bits of evidence on top of updating from 1:1000000 to 1:1.

Clearly evidence bits behave very differently from entropy bits. Acquiring a single entropy bit is an update from 1:1 to 0:1 which is 2^0:1 to 2^-infinity:1. It's worth an unbounded number of evidence bits. It's important not to mix these two things up.

It's important to understand that when they said "bits" they didn't mean information in the Shannon entropy sense, but rather in the log-odds evidence sense.

Gaining a Shannon entropy bit means learning the answer to a yes-no question that had 1:1 odds.

Gaining a log-odds evidence bit means doubling your best-guess odds on a question you are uncertain about, from X:Y to (2X):Y.

One Shannon bit is worth arbitrarily many evidence bits, because a Shannon bit takes you from 1:1 odds to UNBOUNDEDLYHUGE:1 odds. So... yeah, actually, reading your username is worth infinite bits of log-odds evidence on what your username is! (Ignoring practical issues like the small chance of computer malfunctions, of course.)

And to answer your initial question: the 20 just came from the assertion they'd bet 20:1. That was arbitrary.

A government site has implicit authority. You could use that implicit authority to make a scam look more authentic. It also will have a lot of traffic; a lot of opportunities for the scam to work if you do manage to get in the middle.

For example, inject a dialog box that says "Our records indicate your taxes were not paid this year! Before you can view the weather you must click here and log in to resolve this issue!".

Quantum error correction corrects more than just bit flips. It corrects phase flips, accidental measurement, qubit erasure, small global rotations... lots of stuff.

I don't know exactly what you have in mind as "loss of entanglement"... But quantum error correction will very much preserve entanglement at the logical level against decay of entanglement at the physical level.

Related: "Quantum computing worst case scenario: we are Lovelace and Babbage" [1]

For scale: Babbage's planned analytical engine had a word size of 50 digits, a clock rate of 7Hz, and a physical size of roughly a locomotive [2]. Contrast [3] where it's estimated that 600-digit superposed additions would run at 27Hz (by dedicating millions of qubits to magic state distillation of the underlying AND gates). Given current plans, a quantum computer capable of doing arithmetic operations as wide and as fast as the analytical engine would probably be larger than the analytical engine.

We can see how to do reliable quantum computation in principle. The overhead of error correction makes it daunting in scale. It sure would be nice if someone came along and invented the quantum computing equivalent of a vacuum tube or a transistor.

[1]: https://csferrie.medium.com/quantum-computing-worst-case-sce...

[2]: https://medium.com/tech-is-a-tool/building-the-modern-comput...

[3] "How to factor 2048 bit RSA integers in 8 hours using 20 million noisy qubits" https://quantum-journal.org/papers/q-2021-04-15-433/