Record Details

Investigating quantum speedups through numerical simulations [electronic resource] / Shannon Wang ; Fernando Brandao, advisor.
Pasadena, California : California Institute of Technology, 2017.
1 online resource (xv, 81 leaves) : digital (1824 Kb), illustrations (some color).
CIT theses ; 2017
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.
Advisor and committee chair names found in the thesis' metadata record in the digital repository.
Dissertation note:
Thesis (Senior Major) -- California Institute of Technology, 2017.
Bibliography, etc. note:
Includes bibliographical references.
Linked resources:
Caltech Connect
Record appears in:


 Record created 2017-11-08, last modified 2018-09-17

Rate this document:

Rate this document:
(Not yet reviewed)