CaltechTHESIS
  A Caltech Library Service

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. http://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.

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) yahoo.com
Record Number:CaltechTHESIS:06052017-122137777
Persistent URL:http://resolver.caltech.edu/CaltechTHESIS:06052017-122137777
DOI:10.7907/Z9ZP4456
ORCID:
AuthorORCID
Wang, Shannon0000-0003-0585-6556
Default Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:10282
Collection:CaltechTHESIS
Deposited By: Shannon Wang
Deposited On:05 Jun 2017 21:02
Last Modified:06 Oct 2017 22:38

Thesis Files

[img]
Preview
PDF - Final Version
See Usage Policy.

1824Kb

Repository Staff Only: item control page