Recent research has provided the first robust clue that it is possible to build “pseudorandom” quantum circuits that can produce results that only appear to be random but aren’t, and which are almost indistinguishable from truthfully random results in quantum systems.
The findings could lead to major advances in quantum computing and cryptography, and make quantum simulations of complex quantum systems, such as black holes, significantly more efficient.
Previous attempts to prove the existence of pseudorandom quantum circuits, known as pseudorandom unitaries (PRUs), have failed to provide empirical evidence that convinced the scientific community.
The new findings, which rely on presumed mathematical properties of cryptography known as one-way functions, prove the existence of PRUs in what is considered to be a significant step forward in theoretical computer science.
