Meeting notes 11 05 04

Kamil

Thinking about quantum CAs (cellular automata) and quantum finite state machines (FSMs). The steps of a quantum FSM are unitaries, controlled by the input string. These don't generalize classical FSMs, since they're always reversible. Unless the controlled operations are non-unitary (i.e. TPCP operations). Reversibility causes some problems. For example, a reversible FSM can't recognize the language of binary strings of Hamming weight 1. Scott Aaronson has worked on quantum FSMs; see 1101.5355.

David

Wants to distinguish two loops each of size N from one loop of size 2N. We should think of N as exponential. But how to properly encode them in an oracle? Some classical sampling circuits can be turned into quantum circuits that can q-sample the same distributions. Or we could use a quantum oracle (i.e. a big black-box unitary).

Johnny

Generally the k-local Hamiltonian problem in QMA-complete. But what if the Hamiltonian is made of commuting Paulis? In this case, it's in P. He's also looking at perturbative gadgets that can be used for tasks like reducing k-local Hamiltonians to 2-local Hamiltonians. By gadgets, he means <math>H = H_0 + x \sum_i V_i </math> where the x and x² terms are zero and the desired terms show up at the third order of perturbation. One relevant paper is 0803.2686