Post

Building a utility-scale quantum computer that can crack one of the most vital cryptosystems—elliptic curves—doesn’t require nearly the resources anticipated just a year or two ago, two independently written whitepapers have concluded. In one, researchers demonstrated the use of neutral atoms as reconfigurable qubits that have free access to each other. They went on to show this approach could allow a quantum computer to break 256-bit elliptic-curve cryptography (ECC) in 10 days while using 100 times less overhead than previously estimated. In a second paper, Google researchers demonstrated how to break ECC-securing blockchains for bitcoin and other cryptocurrencies in less than nine minutes while achieving a 20-fold resource reduction. Taken together, the papers are the latest sign that cryptographically relevant quantum computing (CRQC) at utility-scale is making meaningful progress. The advances are largely being driven by new quantum architectures developed by physicists and computer scientists in a push to create quantum computers that operate correctly even in the presence of errors that occur whenever qubits—the quantum analog to classical computing bits—interact with their environment. The other key drivers are ever-more efficient algorithms to supercharge Shor’s algorithm, the 1994 series of equations proving that quantum computing could break the ECC and RSA cryptosystems in polynomial time, specifically cubic time , far faster than the exponential time provided by today’s classical computers. Neither paper has been peer-reviewed. Read full article Comments

No, the sky isn’t falling, but Q Day is coming, and it won’t be as expensive as thought.

“The research community continues to make steady progress on both the physical qubits and the quantum algorithms necessary to realize an efficient and practical CRQC,” said Brian LaMacchia, a cryptography engineer who oversaw Microsoft’s post-quantum transition from 2015 to 2022 and now works at Farcaster Consulting Group. “I don’t think either paper gives us a new, hard date for when we’re going to have a practical CRQC (which of course we’ve never had), but they both provide evidence that we are continuing to march down the road to a realizable CRQC and progress toward that goal is not slowing down.”

The paper that is getting the most attention takes a relatively new approach to creating fault-tolerant quantum computing (FTQC) that can reduce the number of physical qubits required to break ECC by a factor of 100. Unlike more common approaches based on superconducting, the researchers built physical qubits out of neutral atoms. Using lasers to cool atoms, the process traps individual atoms into tightly focused beams of light known as “optical tweezers.” Each tweezer snags a single atom. Using optical multiplexing, the researchers can make large arrays of these trapped atoms.

The benefit of this approach is that all physical qubits can interact with all other physical qubits. These “non-local” communications are a major departure from qubit interaction in superconducting approaches, where qubits are laid out on a 2D grid and can interact with only their four immediately adjacent qubit neighbors. The ability for qubits to interact with very far-away qubits makes error correction significantly more efficient, since non-local communication allows for drastically increasing the number and thoroughness of fault checks.