[QIP-Sem] QIP seminar, Mon 11/5, 4pm, 36-428, Pawel Wocjan

[Peter Shor]

MIT Quantum Information Processing seminar
Monday 11/5 at 4pm in 36-428
-------------------------------------------------

Pawel Wocjan (UCF)

Classical Problems Characterizing the Power of Quantum Computing

Abstract:

We construct a translation invariant finite-range interaction on a one-dimensional qudit chain and prove that a  single-shot measurement of the energy of an appropriate computational basis state with respect to this Hamiltonian provides the output of any quantum circuit. The required measurement accuracy scales inverse polynomially with the size of the simulated quantum circuit, showing that the implementation of energy measurements on generic qudit chains is as hard as the realization of universal quantum computation. Here a measurement is any procedure that samples from the spectral measure induced by the observable and the state under consideration. 

Starting from this physically motivated problem, we formulate two simple purely classical PromiseBQP-complete problems. Roughly speaking, the first problem is to decide whether a diagonal entry of a power of a sparse matrix is greater or smaller than a certain value.  The second is the following combinatorial problem. We are given three strings s, t, and t' over some finite alphabet and a symmetric relation on substrings of constant length. The relation specifies which substrings are allowed to be replaced with each other. The problem is to decide for a specific value m whether there are more possibilities to obtain t or t' from s after exactly m replacements.

This talk is based on joint projects with Dominik Janzing and Shengyu Zhang.

-------------------------------------------------
http://qis.mit.edu
http://mailman.mit.edu/mailman/listinfo/qip-sem