Date:10:00am, June 30, 2010

Venue：Conference Hall 322，Science Building

Title: What's wrong with qubits?

Speaker: Zeng Bei (University of Waterloo)

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.