Spherical t-designs as a general purpose tool for partial de-randomization (1st of 2 parts)
Spherical t-designs are ensembles of vectors which reproduce the first 2t moments of the uniform distribution on the complex unit sphere. As such they provide notions of "evenly distributed" sets of vectors that range from tight frames (t=1) to the full sphere (as t approaches infinity). Such configurations have been studied in algebraic combinatorics, coding theory, and quantum information. Similar to t-wise independent functions, they are a general purpose tool for (partial) derandomization. To emphasize this, we will consider two applications:
i.) Optimally distinguishing quantum states: The optimal probability of correctly distinguishing two (biased) coins with a single coin toss is proportional to the total variational distance. This classical result has a quantum mechanical analogue: the optimal probability of correctly distinguishing two quantum states is proportional to the trace distance. In contrast to the classical result, achieving this bound requires choosing a particular type of quantum measurement that depends on the states to be distinguished. It is therefore natural to ask which universal quantum measurements are optimal in the sense that they perform well at distinguishing arbitrary pairs of quantum states. We will review pioneering work by Ambainis and Emerson who showed that spherical 4-designs have this property.
ii.) Phase retrieval: The problem of retrieving phase information from amplitude measurements alone has appeared in many scientific disciplines over the last century. More recently, several new recovery algorithms have been proposed and rigorous performance guarantees have been established. The strongest results of this type are probabilistic in nature and require measurements that are chosen uniformly from the complex unit sphere. We will show that this result can be (partially) derandomized: choosing measurements independently from a spherical 4-design already allows for drawing similar conclusions.
From a practical point of view, the usefulness of these concepts hinges on the availability of constructions for spherical designs. Despite non-constructive existence proofs and approximate randomized constructions, exact families of spherical t-designs are notoriously difficult to find. We will present a family of structured vectors that form spherical 3-designs. These vectors, called stabilizer states, have a rich combinatorial structure and are ubiquitous in quantum information theory. What is more, they perform almost as well as spherical 4-designs in various applications.