A Caltech Library Service

On Quantum Computing and Pseudorandomness


Fefferman, William Jason (2011) On Quantum Computing and Pseudorandomness. Master's thesis, California Institute of Technology. doi:10.7907/3Q00-DD64.


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 ⊄ 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 [BSW03] to the problem of finding an oracle relative to which BQP ⊄ 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:
  • None, None
Defense Date:June 2010
Record Number:CaltechTHESIS:01312011-155543067
Persistent URL:
Default Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:6237
Deposited By: William Fefferman
Deposited On:02 Feb 2011 17:08
Last Modified:14 Oct 2019 20:58

Thesis Files

PDF - Final Version
See Usage Policy.


Repository Staff Only: item control page