Makrand Sinha

Uniformly random unitaries, i.e. unitaries drawn from the Haar measure, have many useful properties but cannot be implemented efficiently. This has motivated a long line of research into random unitaries that ``look'' sufficiently Haar random while also being efficient to implement. Two different notions of derandomisation have emerged: t-designs are random unitaries that information-theoretically reproduce the first t moments of the Haar measure, and pseudorandom unitaries (PRUs) are random unitaries that are computationally indistinguishable from Haar random.In this work, we take a unified approach to constructing t-designs and PRUs. For this, we introduce and analyse the ``PFC ensemble'', the product of a computational basis permutation P, a random binary phase operator F, and a random Clifford unitary C. We show that this ensemble reproduces exponentially high moments of the Haar measure. We can then derandomise the PFC ensemble to show the following:-Linear-depth t-designs. We give the first construction of a (diamond-error) approximate t-design with circuit depth linear in t. This follows from the PFC ensemble by replacing the random phase and permutation operators with their 2t-wise independent counterparts. - Non-adaptive PRUs. We give the first construction of PRUs with non-adaptive security, i.e. we construct unitaries that are indistinguishable from Haar random to polynomial-time distinguishers that query the unitary in parallel on an arbitary state. This follows from the PFC ensemble by replacing the random phase and permutation operators with their pseudorandom counterparts. - Adaptive pseudorandom isometries. We show that if one considers isometries (rather than unitaries) from n to n + \omega(log n) qubits, a small modification of our PRU construction achieves adaptive security, i.e.~even a distinguisher that can query the isometry adaptively in sequence cannot distinguish it from Haar random isometries. This gives the first construction of adaptive pseudorandom isometries. Under an additional conjecture, this proof also extends to adaptive PRUs.

Abstract Aaronson and Ambainis (SICOMP `18) showed that any partial function on $N$ bits that can be computed with an advantage $\delta$ over a random guess by making $q$ quantum queries, can also be computed classically with an advantage $\delta/2$ by a randomized decision tree making ${O}_q(N^{1-\frac{1}{2q}}\delta^{-2})$ queries. Moreover, they conjectured the $k$-Forrelation problem --- a partial function that can be computed with $q = \lceil k/2 ceil$ quantum queries --- to be a suitable candidate for exhibiting such an extremal separation. We prove their conjecture by showing a tight lower bound of $\widetilde{\Omega}(N^{1-1/k})$ for the randomized query complexity of $k$-Forrelation, where the advantage $\delta = 2^{-O(k)}$. By standard amplification arguments, this gives an explicit partial function that exhibits an $O_\epsilon(1)$ vs $\Omega(N^{1-\epsilon})$ separation between bounded-error quantum and randomized query complexities, where $\epsilon>0$ can be made arbitrarily small. Our proof also gives the same bound for the closely related but non-explicit $k$-Rorrelation function introduced by Tal (FOCS `20). Our techniques rely on classical Gaussian tools, in particular, Gaussian interpolation and Gaussian integration by parts, and in fact, give a more general statement. We show that to prove lower bounds for $k$-Forrelation against a family of functions, it suffices to bound the $\ell_1$-weight of the Fourier coefficients between levels $k$ and $(k-1)k$. We also prove new interpolation and integration by parts identities that might be of independent interest in the context of rounding high-dimensional Gaussian vectors.