Investigating Quantum Speedups through Numerical Simulations

Citation

Wang, Shannon (2017) Investigating Quantum Speedups through Numerical Simulations. Senior thesis (Major), California Institute of Technology. doi:10.7907/Z9ZP4456. https://resolver.caltech.edu/CaltechTHESIS:06052017-122137777

Abstract

It has been recently noted in a paper by Brandao et al. that the structure of a linear program in a classical semidefinite programming algorithm lends itself to quantization, such that the classical algorithm may experience a quantum speedup if the step of solving a linear program is replaced with the preparation of a Gibbs state of classical Hamiltonian on a quantum computer, where the Hamiltonian is given by a linear combination of the semidefinite program's constraint matrices. The quantum speedup would be exponential if the complexity of the Gibbs sampler used to execute the update step is polynomial in system size. The Gibbs samplers with explicitly defined runtimes are exponential in system size; however, while the quantum Metropolis sampling algorithm by Temme et al. does not have a runtime bounded explicitly in system size, the algorithm heuristically runs in polylogarithmic time. Since the inverse spectral gap of the quantum Metropolis map varies inversely with the running time of the algorithm, we simulate the behavior of the quantum Metropolis map's spectral gap as a function of system size and row sparsity. We also examine how different definitions of fixed row sparsity affect the spectral gap's behavior when the system size is increased linearly. While more numerical evidence is needed to draw a definitive conclusion, the current results appear to indicate that for system sizes ranging from three to ten qubits, if fixed row sparsity is defined as a fixed polynomial function of the system size, then the quantum Metropolis spectral gap behaves as a polynomial function of system size.

Thesis Files