Southwest Quantum Information and Technology

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

Full Program | Thursday | Friday | Saturday | Sunday

SESSION 8: Breakout I - Quantum Computing
Session Chair:
3:30-4:00	Stephen Jordan, California Institute of Technology
	Permutational Quantum Computing
	Abstract. In topological quantum computation the geometric details of a particle trajectory are irrelevant; only the topology matters. Taking this one step further, we consider a model of computation that disregards even the topology of the particle trajectory, and computes by permuting particles. Whereas topological quantum computation requires anyons, permutational quantum computation can be performed with ordinary spin-1/2 particles, using a variant of the spin-network scheme of Marzuoli and Rasetti. We do not know whether permutational computation is universal. It may represent a new complexity class within BQP. Nevertheless, permutational quantum computers can in polynomial time approximate matrix elements of certain irreducible representations of the symmetric group and simulate certain processes in the Ponzano-Regge spin foam model of quantum gravity. No polynomial time classical algorithms for these problems are known.
4:00-4:30	Peter Love, Haverford College
	Some new constructions for Local Hamiltonian and universal adiabatic quantum computing
	Abstract. The difficulty of finding the ground state energy of a Hamiltonian is formalized in quantum complexity theory through the problem Local Hamiltonian. Various restrictions of the form of the Hamiltonians in this problem have been studied, including, inter alia, restricted locality and geometry of couplings, coupling strengths, interaction types and stoquasticity of the Hamiltonians. Concomitantly, such results typically tell us which physical Hamiltonians are capable of realizing universal quantum computation adiabatically. In this talk I will describe some new results on the problem Local Hamiltonian that allow universal adiabatic quantum computation in stoquastic Hamiltonians, restrict the form of the Hamiltonian required, and reduce (but do not eliminate) the need for perturbative gadgets. I will discuss the implications of these results for the design of universal adiabatic quantum computers.
4:30-5:00	Ali Rezakhani, University of Southern California
	Geometrization of quantum adiabatic computation
	Abstract. A time-optimal approach to adiabatic quantum computation (AQC) will be formulated. The corresponding natural Riemannian metric is also derived, through which AQC can be understood as the problem of finding a geodesic on the manifold of control parameters. This geometrization of AQC and its relation with quantum phase transitions are demonstrated through some examples, where we show that the geometric formulation leads to improved performance of AQC, and sheds light on the roles of entanglement and curvature of the control manifold in algorithmic performance.
5:00-5:30	Aaron Denney, University of New Mexico
	Distinguishing the Borel subgroups of PSL(2; q)
	Abstract. The Hidden Subgroup Problem (HSP) has been a fruitful framework for expressing many quantum algorithms, and the Abelian case is completely understood. Most efforts to attack non-Abelian groups have been based on splitting these groups into simpler factors. The non-Abelian simple group PSL(2; q) has no non-trivial factors, so cannot be attacked in this way. Further, it has no known efficient quantum Fourier transform. As such, the standard method for distinguishing subgroups fails almost from the beginning. However, we can use the 3-transitivity of PSL(2; q) to distinguish among a large set of stabilizer subgroups by working with their intersections, and reducing to a smaller group with an efficient transform. These stabilizer subgroups are conjugates of the Borel subgroup of upper triangular matrices. Although restricted to this one class of subgroups, this is the first efficient algorithm for a case of the HSP in a family of non-Abelian simple groups.