Eli Ben-Sasson

Quantum Computers Explore Many Possibilities Simultaneously

Quantum Computer -- how does it work? You've read the news -- a quantum computer could some day break the cryptography used to sign Bitcoin transactions. We can fix Bitcoin to prevent that, but it's really important to understand: How does it work? How would a quantum computer solve problems that we can't solve today? This is a dumbed-down explanation, written by someone who is *not* a quantum expert. So, how does it work? The Universe works in mysterious ways. And none more mysterious than quantum mechanics. The way I picture it is like this: The state of the universe in 1 second from now is a bit like jello, it takes time for it to stabilize. During this time -- when it's not final/stable --particles (like electrons) are not quite here or there. The correct description of the universe is that there's a multitude of different possibilities, that are all real, and later on, one of these possibilities turns up as reality. Now, think about a computer trying to guess your Bitcoin spending key (those 24 words that control your money). For each one of these 24 words, there are many possibilities. A non-quantum computer would pick one of these possibilities for the first word, like one path in a maze, and then continue to the next word, and so on and so forth until it picked a value for each of the 24 words. If the computer picked your correct value, it's like it reached the exit to the maze. If it's incorrect, the computer hits a dead end and will backtrack and try some other combination. This computer can continue to try different combinations (like different paths in a maze) until it finds the correct one. But there are so many possibilities, the sun will freeze before a computer goes over all of them to find your spending key. This is why the computers we know today don't pose a threat to Bitcoin. But now consider a quantum computer -- It uses the unfinalized nature of reality, this jello-like behavior, to simultaneously explore all possible paths in the maze. Most of these paths reach a dead end and "die". Only a few paths (maybe only one) reaches the exit and remains to live. When reality, this jello, finally settles, it settles only on viable paths that leave the maze. And that's how a quantum computer will get to efficiently guess your spending key and steal your Bitcoin. FOR NEXT LESSON: How could *any* cryptography survive a quantum computer? Is there a way to use keys that cannot be stolen by the all-powerful quantum computer? SPOILER: Not all cryptography is breakable. In particular, ZK-STARKs, (the technology I co-invented and which powers Starknet) is not breakable by a quantum computer.