Randomness is essential to some research, but it’s always been prohibitively complicated to achieve. Now, we can use “pseudorandomness” instead.

Nothing is certain in the quantum realm. A particle, for example, can exist in multiple quantum states simultaneously. The same goes for a quantum bit, or qubit — the basic unit of information used in quantum computing. The act of measurement causes these objects to collapse into a single state, and usually the best you can do is calculate the probability of a particular outcome.

The unpredictability at the heart of the quantum realm has been immensely useful for computing and cryptography, where experts have learned to harness randomness as a tool. But as useful as it is for quantum circuits to incorporate true randomness, it’s a difficult state to achieve, with steep costs. “Generating randomness is pretty expensive,” said William Kretschmer(opens a new tab), a researcher at the Simons Institute for the Theory of Computing who studies quantum complexity.

As a result, quantum researchers have long wanted to see if they could possibly fake that randomness. They wanted to build “pseudorandom” quantum circuits, which seem to be truly random but can nonetheless be constructed relatively simply and manageably. The only problem was that no one knew if it was possible to actually build one.

After years of uncertainty, two researchers posted a paper last October(opens a new tab) that proved that it is in fact possible to construct such a circuit. Their work provides an elegant and secure way to represent quantum randomness that’s indistinguishable from the real thing, without the enormous computational load — though it’s only possible in a world where some basic theoretical assumptions of cryptography are correct. The proof could open new doors for quantum computing and cryptography research.

“Before this recent result on pseudorandom [circuits], we didn’t have good evidence that they actually exist,” said Alexander Poremba(opens a new tab), a quantum computing researcher at the Massachusetts Institute of Technology who was not involved with the new paper. Now, “for the first time, we have very good evidence that pseudorandomness is a real concept.”

...read more at quantamagazine.org