Fefferman, William Jason (2010) On quantum computing and pseudorandomness. Master's thesis, California Institute of Technology. http://resolver.caltech.edu/CaltechTHESIS:01312011-155543067
The relationship between efficient verification and quantum computing is one of the most important and least well-understood questions in the theory of computation. In particular, is there a problem that can be solved efficiently on a quantum computer that cannot be verified? In this thesis we give evidence that \BQP \not\subset \PH, relating the classes of languages decidable with a quantum computer to a generalization of \NP. In so doing we connect a question in pseudorandomness, first studied [BSW'03] to the problem of finding an oracle relative to which \BQP \not\subset \PH. The primary technical challenge is to construct a unitary matrix, realized by an efficient quantum circuit and whose rows are supported on nearly disjoint subsets. Using this matrix and assuming the validity of the aforementioned question in pseudorandomness, we show an instantiation of the Nisan-Wigderson pseudorandom generator that can be broken with quantum computers, but not with the relevant mode of classical computation.
|Item Type:||Thesis (Master's thesis)|
|Subject Keywords:||Quantum Computing, Pseudorandomness|
|Degree Grantor:||California Institute of Technology|
|Division:||Engineering and Applied Science|
|Major Option:||Computer Science|
|Thesis Availability:||Public (worldwide access)|
|Defense Date:||June 2010|
|Default Usage Policy:||No commercial reproduction, distribution, display or performance rights in this work are provided.|
|Deposited By:||William Fefferman|
|Deposited On:||02 Feb 2011 17:08|
|Last Modified:||26 Dec 2012 04:33|
- Final Version
See Usage Policy.
Repository Staff Only: item control page