Abstract: Randomness is a vital tool and resource in both classical and quantum information processing. However, constructing random bits is expensive, and hence minimising their use is desirable. Several tools have been developed in classical computing for this purpose. Two such tools are expanders and k-wise independent random variables, and they have found already found many applications in classical computing. In this thesis we investigate the quantum analogues of these two tools for quantum information processing tasks.
In quantum information processing, algorithms are often modeled by unitary operators and randomness enters the picture from the choice of random unitary operators, much like randomness in classical information processing. Existential proofs in information processing applications are almost always based on unitary matrices drawn from the Haar probability measure on the unitary group (formalisation of the the uniform measure on the unitary group). However, an n-qubit unitary is described by 4^n real parameters, and thus cannot be efficiently approximated using a sub-exponential amount of time or randomness. This has led to the construction of efficient pseudo-random ensembles
of unitaries which emulate the Haar measure, up to the first t-moments, for certain applications [Harrow, Low 2009]. Such constructions are referred to as unitary t-designs. It is known that there are exact unitary 't'-designs for any t [Kuperberg, 2006]. The advantage of using these designs is that approximate unitary t-designs can be efficiently constructed for t = poly(log dimension) [Brandao et al. 2012, Sen 2018].
In this thesis we apply these designs for the following tasks:
1. Showing that the minimum output Renyi p-entropy, for all p >= 1, of quantum channels is subadditive. Renyi 1-entropy is the well known von Neumann entropy and its subadditivity leads to quantum channels with super additive classical Holevo capacity [Shor 2004]. We prove for the first time that approximate unitary n^{2/3}-designs lead to a quantum channel with superadditive classical Holevo capacity;
2. Efficient estimation of average gate fidelity of a quantum logic gate using few random bits, better than the state of the art;
3. Concentration of measure for Fully Quantum Slepian Wolf theorem, an instance of a decoupling theorem in quantum information theory, using an approximate t-design for a suitable value of t, beating the state of the art.
Although the unitary t-designs used in the above works have t larger than what is known to be efficiently implementable, yet in all cases they lead to significant savings in the number of random bits required vis-a-vis Haar random unitaries. Thus, all the three works can be thought of as steps towards their respective derandomisations.
