Southwest Quantum Information and Technology

Twelfth Annual Meeting, February 18-21, 2010
Santa Fe, New Mexico

Full Program | Thursday | Friday | Saturday | Sunday

SESSION 7: Quantum Algorithms
Session Chair:
1:15-2:00	John Watrous, University of Waterloo
	QIP = PSPACE
	Abstract. The interactive proof system model of computation is a cornerstone of complexity theory, and its quantum computational variant has been a topic of study in quantum complexity theory for the past decade. In this talk I will present an exact characterization of the expressive power of quantum interactive proof systems that I recently proved in collaboration with Rahul Jain, Zhengfeng Ji, and Sarvagya Upadhyay. The characterization states that QIP = PSPACE, or in other words that the collection of computational problems having quantum interactive proof systems consists precisely of those problems solvable in polynomial space with an ordinary classical Turing machine. This characterization implies the striking fact that quantum computing does not provide an increase in computational power over classical computing in the context of interactive proof systems.
2:00-2:30	David Meyer, University of California/San Diego
	Multi-query quantum algorithms for summation
	Abstract. PARITY is the problem of determining the parity of a string f of n bits given access to an oracle that responds to a query x ∈ {0, ..., n-1} with the x^th bit of the string, f(x). Classically n queries are required to succeed with probability greater than 1/2, but only the least integer greater than n/2 number of quantum queries suffice to determine the parity with probability 1. We consider a generalization to strings f of n elements of Z_k and the problem of determining ∑f(x). By constructing an explicit algorithm, we show that with n - r quantum queries the optimal success probability is at least the greatest integer less than n/r, divided by k. This quantum algorithm utilizes the n - r queries sequentially and adaptively, like Grover's algorithm, but in a different way that is not amplitude amplification.
2:30-3:00	Rolando Somma, Los Alamos National Laboratory
	Fast Quantum Algorithms for Traversing Paths of Eigenstates
	Abstract. We present optimal quantum algorithms to traverse the path of eigenstates of a discrete or continuous family of Hamiltonians. The implementation cost of the algorithms is the total evolution time with the Hamiltonians. Under some assumptions, the cost of the method is proportional to the ratio of the length of the eigenstate path to the minimum eigenvalue gap of the Hamiltonians. When no assumptions are made, the worst-case cost scales with the inverse of the gap squared. Our algorithms advance by preparing eigenstates from previous ones through a version of fixed point search that is approximated using the phase estimation algorithm. The cost of our methods is optimal and significantly improves upon the cost of known general methods for quantum adiabatic state preparation. In some cases, our methods yield a quantum speed-up over well-known classical annealing methods. (Unitary versions of the method can also be considered.)