[QIP-Sem] QIP seminar, Mon 5/17, 4:30, 36-462, Zeng,Bei

[Peter Shor]

MIT Quantum Information Processing seminar
Monday 5/17 at 4:30 in 36-462
-------------------------------------------------

 Zeng,Bei (University of Waterloo)

What's wrong with qubits?

Abstract:

Quantum 2-SAT is a problem of asking whether there exists a state of n qubits such that its 2-qubit reduced density matrices have support on prescribed subspaces. Here, we show that every positive instance of Quantum 2-SAT always has a solution that is a product of single- or two-qubit states. This gives a no-go theorem for one-way quantum computing, which says that in order to do one-way quantum computing with a natural ground state of a two-body frustration-free Hamiltonian, one has to go to higher dimensional particle systems other than qubit systems. Furthermore, we give a characterization of the whole solution space of the Quantum 2-SAT problem in terms of span of product states. This characterization implies that the counting version of Quantum 2-SAT is in #P, and therefore #P-Complete. Our results indicate that entanglement plays almost no role in the Quantum 2-SAT problem. Joint work with Jianxin Chen, Xie Chen, Runyao Duan, Zhengfeng Ji and Zhaohui Wei. 

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