The Complexity of Quantum Systems on a One-dimensional Chain
| dc.creator | Irani, Sandy | |
| dc.date | 2007-05-28 | |
| dc.date | 2008-02-19 | |
| dc.date.accessioned | 2026-07-07T09:21:19Z | |
| dc.date.available | 2026-07-07T09:21:19Z | |
| dc.description | We prove that adiabatic computation is equivalent to standard quantum computation even when the adiabatic quantum system is restricted to be a set of particles on a one-dimensional chain. We give a construction that uses a 2-local Hamiltonian on nearest neighbors using particles that can have ten distinct states. This implies a construction of a one-dimensional chain of qubits in which the Hamiltonian is 6-local. We adapt this construction to show that the 2-local Hamiltonian for 13-state particles is QMA-complete which in turn implies that the 8-local Hamiltonian restricted to a one-dimensional chain of qubits is QMA-complete. | |
| dc.description | This paper has been merged with arXiv:0705.4077 and is now co-authored with Dorit Aharonov, Daniel Gottesman, and Julia Kempe. Ther version posted here is the same as the original version | |
| dc.identifier | https://arxiv.org/abs/0705.4067 | |
| dc.identifier | http://arxiv.org/abs/0705.4067 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/154980 | |
| dc.subject | Quantum Physics | |
| dc.title | The Complexity of Quantum Systems on a One-dimensional Chain | |
| dc.type | text |