RE: Can Quantum Computers Break Bitcoin?
Because SHA-256 is a bit-mixing algorithm, I don't think quantum computing would lend itself to cracking it any easier than traditional means. I haven't seen any algorithm suggested that would help to solve any hashing algorithm. IOW, QC isn't magic that spits out results for any given problem.
I think QC will even have a problem solving the Discrete Logarithm Problem for Elliptic Curve, because each point in the field is random compared the the adjacent scalar values in the underlying group.
EC is like having a huge stack of papers that are all in the wrong order. For example, the first page may be labeled 1,323, the second page is labeled 75, the third page is 7,888... etc. You can easily count through the stack to find the 75th piece of paper, and tell somebody that it is page number 999. Given that page number, they will have a hard time telling you that it's the 75th piece of paper in the stack. This is the EC DLP.
Now take that stack of papers and extend it so that it goes to the Andromeda galaxy that is 2.537 million light years away. That's only about an 85-bit number of pages. Double that distance (5 million light years), and that's an 86-bit number. We use 256 bits for Bitcoin and most other cryptocurrencies.
Where QC shines is for solving the DLP or factoring of RSA because each value is the value (no weird translation to another coordinate space, like EC requires). This is what the famous Shor algorithm helps to solve.
(Writing this comment inspired me to also create a blog post using the stack of papers metaphor: Introducing the Elliptic Curve Discrete Log Problem)
Thanks for the detailed comment - learned a lot just digging in based on your jumping off points. Followed and upvoted.
These metaphors are useful for understanding
Thanks a lot for clarifying this - based on what you are saying, the risks of quantum computing aren't nearly as bad as if it's some kind of linear computing power issue.
I think there's a lot of misunderstood hype about what quantum computing can actually do.
Don't get me wrong - for certain problems, it will be orders of magnitude more efficient than traditional computing, and this is very cool stuff! But, it's not magic - that's my bigger point.
Maybe somebody will come up with an algorithm in the future for some of the problems that I mentioned, and maybe QC will only be used to solve a small piece of that algorithm (that's its role even in the Shor algorithm - you still need a classical computer for a lot of the factoring work).
But, given the information that I've been able to find today, I don't fear that SHA-256 or EC DLP will be broken by QC any time soon. Time will tell!
Thanks for commenting on this. Your explanation is clear and helpful.