Improved algorithms for approximate quantum Fourier transforms and sparse Hamiltonian simulations.

摘要

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 2n. 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.