Randomness takes time. If you’re playing a card game with a standard 52-card deck, shuffling the cards just once or twice isn’t enough to mix them up. A quick-thinking and attentive opponent could make meaningful guesses about the cards’ post-shuffling order.
For most card games played by humans, seven riffle shuffles (the type shown in figure 1) suffice to mix a standard deck. But it doesn’t completely randomize the cards: Some of the 52! (about 8 × 1067) possible orders are still significantly more probable than others. If a uniform likelihood over all possible orders is your goal, you need to keep shuffling much longer.
New theoretical work by Thomas Schuster, Hsin-Yuan Huang (both at Caltech), and Jonas Haferkamp (of Saarland University in Germany) highlights the enormous gap between “truly random” and “random enough for practical purposes” in the quantum realm. It was already known that for a randomly chosen quantum circuit to truly scramble an n-qubit state, the complexity of the circuit needs to grow exponentially with n: If the number of qubits is doubled, the number of layers in the circuit is squared. Like any exponentially growing function, it quickly becomes unwieldy for large inputs.
Schuster, Huang, and Haferkamp proved that one can achieve a sufficiently scrambled state with a much, much smaller circuit.1 A practically random circuit, indistinguishable from an exponentially sized one, can be built with a number of layers that scales just logarithmically with n: Squaring the number of qubits merely doubles the number of layers.
To read more, click here.