Improved algorithms for approximate quantum fourier transforms and sparse hamiltonian simulations

Abstract

We investigate and improve algorithms for computing the approximate quantum Fourier transform (QFT ) and simulating a sparse Hamiltonian. We present an improved near-linear time algorithm for the approximate QFT modulo 2™. We give a circuit for the arbitrary modulus version that matches the best currently-known bound. We then relate the difficulty of the arbitrary modulus QFT to classical integer multiplication and division. We also investigate the problem of simulating an n-qubit sparse Hamiltonian. As input we receive the system's start state, a black box which, via queries, provides the non-zero entries of each row of the Hamiltonian, and a time t. We present an improved polynomial-time quantum algorithm for computing an approximation of the state of the system at time t. Prior to this, we provide an introduction to quantum computing, and survey some quantum algorithms that are used in our improved algorithms.