91影视

The time it takes local quantum dynamics to "look globally random" is a fundamental question in quantum information theory. In particular, one is often interested in how long it takes before systems reproduce the first few moments of the uniform measure on the relevant group of dynamics; such a system is called a design. Remarkably, in the symmetry-free case it is now known that one can obtain designs after only a time logarithmic in the system size! Here we consider instead the case of the orthogonal, symplectic, Clifford, and matchgate groups, and show that (on a one-dimensional lattice) designs cannot form in sublinear time, constituting an exponential slowdown over the symmetry-free case. Strangely, our results show that no ensemble of one-dimensional local dynamics can reproduce the first few moments of the aforementioned groups in sublinear time, even if they are allowed to leave the group whose moments they are trying to reproduce. This is strange! For example, the matchgate group corresponds to dynamics which are dramatically simpler than the generic case, and yet we show that reproducing its random characteristics takes exponentially longer, even when the ensemble doing the reproducing is itself under no constraints beyond locality. These results also implies that, for these groups, the known linear-depth design constructions are optimal.

Finally, we show that if we drop the requirement that the circuits be constrained to a one-dimensional lattice, we can recover logarithmic-depth designs in the matchgate case. For designs matching upto the first three moments our construction is optimal; more generally it is nearly optimal. This has significant implications for the running time of certain quantum algorithms which are hoped to be applied to questions in quantum chemistry on relatively near-term quantum computers. Indeed, these algorithms often require sampling a random matchgate; our results show that one a one-dimensional lattice this is exponentially more costly than one would naturally have thought, and that all-to-all connected quantum computers can enjoy an exponential speedup over their one-dimensional counterparts for such problems.