Pseudo-randomness and Learning in Quantum Computation

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