| Type of Document |
Dissertation |
| Author |
Beckman, David Eugene
|
| URN |
etd-05272004-174253 |
| Persistent URL |
http://resolver.caltech.edu/CaltechETD:etd-05272004-174253 |
| Title |
Investigations in quantum computing: causality and graph isomorphism |
| Degree |
PhD |
| Option |
Physics |
| Advisory Committee |
| Advisor Name |
Title |
| John Preskill |
Committee Chair |
| David Politzer |
Committee Member |
| Hideo Mabuchi |
Committee Member |
| Steven Frautschi |
Committee Member |
|
| Keywords |
- quantum mechanics
- causality
- localizability
- superluminal signaling
- graph certificate
- graph isomorphism
|
| Date of Defense |
2004-05-14 |
| Availability |
unrestricted |
Abstract
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.
|
| Files |
| Filename |
Size |
Approximate Download Time
(Hours:Minutes:Seconds)
|
| 28.8 Modem |
56K Modem |
ISDN (64 Kb) |
ISDN (128 Kb) |
Higher-speed Access |
| |
thesis.pdf |
917.99 Kb |
00:04:14 |
00:02:11 |
00:01:54 |
00:00:57 |
00:00:04 |
|
