Re: NANO: Amazing, isn't it?

Eliezer Yudkowsky (
Sun, 02 Feb 1997 14:50:58 -0600

> There exists another fun calculation that allows you to find the x:th
> digit of pi in O(something small) without calculating the previous d-1
> digits, this has been used to calculate the ten billionth digit of pi; see

Ah. Then given 64 qb, you could search every 1000 consecutive digits of
pi for hidden messages for the first sixteen billion billion digits of
pi, in (of course) the same time it would take to search any 1000

> I wonder if there is some way of calculating pi faster on a quantum
> computer.
Easy as... I can't say it. But any way, yeah, assuming you have 4GB
quantum-writable memory, and a 32qb processor, you can assign each
branch a byte of memory to write to, and calculate the first 330 billion
digits of pi in very little time. On the other hand, you only need a
trivial amount of memory, like a few KB of QRAM, to check for secret
messages as much of pi as you have the qubits for. Assuming that only
one branch of reality indicates success.

That brings me to a question: What do we need for quantum-writable
memory? Anything exotic? And by the way, why do we need (say) 45
qubits to factor a 15-bit number? Shouldn't 15 qubits be enough to test
every possible divisor of a 15-bit number?

--       Eliezer S. Yudkowsky

Disclaimer:  Unless otherwise specified, I'm not telling you
everything I think I know.