  This thesis discusses the young fields of quantum pseudo-randomness and
quantum learning algorithms. We present techniques for derandomising algorithms
to decrease randomness resource requirements and improve efficiency. One key
object in doing this is a k-design, which is a distribution on the unitary
group whose kth moments match those of the unitarily invariant Haar measure. We
show that for a natural model of a random quantum circuit, the distribution of
random circuits quickly converges to a 2-design. We then present an efficient
unitary k-design construction for any k, provided the number of qubits n
satisfies k = O(n/log n). In doing this, we provide an efficient construction
of a quantum tensor product expander, which is a generalisation of a quantum
expander which in turn generalises classical expanders. We then discuss
applications of k-designs. We show that they can be used to improve the
efficiency of many existing algorithms and protocols and also find new
applications to derandomising large deviation bounds. In particular, we show
that many large deviation bound results for Haar random unitaries carry over to
k-designs for k = poly(n). In the second part of the thesis, we present some
learning and testing algorithms for the Clifford group. We find an optimal
algorithm for identifying an unknown Clifford operation. We also give an
algorithm to test if an unknown operation is close to a Clifford or far from
every Clifford.
