Entangled multipartite states are resources for universal quantum computation, but they can also give rise to ensembles of unitary transformations, a topic usually studied in the context of random quantum circuits. Using several graph state techniques, we show that these resources can "derandomize" circuit results by sampling the same kinds of ensembles quantum mechanically, analogously to a quantum random number generator. Furthermore, we find simple examples that give rise to new ensembles whose statistical moments exactly match those of the uniformly random distribution over all unitaries up to order t, while foregoing adaptive feedforward entirely. Such ensembles-known as t designs-often cannot be distinguished from the "truly" random ensemble, and so they find use in many applications that require this implied notion of pseudorandomness.
Entangled multipartite states are resources for universal quantum computation, but they can also give rise to ensembles of unitary transformations, a topic usually studied in the context of random quantum circuits. Using several graph state techniques, we show that these resources can "derandomize" circuit results by sampling the same kinds of ensembles quantum mechanically, analogously to a quantum random number generator. Furthermore, we find simple examples that give rise to new ensembles whose statistical moments exactly match those of the uniformly random distribution over all unitaries up to order t, while foregoing adaptive feedforward entirely. Such ensembles-known as t designs-often cannot be distinguished from the "truly" random ensemble, and so they find use in many applications that require this implied notion of pseudorandomness.
This thesis is focused on the generation and understanding of particular kinds of quantum randomness. Randomness is useful for many tasks in physics and information processing, from randomized benchmarking , to black hole physics , as well demonstrating a so-called quantum speedup , and many other applications. On the one hand we explore how to generate a particular form of random evolution known as a t-design. On the other we show how this can also give instances for quantum speedup - where classical computers cannot simulate the randomness efficiently. We also show that this is still possible in noisy realistic settings. More specifically, this thesis is centered around three main topics. The first of these being the generation of epsilon-approximate unitary t-designs. In this direction, we first show that non-adaptive, fixed measurements on a graph state composed of poly(n,t,log(1/epsilon)) qubits, and with a regular structure (that of a brickwork state) effectively give rise to a random unitary ensemble which is a epsilon-approximate t-design. This work is presented in Chapter 3. Before this work, it was known that non-adaptive fixed XY measurements on a graph state give rise to unitary t-designs , however the graph states used there were of complicated structure and were therefore not natural candidates for measurement based quantum computing (MBQC), and the circuits to make them were complicated. The novelty in our work is showing that t-designs can be generated by fixed, non-adaptive measurements on graph states whose underlying graphs are regular 2D lattices. These graph states are universal resources for MBQC. Therefore, our result allows the natural integration of unitary t-designs, which provide a notion of quantum pseudorandomness which is very useful in quantum algorithms, into quantum algorithms running in MBQC. Moreover, in the circuit picture this construction for t-designs may be viewed as a constant depth quantum circuit, albeit with a polynomial number of ancillas. We then provide new constructions of epsilon-approximate unitary t-designs both in the circuit model and in MBQC which are based on a relaxation of technical requirements in previous constructions. These constructions are found in Chapters 4 and 5.
Measurement based (MB) quantum computation allows for universal quantum computing by measuring individual qubits prepared in entangled multipartite states, known as graph states. Unless corrected for, the randomness of the measurements leads to the generation of ensembles of random unitaries, where each random unitary is identified with a string of possible measurement results. We show that repeating an MB scheme an efficient number of times, on a simple graph state, with measurements at fixed angles and no feedforward corrections, produces a random unitary ensemble that is an $\ensuremath{\varepsilon}$-approximate t design on n qubits. Unlike previous constructions, the graph is regular and is also a universal resource for measurement based quantum computing, closely related to the brickwork state.
At its core a t-design is a method for sampling from a set of unitaries in a way which mimics sampling randomly from the Haar measure on the unitary group, with applications across quantum information processing and physics. We construct new families of quantum circuits on n-qubits giving rise to ε-approximate unitary t-designs efficiently in O(n3t12) depth. These quantum circuits are based on a relaxation of technical requirements in previous constructions. In particular, the construction of circuits which give efficient approximate t-designs by Brandao, Harrow, and Horodecki (F.G.S.L Brandao, A.W Harrow, and M. Horodecki, Commun. Math. Phys. (2016).) required choosing gates from ensembles which contained inverses for all elements, and that the entries of the unitaries are algebraic. We reduce these requirements, to sets that contain elements without inverses in the set, and non-algebraic entries, which we dub partially invertible universal sets. We then adapt this circuit construction to the framework of measurement based quantum computation(MBQC) and give new explicit examples of n-qubit graph states with fixed assignments of measurements (graph gadgets) giving rise to unitary t-designs based on partially invertible universal sets, in a natural way. We further show that these graph gadgets demonstrate a quantum speedup, up to standard complexity theoretic conjectures. We provide numerical and analytical evidence that almost any assignment of fixed measurement angles on an n-qubit cluster state give efficient t-designs and demonstrate a quantum speedup.
Random quantum circuits aim to efficiently reproduce the statistical properties of ideal random quantum evolution. One approach is to construct approximate unitary designs, which match the moments of Haar-random unitaries up to a prescribed order with controlled error. In this work, we establish quantitative guarantees for how accurately these designs reproduce the full distributions of individual output probabilities. We show that, for every strong ε-approximate unitary k-design on n qubits, the distribution of each individual output probability is within O(k(k+2n)2n+ε) in Kolmogorov distance of the finite-dimensional Porter-Thomas distribution, a beta distribution with parameters 1 and 2n−1. This bound is optimal up to constant factors, implying that a substantially better uniform bound requires additional structure. We further show that local invariance yields an exponential improvement in the dependence on k, with guarantees also in the stronger metric of total variation: every strong ε-approximate unitary k-design invariant under unitary translations acting on logk+O(1) qubits achieves error 2−Ω(k)+O(ε) in Kolmogorov distance and 2−Ω(k)+O(εlog(2/ε)) in total variation distance. These results identify both the distributional accuracy guaranteed by moment matching and the additional structure that substantially improves it. As an application, we show that if the marginal distribution of each output probability of a strong approximate design is within Kolmogorov distance η of its Haar counterpart, then the expected Shannon entropy of the output distribution differs from its Haar value by O(η).
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 firsttmoments 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 constructingt-designs and PRUs. For this, we introduce and analyse the “PFCensemble”, the product of a random computational basis permutationP, a random binary phase operatorF, and a random Clifford unitaryC. We show that this ensemble reproduces exponentially high moments of the Haar measure. We can then derandomise thePFCensemble to show the following: •Linear-deptht-designs. We give the first construction of a (diamond-error) approximatet-design with circuit depth linear int. This follows from thePFCensemble by replacing the random phase and permutation operators with their2t-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 thePFCensemble 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) fromnton+ω(logn)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.
Can simple processes appear highly complex? Gowers (Comb. Prob. Comp. '96) conjectured that repeatedly composing local random reversible operations can yield global permutations that are indistinguishable from random. In this work, we study the unitary quantum analog of this question, in an attempt to make new progress on this longstanding conjecture.
Our first result shows that statistical moment matching in the form of unitary designs does not generically lead to pseudorandomness---even for the simplest quantum processes: for every fixed t, we give an efficiently samplable family {νn}n of distributions on one- and two-qubit gates such that, after T=Ot(n2log2n) independent steps, the resulting n-qubit ensemble is an approximate unitary t-design with negligible error exp(−Ω(log2n)), yet an efficient quantum algorithm distinguishes it from random using only Ot(log2n) queries. This refutes the unitary analog of the Hoory--Magen--Myers--Rackoff conjecture (ICALP '04) for permutations.
Our second result is a stronger separation between unitary designs and pseudorandom unitaries at polynomially bounded moments; our counterexample, however, requires highly structured ensembles, in contrast with the simple local walks from before. This suggests caution when using unitary designs to model information scrambling in black-hole physics, as even maximally scrambled systems can exhibit structure which is accessible to efficient experiments. Motivated by these findings, we then propose new conjectures for how pseudorandomness can plausibly emerge within simple quantum processes, such as random quantum circuits.