A Caltech Library Service

The Power of Quantum Fourier Sampling


Fefferman, William Jason (2014) The Power of Quantum Fourier Sampling. Dissertation (Ph.D.), California Institute of Technology. doi:10.7907/6HJB-MC69.


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 NP-Hard, 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):
  • Umans, Christopher M. (co-advisor)
  • Kitaev, Alexei (co-advisor)
Group:Institute for Quantum Information and Matter
Thesis Committee:
  • Umans, Christopher M. (chair)
  • Chandrasekaran, Venkat
  • Preskill, John P.
  • Kitaev, Alexei
Defense Date:23 May 2014
Record Number:CaltechTHESIS:05302014-131308138
Persistent URL:
Default Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:8443
Deposited By: William Fefferman
Deposited On:30 May 2014 23:54
Last Modified:02 Jun 2020 21:53

Thesis Files

PDF - Final Version
See Usage Policy.


Repository Staff Only: item control page