In previous papers about searches on star graphs several patterns have been made apparent; the speed up only occurs when graphs are ''tuned'' so that their time step operators have degenerate eigenvalues, and only certain initial states are effective. More than that, the searches are never faster than order square root of N time. In this thesis the problem is defined rigorously, the causes for all of these patterns are identified, sufficient and necessary conditions for quadratic-speed searches for any connected subgraph are demonstrated, the tolerance of these conditions is investigated, and it is shown that (unfortunately) we can do no better than order square root of N time. Along the way, a useful formalism is established that may be useful in future work involving highly symmetric graphs.
The tools and techniques so derived are then used to demonstrate that tree graphs can be used for the computation of Boolean functions. The philosophy of Farhi's work on the continuous-time NAND tree is applied to a discrete-time walk with any (AND, OR, NAND, or NOR) gate at each vertex. Tentative results show that the vast majority of possible Boolean functions on N bits can be calculated in order square root of N time.
|Advisor:||Hillery, Mark, Cappell, Sylvain|
|School:||New York University|
|School Location:||United States -- New York|
|Source:||DAI-B 76/04(E), Dissertation Abstracts International|
|Subjects:||Applied Mathematics, Mathematics, Quantum physics|
|Keywords:||Quantum algorithm, Quantum computation, Quantum search, Quantum walk|
Copyright in each Dissertation and Thesis is retained by the author. All Rights Reserved
The supplemental file or files you are about to download were provided to ProQuest by the author as part of a
dissertation or thesis. The supplemental files are provided "AS IS" without warranty. ProQuest is not responsible for the
content, format or impact on the supplemental file(s) on our system. in some cases, the file type may be unknown or
may be a .exe file. We recommend caution as you open such files.
Copyright of the original materials contained in the supplemental file is retained by the author and your access to the
supplemental files is subject to the ProQuest Terms and Conditions of use.
Depending on the size of the file(s) you are downloading, the system may take some time to download them. Please be