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.