Unitary t -designs are the bread and butter of quantum information theory and beyond. An important issue in practice is that of efficiently constructing good approximations of such unitary t -designs. Building on results by Aubrun (Comm. Math. Phys. 2009), we prove that sampling dtpoly(t,logd,1/ϵ) unitaries from an exact t -design provides with positive probability an ϵ -approximate t -design, if the error is measured in one-to-one norm. As an application, we give a randomized construction of a quantum encryption scheme that has roughly the same key size and security as the quantum one-time pad, but possesses the additional property of being non-malleable against adversaries without quantum side information.
Unitary t -designs are the bread and butter of quantum information theory and beyond. An important issue in practice is that of efficiently constructing good approximations of such unitary t -designs. Building on results by Aubrun (Comm. Math. Phys. 2009), we prove that sampling dtpoly(t,logd,1/ϵ) unitaries from an exact t -design provides with positive probability an ϵ -approximate t -design, if the error is measured in one-to-one norm. As an application, we give a randomized construction of a quantum encryption scheme that has roughly the same key size and security as the quantum one-time pad, but possesses the additional property of being non-malleable against adversaries without quantum side information.
Random unitaries are useful in quantum information and related fields but hard to generate with limited resources. An approximate unitary k-design is a measure over an ensemble of unitaries such that the average is close to a Haar (uniformly) random ensemble up to the first k moments. A strong notion of approximation bounds the distance from Haar randomness in relative error: the weighted twirl induced by an approximate design can be written as a convex combination involving that of an exact design and vice versa. The main focus of our work is on efficient constructions of approximate designs, in particular whether relative-error designs in sublinear depth are possible. We give a positive answer to this question as part of our main results: 1. Twirl-Swap-Twirl: Let A and B be systems of the same size. Consider a protocol that locally applies k-design unitaries to A^k and B^k respectively, then exchanges l qudits between each copy of A and B respectively, then again applies local k-design unitaries. This protocol yields an ε-approximate relative k-design when l = O(k log k + log(1/ε)). In particular, this bound is independent of the size of A and B as long as it is sufficiently large compared to k and 1/ε. 2. Twirl-Crosstwirl: Let A_1, … , A_P be subsystems of a multipartite system A. Consider the following protocol for k copies of A: (1) locally apply a k-design unitary to each A_p for p = 1, … , P; (2) apply a "crosstwirl" k-design unitary across a joint system combining l qudits from each A_p. Assuming each A_p’s dimension is sufficiently large compared to other parameters, one can choose l to be of the form 2 (Pk + 1) log_q k + log_q P + log_q(1/ε) + O(1) to achieve an ε-approximate relative k-design. As an intermediate step, we show that this protocol achieves a k-tensor-product-expander, in which the approximation error is in 2 → 2 norm, using communication logarithmic in k. 3. Recursive Crosstwirl: Consider an m-qudit system with connectivity given by a lattice in spatial dimension D. For every D = 1, 2, …, we give a construction of an ε-approximate relative k-design using unitaries of spatially local circuit depth O ((log m + log(1/ε) + k log k ) k polylog(k)). Moreover, across the boundaries of spatially contiguous sub-regions, unitaries used in the design ensemble require only area law communication up to corrections logarithmic in m. Hence they generate only that much entanglement on any product state input. These constructions use the alternating projection method to analyze overlapping Haar twirls, giving a bound on the convergence speed to the full twirl with respect to the 2-norm. Using von Neumann subalgebra indices to replace system dimension, the 2-norm distance converts to relative error without introducing system size. The Recursive Crosstwirl construction answers one variant of [Harrow and Mehraban, 2023, Open Problem 1], showing that with a specific, layered architecture, random circuits produce relative error k-designs in sublinear depth. Moreover, it addresses [Harrow and Mehraban, 2023, Open Problem 7], showing that structured circuits in spatial dimension D of depth << m^{1/D} may achieve approximate k-designs.
Abstract Unitary t -designs are ‘good’ finite subsets of the unitary group that approximate the whole unitary group well. Unitary t -designs have been applied in randomized benchmarking, tomography, quantum cryptography and many other areas of quantum information science. If a unitary t -design itself is a group then it is called a unitary t -group. Although it is known that unitary t -designs in exist for any t and d , the unitary t -groups do not exist for if , as it is shown by Guralnick–Tiep (Guralnick and Tiep 2005 Represent. Theory 9 138–208) and Bannai–Navarro–Rizo–Tiep (Bannai et al 2018 J. Math. Soc. Japan (accepted) ). Explicit constructions of exact unitary t -designs in are not easy in general. In particular, explicit constructions of unitary 4-designs in have been an open problem in quantum information theory. We prove that some exact unitary -designs in the unitary group are constructed from unitary t -groups in that satisfy certain specific conditions. Based on this result, we specifically construct exact unitary 3-designs in from the unitary 2-group in and also unitary 4-designs in from the unitary 3-group in numerically. We also discuss some related problems and a few applications to physics problems.
Epsilon-nets and approximate unitaryt-designs are natural notions that capture properties of unitary operations relevant for numerous applications in quantum information and quantum computing. In this work we study quantitative connections between these two notions. Specifically, we prove that, forddimensional Hilbert space, unitaries constituting$\delta −approximatet−expandersform\epsilon −netsfort\simeq \frac {d^{5/2}}{ \epsilon }and\delta \simeq \left ({\frac { \epsilon ^{3/2}}{d}}\right)^{d^{2}}.Wealsoshowthatforarbitraryt,\epsilon −netscanbeusedtoconstruct\delta −approximateunitaryt−designsfor\delta \simeq \epsilon t,wherethenotionofapproximationisbasedonthediamondnorm.Finally,weprovethatthedegreeofanexactunitarytdesignnecessarytoobtainan\epsilon −netmustgrowatleastasfastas\frac {1}{ \epsilon }(forfixeddimension)andnotslowerthand^{2}(forfixed\epsilon ).Thisshowsnearoptimalityofourresultconnectingt−designsand\epsilon $-nets. We apply our findings in the context of quantum computing. First, we show that that approximate t-designs can be generated by shallow random circuits formed from a set of universal two-qudit gates in the parallel and sequential local architectures considered in (Brandão et al., 2016). Importantly, our gate sets need not to be symmetric (i.e., contains gates together with their inverses) or consist of gates with algebraic entries. Second, we consider compilation of quantum gates and prove a non-constructive Solovay-Kitaev theorem for general universal gate sets. Our main technical contribution is a new construction of efficient polynomial approximations to the Dirac delta in the space of quantum channels, which can be of independent interest.
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.
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.
We introduce an ε-approximate unitary 2-design that is compatible with the structure of p- and q-quadratures in continuous-variable (CV) quantum systems. The design unitaries are defined on a finite-dimensional discretisation of the CV space and can be physically implemented as operations on the full CV space. This establishes the first approximate unitary design for CV systems. The design alternatingly acts with unitaries based on the quadrature operators q^ and p^. We prove that the parameter ε is given by 1/dℓ, where d is the dimension of the truncated Hilbert space and ℓ is the number of iterations.
We propose an Unclonable Encryption scheme in which the encryption operators are given by the unitaries which constitute the approximate unitary design. We prove its security using recent results on decoupling. This establishes unclonable-indistinguishable security for a CV encryption for the first time.