A Caltech Library Service

Investigations in Quantum Computing: Causality and Graph Isomorphism


Beckman, David Eugene (2004) Investigations in Quantum Computing: Causality and Graph Isomorphism. Dissertation (Ph.D.), California Institute of Technology. doi:10.7907/S1R0-0V87.


In this thesis I explore two different types of limits on the time complexity of quantum computation---that is, limits on how much time is required to perform a given class of quantum operations on a quantum system. Upper limits can be found by explicit construction; I explore this approach for the problem of determining whether two graphs are isomorphic. Finding lower limits, on the other hand, usually requires appeal to some fundamental principle of the operation under consideration; I use this approach to derive lower limits placed by the requirements of relativistic causality on the time required for implementation of some nonlocal quantum operations. In some situations these limits are attainable, but for other physical spacetime geometries we exhibit classes of operations which do not violate relativistic causality but which are nevertheless not implementable.

Item Type:Thesis (Dissertation (Ph.D.))
Subject Keywords:causality; graph certificate; graph isomorphism; localizability; quantum mechanics; superluminal signaling
Degree Grantor:California Institute of Technology
Division:Physics, Mathematics and Astronomy
Major Option:Physics
Thesis Availability:Public (worldwide access)
Research Advisor(s):
  • Preskill, John P.
Thesis Committee:
  • Preskill, John P. (chair)
  • Politzer, Hugh David
  • Mabuchi, Hideo
  • Frautschi, Steven C.
Defense Date:14 May 2004
Record Number:CaltechETD:etd-05272004-174253
Persistent URL:
Default Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:2139
Deposited By: Imported from ETD-db
Deposited On:28 May 2004
Last Modified:05 Jan 2021 23:48

Thesis Files

PDF - Final Version
See Usage Policy.


Repository Staff Only: item control page