期刊
48TH ANNUAL IEEE SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE, PROCEEDINGS
卷 -, 期 -, 页码 373-+出版社
IEEE COMPUTER SOC
DOI: 10.1109/FOCS.2007.46
关键词
-
资金
- Israel Science Foundation [039-7549]
- Binational Science Foundation [037-8404]
- US Army Research Office [030-7790]
- CIFAR
- Government of Canada through NSERC
- Province of Ontario through MRI
- NSF [CCR-0514082]
- CNRS
- LRI
- University of Paris-Sud, Orsay,France
- European Commission
- IST [015848]
- ANR AlgoQP
- FrenchResearch Ministry
- Alon Fellowship of the Israeli Higher Council of Academic Research
- Individual Research
- ISF
- European Research Council (ERC)
We study the computational strength of quantum particles (each of finite dimensionality) arranged on a line. First, we prove that it is possible to perform universal adiabatic quantum computation using a one-dimensional quantum system (with 9 states per particle). Building on the same construction, but with some additional technical effort and 12 states per particle, we show that the problem of approximating the ground state energy of a system composed of a line of quantum particles is QMA-complete, QMA is a quantum analogue of NP. This is in striking contrast to the analogous classical problem, one dimensional MAX-2-SAT with nearest neighbor constraints, which is in P. The proof of the QMA-completeness result requires an additional idea beyond the usual techniques in the area: Some illegal configurations cannot be ruled out by local checks, and are instead ruled out because they would, in the future, evolve into a state which can be seen locally to be illegal. Assuming BQP not equal QMA, our construction gives a one-dimensional system which takes an exponential time to relax to its ground state at any temperature. This makes it a candidate for a one-dimensional spin glass.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据