Program
Full Program | Thursday | Friday | Saturday | All Sessions | Posters | Talks
SESSION 7: Computer Science (Pavilion I - III)Chair: Jon Yard (Microsoft) | |
| 10:15 am - 11:00 am | Ashley Montanaro, (University of Bristol) Quantum speedup of backtracking and Monte Carlo algorithms | Abstract. In this talk I will describe how quantum computing can accelerate two standard types of classical algorithms: backtracking algorithms and Monte Carlo methods. Backtracking is a standard approach for solving constraint satisfaction problems (CSPs). Backtracking algorithms explore a tree whose vertices are partial solutions to a CSP in an attempt to find a complete solution. I will present a bounded-error quantum algorithm which finds a solution in time which is (almost) bounded by the square root of the size of the tree. In particular, this quantum algorithm can be used to speed up the DPLL algorithm, which is the basis of many of the most efficient SAT solvers used in practice. The quantum algorithm is based on the use of a quantum walk algorithm of Belovs to search in the backtracking tree. Monte Carlo methods use random sampling to estimate numerical quantities which are hard to compute deterministically. One important example is the use in statistical physics of rapidly mixing Markov chains to approximately compute partition functions. I will present a quantum algorithm which uses amplitude amplification to estimate the expected output value of an arbitrary randomised or quantum subroutine with bounded variance, and achieves a near-quadratic speedup over the best possible classical algorithm. Combining the algorithm with the use of quantum walks gives a quantum speedup of the fastest known classical algorithms with rigorous performance bounds for computing partition functions, which use multiple-stage Markov chain Monte Carlo techniques. |
| 11:00 am - 11:30 am | Rolando Somma, (Los Alamos National Laboratory) A Trotter-Suzuki approximation for Lie groups with applications to Hamiltonian simulation | Abstract. We present a product formula to approximate the exponential of a skew-Hermitian operator that is a sum of elements of a Lie algebra. The number of terms in the product depends on the structure factors of the algebra. When the dimension of the algebra is small but the elements have large or unbounded norm, or when the norm of nested commutators is significantly less than the product of the norms, our formula results in a significant improvement upon well-known product formulas in the literature. We apply these results to construct product formulas useful for the quantum simulation of continuous-variable, bosonic physical systems. In these cases, we show that the number of terms in the product can be sublinear or even subpolynomial in the dimension of the relevant local Hilbert spaces, where such a dimension is determined by the energy scale of the problem. Our results emphasize the power of quantum computing for the simulation of various quantum systems. |
| 11:30 am - 12:00 pm | Vadym Kliuchnikov, QuArC (Microsoft) A framework for approximating qubit unitaries | Abstract. We present an algorithm for efficiently approximating of qubit unitaries over gate sets derived from totally definite quaternion algebras. It achieves ε-approximations using circuits of length O(log(1/ε)), which is asymptotically optimal. The algorithm achieves the same quality of approximation as previously-known algorithms for Clifford+T [arXiv:1212.6253], V-basis [arXiv:1303.1411] and Clifford+π/12 [arXiv:1409.3552], running on average in time polynomial in O(log(1/ε)) (conditional on a number-theoretic conjecture). Ours is the first such algorithm that works for a wide range of gate sets and provides insight into what should constitute a "good" gate set for a fault-tolerant quantum computer. |
SQuInT Chief Organizer
Prof. Akimasa Miyake
amiyake@unm.edu
SQuInT Co-Organizer
Prof. Elohim Becerra
fbecerra@unm.edu
SQuInT Founder
Prof. Ivan Deutsch
ideutsch@unm.edu
SQuInT Administrator
Gloria Cordova
gjcordo1@unm.edu
505 277-1850
