A 鈥渦seless鈥� algorithm that serves as a benchmark for demonstrating the power of quantum computers over ordinary devices could potentially be repurposed as a way to keep data secure from, ironically, quantum computers.
Quantum computers have long threatened to crack existing encryption algorithms, which rely on problems that are difficult for classical computers to solve, such as finding the prime factors of a large number. A sufficiently big quantum computer could do this, but at the University of Chicago, Illinois, and his colleagues .
Their idea is based on determining the output of a random quantum circuit executed on a quantum computer. Such an output is easy to check if you know what the circuit looks like, but figuring out the shape of the circuit from the output alone is very difficult.
Advertisement
This random circuit sampling (RCS) algorithm is already used as a kind of benchmark for quantum computers, to identify the point at which they achieve quantum advantage 鈥� where a quantum computer becomes able to do something that no classical computer can. Because it was thought that this algorithm had no particularly useful purpose, such efforts have been criticised as somewhat pointless, so finding an application in encryption would be rather handy.
There is just one problem: claims of quantum advantage have often been rebuffed at a later date when it turned out classical computers could solve RCS after all, meaning the problem may not be 鈥渉ard鈥� enough to be used in cryptography. The first claim of quantum advantage came from Google in 2019, when the company said its Sycamore quantum computer could perform calculations that would take even the world鈥檚 most powerful classical supercomputer 10,000 years to complete. This was swiftly refuted, twice, by different groups working on classical machines.
Fefferman says the jury is still out on whether RCS is a genuinely hard problem, but this is also true of current encryption methods. Cryptography builds confidence over time by showing that despite the large incentives 鈥� being able to siphon off secrets and money on a grand scale 鈥� nobody has yet found a way to crack encryption schemes, he says.
鈥淚 totally expect that there will be some back and forth in the community about new quantum algorithms that can learn some class of quantum circuits,鈥� says Fefferman. Those classes would then be excluded from the possible circuits chosen by the algorithm, he says. 鈥淎s soon as we have some ensemble that is difficult to learn, we can use that for cryptography.鈥�
at the US National Institute of Standards and Technology (NIST) says the proposed encryption method 鈥�looks like a very cool application鈥�, but it isn鈥檛 necessarily practical today given the current computational capabilities of quantum computers.
