Citation
Fefferman, William Jason (2014) The Power of Quantum Fourier Sampling. Dissertation (Ph.D.), California Institute of Technology. doi:10.7907/6HJBMC69. http://resolver.caltech.edu/CaltechTHESIS:05302014131308138
Abstract
How powerful are Quantum Computers? Despite the prevailing belief that Quantum Computers are more powerful than their classical counterparts, this remains a conjecture backed by little formal evidence. Shor's famous factoring algorithm [Shor97] gives an example of a problem that can be solved efficiently on a quantum computer with no known efficient classical algorithm. Factoring, however, is unlikely to be NPHard, meaning that few unexpected formal consequences would arise, should such a classical algorithm be discovered. Could it then be the case that any quantum algorithm can be simulated efficiently classically? Likewise, could it be the case that Quantum Computers can quickly solve problems much harder than factoring? If so, where does this power come from, and what classical computational resources do we need to solve the hardest problems for which there exist efficient quantum algorithms?
We make progress toward understanding these questions through studying the relationship between classical nondeterminism and quantum computing. In particular, is there a problem that can be solved efficiently on a Quantum Computer that cannot be efficiently solved using nondeterminism? In this thesis we address this problem from the perspective of sampling problems. Namely, we give evidence that approximately sampling the Quantum Fourier Transform of an efficiently computable function, while easy quantumly, is hard for any classical machine in the Polynomial Time Hierarchy. In particular, we prove the existence of a class of distributions that can be sampled efficiently by a Quantum Computer, that likely cannot be approximately sampled in randomized polynomial time with an oracle for the Polynomial Time Hierarchy.
Our work complements and generalizes the evidence given in Aaronson and Arkhipov's work [AA2013] where a different distribution with the same computational properties was given. Our result is more general than theirs, but requires a more powerful quantum sampler.
Item Type:  Thesis (Dissertation (Ph.D.)) 

Subject Keywords:  Quantum complexity theory 
Degree Grantor:  California Institute of Technology 
Division:  Engineering and Applied Science 
Major Option:  Computer Science 
Thesis Availability:  Public (worldwide access) 
Research Advisor(s): 

Group:  Institute for Quantum Information and Matter, IQIM 
Thesis Committee: 

Defense Date:  23 May 2014 
Record Number:  CaltechTHESIS:05302014131308138 
Persistent URL:  http://resolver.caltech.edu/CaltechTHESIS:05302014131308138 
DOI:  10.7907/6HJBMC69 
Default Usage Policy:  No commercial reproduction, distribution, display or performance rights in this work are provided. 
ID Code:  8443 
Collection:  CaltechTHESIS 
Deposited By:  William Fefferman 
Deposited On:  30 May 2014 23:54 
Last Modified:  11 Apr 2019 17:50 
Thesis Files

PDF
 Final Version
See Usage Policy. 422Kb 
Repository Staff Only: item control page