Of course, these results are all still formulated in the oracle setting, but it looks plausible that instantiating with primitives like AES will carry them over into the real world.

[1] https://link.springer.com/article/10.1007/s001459900025

[2] https://ieeexplore.ieee.org/document/6400943

[3] https://link.springer.com/chapter/10.1007/978-3-031-07082-2_17

You’d think that a large language model – a black-box if I’ve ever seen one – whose output is supposedly indicative of an adversarial stance towards organic life, would be the perfect problem for something like GA.

In the movies we’d be using large FTQCs to determine if an LLM could ever press the button.

Imagine the funding you’re missing out on. đź™‚

Alas, the model input is far too large for GA’s speedup to matter even in ideal conditions?

Hey, maybe that’s the alternative to pausing AI research, just restrict the size of the input such that the model can be shown to be safe.

My question is, could you do better than GA?

]]>But what about:

\( U(t) = |l(0)\rangle \langle l(0)| + q(r)|l(1)\rangle \langle l(1)| \) vs. \( U(t+e) = |l(0)\rangle \langle l(0)| + q(r+e)|l(1)\rangle \langle l(1)| \).

for some qubit encoding l.

How can QEC correct these type of precision errors? Are functional fault tolerant quantum computers not perceptible to these type of errros?

]]>Isn’t Grover highly susceptible to this type of error as well? Any resources that explain how FTQC is able to specifically make analog phases in the logical subspace error free?

]]>bitcoin mining is the problem of finding a nonce given a header such that, SHA256(header, nonce) < threshold. This condition can be expressed as a classical boolean circuit that outputs true or false with the input being a nonce. This can be trivially converted into a reversible quantum circuit which can be used as an oracle for grover.

Classically, the problem requires T = 2^256/threshold hash evaluations to find a solution with high probability. With grover, it should take ~sqrt(T) steps on a fault tolerant QC to find a solution w.h.p.

This concrete problem above does not depend on any philosophical disagreement about nature of oracles / black boxes and quantum databases. I haven't read the new paper, does it give any evidence for a faster classical algorithm or refute the runtime of grover? If not, I don't see any reason to.

]]>On the fourth hand, an AGI singularity (looking more and more likely in our lifetimes) would be an event horizon beyond which any sort of breakthrough prediction gets even more difficult.

]]>So, I dunno, maybe I’ll give it 50/50? But note that the Grover speedup could be “real” in the sense I care about, even if the probability of exploiting it in my lifetime were much smaller than that—just like the principles of heavier-than-air flight were real in 1700, as someone aptly pointed out above.

]]>