CaltechTHESIS
  A Caltech Library Service

On quantum computing and pseudorandomness

Citation

Fefferman, William Jason (2010) On quantum computing and pseudorandomness. Master's thesis, California Institute of Technology. http://resolver.caltech.edu/CaltechTHESIS:01312011-155543067

Abstract

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)
Research Advisor(s):
  • Kitaev, Alexei (advisor)
  • Umans, Christopher M. (advisor)
Thesis Committee:
  • Unknown, Unknown
Defense Date:June 2010
Record Number:CaltechTHESIS:01312011-155543067
Persistent URL:http://resolver.caltech.edu/CaltechTHESIS:01312011-155543067
Default Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:6237
Collection:CaltechTHESIS
Deposited By: William Fefferman
Deposited On:02 Feb 2011 17:08
Last Modified:26 Dec 2012 04:33

Thesis Files

[img]
Preview
PDF - Final Version
See Usage Policy.

350Kb

Repository Staff Only: item control page