A Caltech Library Service

Investigating Quantum Speedups through Numerical Simulations


Wang, Shannon (2017) Investigating Quantum Speedups through Numerical Simulations. Senior thesis (Major), California Institute of Technology. doi:10.7907/Z9ZP4456.


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.

Item Type:Thesis (Senior thesis (Major))
Subject Keywords:physics, quantum computing, quantum speedups, quantum semidefinite programming
Degree Grantor:California Institute of Technology
Division:Physics, Mathematics and Astronomy
Major Option:Physics
Thesis Availability:Public (worldwide access)
Research Advisor(s):
  • Brandao, Fernando
Thesis Committee:
  • Stone, Edward C. (chair)
  • Libbrecht, Kenneth George
  • Frautschi, Steven C.
  • Politzer, Hugh David
  • Refael, Gil
  • Soifer, B. Thomas
  • Brandao, Fernando
Defense Date:23 May 2017
Non-Caltech Author Email:shannonawang (AT)
Record Number:CaltechTHESIS:06052017-122137777
Persistent URL:
Wang, Shannon0000-0003-0585-6556
Default Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:10282
Deposited By: Shannon Wang
Deposited On:05 Jun 2017 21:02
Last Modified:06 Oct 2017 22:38

Thesis Files

PDF - Final Version
See Usage Policy.


Repository Staff Only: item control page