paper

Pseudo-randomness and Learning in Quantum Computation

arXiv:1006.5227

Abstract

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.

Contains results from 0802.1919 (with an alternative proof of the Markov chain mixing time bound), 0811.2597, 0903.5236 and 0907.2833. Also presents an introduction to k-designs, proving the relationships between different definitions. There is a review chapter on uses of k-designs

References in corpus (43)

Cited by in corpus (9)