Interacting boson problems are QMA-hard Export

@article{arXiv_0905_3413 , abstract = {Computing the ground-state energy of interacting electron (fermion) problems has recently been shown to be hard for QMA, a quantum analogue of the complexity class NP. Fermionic problems are usually hard, a phenomenon widely attributed to the so-called sign problem occurring in Quantum Monte Carlo simulations. The corresponding bosonic problems are, according to conventional wisdom, tractable. Here, we discuss the complexity of interacting boson problems and show that they are also QMA-hard. In addition, we show that the bosonic version of the so-called N-representability problem is QMA-complete, as hard as its fermionic version. As a consequence, these problems are unlikely to have efficient quantum algorithms.}, archivePrefix = {arXiv}, author = {Wei, Tzu-Chieh and Mosca, Michele and Nayak, Ashwin}, citeulike-article-id = {4574211}, citeulike-linkout-0 = {http://arxiv.org/abs/0905.3413}, citeulike-linkout-1 = {http://arxiv.org/pdf/0905.3413}, eprint = {0905.3413}, keywords = {bosons, complexity, computation}, month = {May}, posted-at = {2009-07-03 10:38:19}, priority = {2}, title = {Interacting boson problems are QMA-hard}, url = {http://arxiv.org/abs/0905.3413}, year = {2009} }

TY - JOUR ID - arXiv_0905_3413 L3 - citeulike-article-id:4574211 N2 - Computing the ground-state energy of interacting electron (fermion) problems has recently been shown to be hard for QMA, a quantum analogue of the complexity class NP. Fermionic problems are usually hard, a phenomenon widely attributed to the so-called sign problem occurring in Quantum Monte Carlo simulations. The corresponding bosonic problems are, according to conventional wisdom, tractable. Here, we discuss the complexity of interacting boson problems and show that they are also QMA-hard. In addition, we show that the bosonic version of the so-called N-representability problem is QMA-complete, as hard as its fermionic version. As a consequence, these problems are unlikely to have efficient quantum algorithms. TI - Interacting boson problems are QMA-hard KW - bosons KW - complexity KW - computation AU - Wei, Tzu-Chieh AU - Mosca, Michele AU - Nayak, Ashwin PY - 2009/May/20/ UR - http://arxiv.org/abs/0905.3413 ER -