Hey there, quantum cryptography researcher here. I've written extensively on the subject: #735909 #1288781 #1453183 #1419471

Nobody can answer the question "When will quantum computers be powerful enough to threaten classical cryptography?". You're right to be skeptical of anyone who claims the threat is imminent without proof. But i would like to dispell a few inaccurate notions in your post and its comments.

First, facts only:

• Private keys aren't stored on the blockchain. A private key is just a big number, which you either know, or you don't.
• Public keys are sometimes stored on the blockchain. A public key is another big number, mathematically related to its private key. If you have the private key, you can create signatures which spend any bitcoins locked to your public key.
• If you have a big quantum computer, you can run Shor's algorithm to factor a public key into its private key.
• You cannot use a quantum computer to efficiently invert a strong hash function like SHA256. It gets easier, but is still thought to be intractable.
• Many public keys are exposed on the blockchain, including those of Satoshi's coins and of big exchange cold wallets. See this dashboard (explainer).
• Most NATO-aligned governments (US, UK, EU, AU) have deadlines to migrate fully to post-quantum crypto and disallow the use of quantum-vulnerable algorithms by 2035.

Now some corrections:

a hard fork involving hashing algorithm change would be the most effective solution

We do not need to change Bitcoin's block-mining hash algorithm any time soon. Grover's Algorithm gives at best a mild speedup over classical computers. IF in the distant future quantum computers start threatening classical mining, they will be a centralizing force (due to the nature of QCs, see https://stephanlivera.com/episode/670/), and we should soft fork in a change of hash algorithm (no hard fork needed).

For one, quantum proof bitcoin exists (I've never confirmed but heard from multiple sources).

There are quantum-resistant sidechains pegged to bitcoin, but their bridges are still vulnerable to sufficiently advanced quantum computers. At best they are a stopgap. There are suggestions which use newly proposed opcodes like OP_CAT to implement PQ-safe address formats. There are BIPs currently being drafted which may someday introduce explicit PQ-safe cryptography opcodes.

But AFAIK there is no consensus mechanism on bitcoin (mainnet) in existence today which fully secures coins against big quantum computers (QCs). At best you can avoid being the low-hanging fruit by using hashed addresses and spreading your coins out among many smaller UTXOs.

Any wallet that has not sent any money has not published a key to crack.

Correct, but that's not why people are worried.

In total about a third of all bitcoins which will ever exist are currently locked to pubkeys which are exposed on-chain. Even if your coins stay secure in a hashed address, a QC could steal a large portion of the Bitcoin supply because many coins are pubkey-exposed, and are (conjecturally) held by dead hands who can make no moves to rescue them. So this inheritance falls to the first organization to aim a sufficiently big QC at it.

The FUD comes from the idea of supply flooding: That if a QC attacker wanted to, they could flood the market selling stolen dormant bitcoins and crash the value of bitcoin, at least in the short term.

Whether this would actually happen is unknown - We can't know what the motivation of a QC attacker would be (see this article for an examination of that question), or what legal precedent such an attacker would use to justify mass theft, or whether exchanges would permit such high volume from a single customer who is clearly malicious. I think most of the FUD comes from fear of the many unknown outcomes of that scenario.

The good news is that scalable and quantum-safe signature schemes exist, which can replace the current quantum-vulnerable scheme used today, and they're only going to get better. So most people have no reason to worry. Just hodl tight in hashed addresses and move to PQ-safe addresses once they become available.