Cumulative effects in quantum algorithms and quantum process tomography

This thesis comprises three results on quantum algorithms and quantum process tomography. In the first section, I create a tool that uses properties of the quantum general adversary bound to upper bound the query complexity of Boolean functions. Using this tool I prove the existence of O(1)-query quantum algorithms for a set of functions called FAULT TREES. To obtain these results, I combine previously known properties of the adversary bound in a new way, as well as extend an existing proof of a composition property of the adversary bound. The second result is a method for characterizing errors in a quantum computer. Many current tomography procedures give inaccurate estimates because they do not have adequate methods for handling noise associated with auxiliary operations. The procedure described here provides two ways of dealing with this noise: estimating the noise independently so its effect can be completely understood, and analyzing the worst case effect of this noise, which gives better bounds on standard estimates. The final section describes a quantum analogue of a classical local search algorithm for Classical k-SAT. I show that for a restricted version of Quantum 2-SAT, this quantum algorithm succeeds in polynomial time. While the quantum algorithm ultimately performs similarly to the classical algorithm, quantum effects, like the observer effect, make the analysis more challenging.

Department dc:contributor.department

Massachusetts Institute of Technology. Department of Physics.

Grantor dc:publisher

Massachusetts Institute of Technology

Year dc:date.issued

2014

Author dc:creator

• Hess, Shelby Kimmel

Advisor dc:contributor.advisor

• Edward Farhi.

• Physics.

Statement dc:rights

• M.I.T. theses are protected by copyright. They may be viewed from this source for any purpose, but reproduction or distribution in any format is prohibited without written permission. See provided URL for inquiries about permission.

Licence dc:rights.uri

• http://dspace.mit.edu/handle/1721.1/7582

Language dc:language.iso

eng

Handle dc:identifier.uri

http://hdl.handle.net/1721.1/100678

OAI identifier oai:identifier

oai:dspace.mit.edu:1721.1/100678