FQ is OK with me, please move it if you think it fits better than in MPSIMS.
I wonder if the OP was inspired to ask based on this news making the rounds this week:
No, I was not, I don’t usually read crypto-news sites, but it goes in the direction I was musing. If the problem is so obvious that even me, a complete aficionado, can figure out that there could be trouble ahead the professionals must be aware of that too. Nice to know that the general direction of my thinking is not completely off base. A bit sad to see that cryptocurrencies are not going to collapse tomorrow. Probably.
I would suggest that, if quantum computing continues to progress, this is a sticking plaster that will not stop the bloodbath.
The threat to Blockchain is just an example of technological advancements challenging our security and systems. It’s an arms race and some security solutions will inevitable hit a brick wall.
Another example of the arms race in action:
Done.
Thanks! I was overthinking when I put it in MPSIMS. It does fit better here indeed. 
Is there anything where there is a mathematical proof that something has no classical solution, but where it is believed that this may not hold for quantum?
There are certainly threats to the security of most cryptocurrencies from quantum computers, as well as to most forms of currently used encryption in general. However, these threats are well known, and there are active mitigation measures—NIST has begun evaluation of ‘quantum safe’ encryption methods in 2016, and has introduced standards as well as migration timelines (deprecation of unsafe methods by 2030, and fully disallowing them by 2035). So there are already active efforts to mitigate the problem.
Of course, there is significant uncertainty as to the actual timelines in play. There have been recent algorithmic breakthroughs that have significantly reduced the resource estimates for breaking current encryption methods (both integer factorization based RSA, which secures most internet traffic, and elliptic curve/discrete logarithm based methods), from needing a quantum computer with ~20,000,000 qubits to needing only ~1,000,000 or even 100,000 qubits with a specific architecture (500,000 for elliptic curves). (Current devices, depending on architecture, are on the order of ~1,000 qubits.) It remains to be seen whether these breakthroughs make their way from the drawing board into the real world, but as one data point, Google (whose researchers are behind some of these breakthroughs) has publicly stated that they have accelerated their timeline for migration to quantum-safe encryption internally to 2029. Since this is a process that probably won’t come cheap, they seem to put at least some stock in their own hype. Also, Android 17 will ship with native support for post-quantum cryptography.
(Anyhow, I’m a researcher in quantum computing, so if there are any further questions, I’d be happy to try and answer them.)
Depends on what you mean by that. In principle, quantum and classical computers compute all the same things (i.e. the set of computable functions is the same for both paradigms), however, the complexity (how much the computation time and/or resources increase if the input size increases, roughly) may scale differently in certain cases. The most well-known of these cases is integer factorization, which is what underlies (most) current cryptography, such as RSA. There, it is strongly conjectured that the best classical algorithms take exponential time (well, sub-exponential, technically), while Shor’s algorithm takes polynomial time on a quantum computer (exponential and polynomial here are to be understood such that the time it takes to solve an instance of size n grows exponentially or polynomially with n). There currently is no known classical algorithm that can equal the performance of the quantum algorithm, but there is no proof that such an algorithm doesn’t exist—however, we’re sure enough that none does that we wager essentially the whole of global cybersecurity on that assumption.
There are, however, cases where a provable speedup for quantum computing exists. The most well-known example is searching through an unstructured database for a particular element: if there are n elements in the database, you’d have to make \frac{n}{2} comparisons to find what you’re looking for on average using a classical strategy, but a quantum algorithm (Grover’s algorithm) exists that needs only ~\sqrt{n} steps. That’s a far more modest speedup than in the case of Shor’s algorithm, but this also yields an ‘one size fits all’ improvement for a large class of problems: any problem that is difficult to solve, but where the solution is simple to verify (like integer factorization, because multiplication is fast), receives a speedup by just checking all possible solutions. There are also examples of greater provable speedups, such as for the game Mastermind.
While this isn’t something that classical computers can’t do, for relevant problem sizes, they may take millions of years, while a quantum computer achieves the result within hours (see here for an interesting visualization). But depending on your definitions, there may also be things that quantum computers can do, that no classical ones can. This point was first raised by Feynman, who stated that ‘it is impossible to represent the results of quantum mechanics with a classical universal device’. A simple example is randomness: if quantum mechanics is genuinely random (and there are good reasons to think it is), then no classical computer can account for quantum measurement outcomes. There are also quantum systems that show properties corresponding to classically undecidable questions, most notably the question whether a quantum system has a finite difference in the energies of its ground state and first excited state. One may be divided regarding the significance of this and similar results, however—after all, undecidable questions also arise in classical systems (albeit, to the best of my knowledge, only regarding the long-term behavior of systems, such as the question of whether a certain configuration is ever achieved, not in their properties).
All it will take for a massive movement to quantum safe forms of TLS (https encryption) is for Google to announce they will be downranking non-quantum safe websites. This is the same as the big increase in encrypted websites 10+ years ago when Google started downranking unencrypted websites.