时 间: 2010年6月30日（周三）上午10:00

地 点: 清华大学高等研究院 科学馆322报告厅

题 目: What's wrong with qubits?

报 告 人: Zeng Bei (University of Waterloo)

报告摘要: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.