Nicholas Hunter-Jones

We consider random quantum circuits (RQC) on arbitrary connected graphs whose edges determine the allowed 2-qudit interactions. Prior work has established that such n-qudit circuits with local dimension q on 1D, complete, and D-dimensional graphs form approximate unitary designs, that is, they generate unitaries from distributions close to the Haar measure on the unitary group U(q^n) after polynomially many gates. Here, we extend those results by proving that RQCs comprised of O(poly(n,k)) gates on a wide class of graphs form approximate unitary k-designs. We prove that RQCs on graphs with spanning trees of bounded degree and height form k-designs after O(|E|n rm poly(k)) gates, where |E| is the number of edges in the graph. Furthermore, we identify larger classes of graphs for which RQCs generate approximate designs in polynomial circuit size. For k łeq 4, we show that RQCs on graphs of certain maximum degrees form designs after O(|E|n) gates, providing explicit constants. We determine our circuit size bounds from the spectral gaps of local Hamiltonians. To that end, we extend the finite-size (or Knabe) method for bounding gaps of frustration-free Hamiltonians on regular graphs to arbitrary connected graphs. We further introduce a new method based on the Detectability Lemma for determining the spectral gaps of Hamiltonians on arbitrary graphs. Our methods have wider applicability as the first method provides a succinct alternative proof of [Commun. Math. Phys. 291, 257 (2009)] and the second method proves that RQCs on any connected architecture form approximate designs in quasi-polynomial circuit size.

Abstract We consider quantum circuits consisting of randomly chosen two-local gates and study the number of gates needed for the distribution over measurement outcomes for typical circuit instances to be anti-concentrated, roughly meaning that the probability mass is not too concentrated on a small number of measurement outcomes. Understanding the conditions for anti-concentration is important for determining which quantum circuits are difficult to simulate classically, as anti-concentration has been in some cases an ingredient of mathematical arguments that simulation is hard and in other cases a necessary condition for easy simulation. Our definition of anti-concentration is that the expected collision probability, that is, the probability that two independently drawn outcomes will agree, is only a constant factor larger than if the distribution were uniform. We show that when the 2-local gates are each drawn from the Haar measure (or any two-design), at least O(n log(n)) gates (and thus O(log(n)) circuit depth) are needed for this condition to be met on an n qudit circuit. In both the case where the gates are nearest-neighbor on a 1D ring and the case where gates are long-range, we show O(n log(n)) gates are also sufficient, and we precisely compute the optimal constant prefactor for the n log(n). The technique we employ relies upon a mapping from the expected collision probability to the partition function of an Ising-like classical statistical mechanical model, which we manage to bound using stochastic and combinatorial techniques.

Random quantum circuits are proficient information scramblers and efficient generators of randomness, rapidly approximating moments of the unitary group. We study the convergence of local random quantum circuits to unitary k-designs. Employing a statistical mechanical mapping, we give an exact expression of the distance to forming an approximate design as a lattice partition function. In the statistical mechanics model, the approach to randomness has a simple interpretation in terms of domain walls extending through the circuit. We analytically compute the second moment, showing that random circuits acting on n qudits form approximate 2-designs in O(n) depth, as is known. Furthermore, we argue that random circuits form approximate unitary k-designs in O(nk) depth and are thus essentially optimal in both n and k. We can show this in the limit of large local dimension, but more generally rely on a conjecture about the dominance of certain domain wall configurations.

The concept of quantum complexity has far-reaching implications spanning theoretical computer science, quantum many-body physics, and high energy physics. The quantum complexity of a unitary transformation or quantum state is defined as the size of the shortest quantum computation that executes the unitary or prepares the state. It is reasonable to expect that the complexity of a quantum state governed by a chaotic many-body Hamiltonian grows linearly with time for a time that is exponential in the system size; however, because it is hard to rule out a short-cut that improves the efficiency of a computation, it is notoriously difficult to derive lower bounds on quantum complexity for particular unitaries or states without making additional assumptions. To go further, one may study more generic models of complexity growth. We provide a rigorous connection between complexity growth and unitary k-designs, ensembles which capture the randomness of the unitary group. This connection allows us to leverage existing results about design growth to draw conclusions about the growth of complexity. We prove that local random quantum circuits generate unitary transformations whose complexity grows linearly for a long time, mirroring the behavior one expects in chaotic quantum systems and verifying conjectures by Brown and Susskind. Moreover, our results apply under a strong definition of quantum complexity based on optimal distinguishing measurements.