Southwest Quantum Information and Technology

Tenth Annual Meeting, February 14-17, 2008
University of New Mexico, Santa Fe, New Mexico

Full Program | Thursday Tutorials | Friday | Saturday | Sunday

SESSION 6: Algorithms
Session Chair: Wim van Dam
08:30-09:15	Edward Farhi, Massachusetts Institute of Technology (invited)
	A quantum computer can determine who wins a game faster than a classical computer
	Abstract. Imagine a game where two players go back and forth making moves and at the end of a fixed number of moves the position is either a win or a loss for the first player. In this case, if both players play best possible, it is determined at the first move who wins or loses. To figure out who will be the winner you need not look at all of the final positions but only at N^.753 where N is the number of final positions. I will show that with a quantum computer the exponent can be reduced to 1/2. The technique involves quantum scattering theory.
09:15-9:45	Jon Yard, Los Alamos National Laboratory
	A general quantum algorithm for knot and link polynomials
	Abstract. In this talk, I will present a quantum algorithm for approximating topological invariants of knots and links coming from Markov traces on centralizer algebras of quantum groups. The method is based on a general formalism for efficiently implementing, on a quantum computer, representations of braid groups associated with path algebras. The general framework presented accommodates known quantum algorithms for approximately evaluating the Jones and HOMFLYPT polynomials - which arise from Markov traces on Temperley-Lieb and Hecke algebras associated to deformations of unitary groups. The framework also allows one to approximately evaluate the Kauffman polynomial invariants which arise from Markov traces on Birman-Wenzl-Murakami algebras associated to deformations of the orthogonal and symplectic groups. Time permitting, I will also comment on the cases in which approximating the Kauffman polynomial is a universal quantum algorithm which solves a Promise-BQP-complete problem.
10:15-10:45	David Meyer, University of California at San Diego
	When a quantum query is no better than a classical one
	Abstract. We consider a simple generalization of Deutsch's problem in which a single quantum query, rather than solving the problem, provides no more information than a single classical query. This result can be explained by properties of quantum interference, and also follows from results in the early quantum hypothesis testing literature.