Low-Depth Random Unitaries without Ancillae

In the quantum world, randomness is not just a lack of order; it is a powerful tool. Just as a well-shuffled deck of cards is essential for a fair game, a truly random arrangement of quantum states is the foundation for many advanced technologies, from ultra-precise sensors to unbreakable codes. Scientists use these random arrangements, known as unitaries, to test how well quantum computers work, to measure tiny physical changes, and to understand how information spreads through complex systems. However, creating a perfectly random quantum state is incredibly difficult. The most natural way to do it requires a number of steps that grows so fast with the size of the system that it becomes impossible to perform on any machine we can build today. To get around this, researchers use "designs," which are clever shortcuts. These are circuits that are not perfectly random but mimic the statistical behavior of true randomness closely enough for practical use. The goal has always been to make these shortcuts as short and simple as possible, using the fewest steps and the least amount of hardware.

For years, a major obstacle stood in the way of making these shortcuts efficient. The most effective methods known to science required a massive amount of extra space. To generate a random design on a system of a certain size, these methods demanded a vast number of additional, unused quantum bits, often far more than the system itself contained. This spatial overhead was a severe bottleneck, making many advanced protocols impractical for real-world devices where space is at a premium. The central question became whether it was possible to achieve the same high-quality randomness without borrowing this extra space, using only the qubits that were already part of the system.

A team of researchers at Tsinghua University has now answered this question with a definitive yes. They have developed a new method to generate these random quantum designs that requires no extra space at all. Their approach works for systems of any size and on various physical layouts, including those where every part can talk to every other part. The team proved that they can create these designs in a number of steps that is essentially the best possible, scaling efficiently as the system grows. For systems arranged in a grid-like structure, the number of steps grows slowly with the size of the system, and for systems where everything is connected, the steps grow even more slowly. Crucially, this efficiency is achieved without adding a single extra quantum bit.

The researchers achieved this by rethinking how randomness is built. Instead of trying to generate complex random phases for every possible state, which is computationally expensive, they used a strategy based on testing whether groups of states are identical. They found that they could approximate these tests using a series of simple, randomized checks that could be performed directly on the system's own qubits. By borrowing inactive parts of the system temporarily to help with the calculation and then returning them exactly as they were, they avoided the need for permanent extra storage. This technique, known as catalytic computation, allowed them to perform complex arithmetic operations without leaving any trace or requiring extra hardware.

Once they had a method to create a very good approximation of a random design, the team took a further step to make it perfect. They showed that by simply adjusting the probability of choosing certain circuits from their collection, they could turn their approximate design into an exact one. This exact design replicates the behavior of true randomness with zero error, a significant improvement over previous methods that required exponentially more resources to achieve the same level of precision. The result is a set of instructions that can be run on current and future quantum devices to generate high-quality randomness with minimal time and space costs.

This breakthrough has immediate implications for a wide range of quantum tasks. Protocols that rely on random measurements, such as those used to estimate the properties of quantum states or to benchmark the performance of quantum gates, can now be run much more efficiently. The new method removes the need for the vast amounts of extra memory that previously made these tasks difficult or impossible on near-term devices. By minimizing the space and time required, the researchers have opened the door to more complex experiments and more reliable quantum technologies, bringing the promise of quantum advantage closer to reality.