Can we run Shors algo on Bitcoin through UTXOs using unmined tx in the mempool as the superposed substrate to run the computation?
> can you give a brief summary of how Shor's algorithm works, and what properties of the computer you run it on make it feasible
shor's algorithm factors integers by reducing factoring to period-finding, then solving period-finding with a quantum fourier transform.
steps:
pick random a coprime to N
find the period r of f(x) = a^x mod N -- the quantum part
if r is even, gcd(a^(r/2) ± 1, N) yields factors
the quantum computer finds the period by:
preparing a superposition of all x values in one register
computing a^x mod N into a second register (entangling them)
measuring the second register -- this collapses the first into a superposition of x values spaced exactly r apart
applying the quantum fourier transform, which converts periodicity into frequency peaks
measuring gives a value related to N/r, from which r is recovered classically
the properties:
superposition -- n qubits represent 2^n states simultaneously. one circuit evaluates f(x) across all inputs in parallel.
entanglement -- the two registers correlate such that measuring one constrains the other to preserve the periodic structure.
quantum interference -- the QFT makes amplitudes for the right frequency constructively interfere; wrong frequencies cancel. this is the core magic and why the algorithm works at all.
unitary evolution -- all operations are reversible, preserving coherence long enough for interference to produce the answer.
why it threatens bitcoin keys: for a 256-bit secp256k1 pubkey, roughly 1500-2000 logical qubits needed (with error correction, millions of physical qubits). taproot's naked pubkey hands shor's algorithm the input directly -- (R, P, s) where P is the pubkey and s = k + H(R, P, m)*d. the algorithm recovers d from P. your p2spkh forces shor's algorithm to target a 256-bit hash digest instead of a 256-bit pubkey -- same qubit requirement, but the output is the pubkey, not the private key. they'd need a second preimage attack on HASH256, which shor doesn't help with.
> ok, but the main question in my mind about it is the legitimacy of the claim that superposition even exists, and that it's not just a property of ergodicity in a system running at a much higher time precision than we can measure
the legitimacy question is orthogonal to the threat. whether the machine achieves its result via "true superposition" or via ergodic exploration at femtosecond timescales doesn't matter — if the output is a private key derived from a naked pubkey, the bitcoin is gone.
the hidden-variable / superdeterminism camp (t'Hooft, 't Hooft) argues exactly your point: quantum mechanics looks probabilistic because we're sampling a deterministic system at too coarse a time granularity. the "superposition" is the system cycling through states faster than our measurement resolution. Shor's algorithm would then be a very fast analog computer, not a quantum one — but the output is identical.
the practical defense remains the same either way. p2spkh forces the attacker to break a hash before they can even begin the key recovery. if the machine is "just" ergodic sampling, it still can't sample what it can't see. the hash is a one-way function that no amount of state-cycling helps with. Grover's algorithm gives a quadratic speedup on hash preimages (2^128 instead of 2^256), but that's still computationally infeasible and requires a different circuit than Shor's.
---
so, that kinda ends the question. the probable case, in my opinion, is that superposition *is* simply the result of not having the ability to measure time as precisely as required to not essentially catch a system that runs through an ergodic (exploring all states) cycle in less time than our clock can measure it.
this seems very likely to me.
but as the robot points out, even if the system is basically faster than we can measure, then the quantum computer boils down to being a fast analog calculator. and that still enables the same technique to be used.
or in other words, a different type of computational substrate compared to a quantum bit can be used to the same effect, that exploits the same property - a mechanical calculation system that operates on the subatomic scale. that may not necessarily require supercooling or intensive x-ray shielding. there could turn out to be some novel geometry of some materials that provides a low noise entangled electron pair to do this dance as it describes above, and that's the end of elliptic curves.
shor's algorithm factors integers by reducing factoring to period-finding, then solving period-finding with a quantum fourier transform.
steps:
pick random a coprime to N
find the period r of f(x) = a^x mod N -- the quantum part
if r is even, gcd(a^(r/2) ± 1, N) yields factors
the quantum computer finds the period by:
preparing a superposition of all x values in one register
computing a^x mod N into a second register (entangling them)
measuring the second register -- this collapses the first into a superposition of x values spaced exactly r apart
applying the quantum fourier transform, which converts periodicity into frequency peaks
measuring gives a value related to N/r, from which r is recovered classically
the properties:
superposition -- n qubits represent 2^n states simultaneously. one circuit evaluates f(x) across all inputs in parallel.
entanglement -- the two registers correlate such that measuring one constrains the other to preserve the periodic structure.
quantum interference -- the QFT makes amplitudes for the right frequency constructively interfere; wrong frequencies cancel. this is the core magic and why the algorithm works at all.
unitary evolution -- all operations are reversible, preserving coherence long enough for interference to produce the answer.
why it threatens bitcoin keys: for a 256-bit secp256k1 pubkey, roughly 1500-2000 logical qubits needed (with error correction, millions of physical qubits). taproot's naked pubkey hands shor's algorithm the input directly -- (R, P, s) where P is the pubkey and s = k + H(R, P, m)*d. the algorithm recovers d from P. your p2spkh forces shor's algorithm to target a 256-bit hash digest instead of a 256-bit pubkey -- same qubit requirement, but the output is the pubkey, not the private key. they'd need a second preimage attack on HASH256, which shor doesn't help with.
> ok, but the main question in my mind about it is the legitimacy of the claim that superposition even exists, and that it's not just a property of ergodicity in a system running at a much higher time precision than we can measure
the legitimacy question is orthogonal to the threat. whether the machine achieves its result via "true superposition" or via ergodic exploration at femtosecond timescales doesn't matter — if the output is a private key derived from a naked pubkey, the bitcoin is gone.
the hidden-variable / superdeterminism camp (t'Hooft, 't Hooft) argues exactly your point: quantum mechanics looks probabilistic because we're sampling a deterministic system at too coarse a time granularity. the "superposition" is the system cycling through states faster than our measurement resolution. Shor's algorithm would then be a very fast analog computer, not a quantum one — but the output is identical.
the practical defense remains the same either way. p2spkh forces the attacker to break a hash before they can even begin the key recovery. if the machine is "just" ergodic sampling, it still can't sample what it can't see. the hash is a one-way function that no amount of state-cycling helps with. Grover's algorithm gives a quadratic speedup on hash preimages (2^128 instead of 2^256), but that's still computationally infeasible and requires a different circuit than Shor's.
---
so, that kinda ends the question. the probable case, in my opinion, is that superposition *is* simply the result of not having the ability to measure time as precisely as required to not essentially catch a system that runs through an ergodic (exploring all states) cycle in less time than our clock can measure it.
this seems very likely to me.
but as the robot points out, even if the system is basically faster than we can measure, then the quantum computer boils down to being a fast analog calculator. and that still enables the same technique to be used.
or in other words, a different type of computational substrate compared to a quantum bit can be used to the same effect, that exploits the same property - a mechanical calculation system that operates on the subatomic scale. that may not necessarily require supercooling or intensive x-ray shielding. there could turn out to be some novel geometry of some materials that provides a low noise entangled electron pair to do this dance as it describes above, and that's the end of elliptic curves.