← Back to Event List

Doctoral Dissertation Defense: David J. Cornwell

Advisors: Dr. Samuel Lomonaco and Dr. Thomas Armstrong


Information Technology/Engineering : 346

Date & Time

March 26, 2014, 10:00 am12:00 pm


Title: Amplified Quantum Transforms

Abstract: In this work we investigate a new quantum algorithm called the Amplified Quantum Fourier Transform (Amplified-QFT) to solve the Local Period Problem where there is an Oracle with a periodic subset and we wish to recover its period. This algorithm uses parts of the famous Grover's quantum search algorithm to amplify the amplitudes on the subset, followed by the equally famous Shor's quantum algorithm for recovering the period.  We compare the Amplified-QFT algorithm against the Quantum Fourier Transform (QFT) and Quantum Hidden Subgroup (QHS) algorithms and calculate the probabilities of success for all three algorithms. We show that the Amplified-QFT algorithm is on average, quadratically faster than either the QFT or QHS algorithms. We also investigate two more general settings:
  1. where the QFT is replaced by a general unitary operator U in the Amplified-QFT algorithm; and
  2. where Grover's algorithm is replaced by a general amplification procedure in the Amplified-QFT algorithm.
We also investigate this algorithm when a random Error Stream affects the Oracle, which involves calculating expectations and variances over a random set. We calculate the probabilities of success in this case.  Further, we find an Uncertainty Principle for the Amplified-QFT algorithm.

We also identify a decision problem, the Constant or Balanced Signal Decision Problem, which can be solved by using the one dimensional Amplified Haar Wavelet Transform. This decision problem is a generalization of the Deutsch-Josza problem.