Pseudo-randomness and Learning in Quantum Computation

Details Pseudo-randomness and Learning in Quantum Computation Pseudo-randomness and Learning in Quantum Computation

2010-06-27

arxiv.org/abs/1006.5227v1

PhD Thesis, University of Bristol, UK, 2010

Physics

Quantum Physics

Contains results from 0802.1919 (with an alternative proof of the Markov chain mixing time bound), 0811.2597, 0903.5236 and 09

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

Pseudo-randomness and Learning in Quantum Computation does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Pseudo-randomness and Learning in Quantum Computation, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Pseudo-randomness and Learning in Quantum Computation will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-630897