Return to search
## On Algorithms, Separability and Cellular Automata in Quantum Computing

In Part I of this thesis, we present a new model of quantum cellular automata

(QCA) based on local unitary operations. We will describe a set of desirable

properties for any QCA model, and show that all of these properties are

satisfied by the new model, while previous models of QCA do not. We will also

show that the computation model based on Local Unitary QCA is equivalent to

the Quantum Circuit model of computation, and give a number of applications of

this new model of QCA. We also present a physical model of classical CA, on

which the Local Unitary QCA model is based, and Coloured QCA, which is an

alternative to the Local Unitary QCA model that can be used as the basis for

implementing QCA in actual physical systems.

In Part II, we explore the quantum separability problem, where we are given a

density matrix for a state over two quantum systems, and we are to determine

whether the state is separable with respect to these systems. We also look at

the converse problem of finding an entanglement witness, which is an

observable operator which can give a verification that a particular quantum

state is indeed entangled. Although the combined problem is known to be

NP-hard in general, it reduces to a convex optimization problem, and by

exploiting specific properties of the set of separable states, we introduce a

classical algorithm for solving this problem based on an Interior Point

Algorithm introduced by Atkinson and Vaidya in 1995.

In Part III, we explore the use of a low-depth AQFT (approximate quantum

Fourier transform) in quantum phase estimation. It has been shown previously

that the logarithmic-depth AQFT is as effective as the full QFT for the

purposes of phase estimation. However, with sub-logarithmic depth, the phase

estimation algorithm no longer works directly. In this case, results of the

phase estimation algorithm need classical post-processing in order to retrieve

the desired phase information. A generic technique such as the method of

maximum likelihood can be used in order to recover the original phase.

Unfortunately, working with the likelihood function analytically is

intractable for the phase estimation algorithm. We develop some computational

techniques to handle likelihood functions that occur in phase estimation

algorithms. These computational techniques may potentially aid in the analysis

of certain likelihood functions.

Identifer | oai:union.ndltd.org:WATERLOO/oai:uwspace.uwaterloo.ca:10012/3322 |

Date | January 2007 |

Creators | Cheung, Donny |

Source Sets | University of Waterloo Electronic Theses Repository |

Language | English |

Detected Language | English |

Type | Thesis or Dissertation |

Page generated in 0.0012 seconds