Hamiltonian quantum computer in one dimension

Abstract

Quantum computation can be achieved by preparing an appropriate initial product state of qudits and then letting it evolve under a fixed Hamiltonian. The readout is made by measurement on individual qudits at some later time. This approach is called the Hamiltonian quantum computation and it includes, for example, the continuous-time quantum cellular automata and the universal quantum walk. We consider one spatial dimension and study the compromise between the locality $k$ and the local Hilbert space dimension $d$. For geometrically 2-local (i.e., $k=2$), it is known that $d=8$ is already sufficient for universal quantum computation but the Hamiltonian is not translationally invariant. As the locality $k$ increases, it is expected that the minimum required $d$ should decrease. We provide a construction of Hamiltonian quantum computer for $k=3$ with $d=5$. One implication is that simulating 1D chains of spin-2 particles is BQP-complete. Imposing translation invariance will increase the required $d$. For this we also construct another 3-local ($k=3$) Hamiltonian that is invariant under translation of a unit cell of two sites but that requires $d$ to be 8.

arXiv comment13 pages, 6 figures, accepted version

References in corpus (12)

• Fault-tolerant quantum computation by anyons
• Non-Abelian Anyons and Topological Quantum Computation
• A Quantum Adiabatic Evolution Algorithm Applied to Random Instances of an NP-Complete Problem
• Measurement-based quantum computation
• Universal computation by quantum walk
• Adiabatic quantum computation with Cooper pairs
• The power of quantum systems on a line
• Hamiltonian Quantum Cellular Automata in 1D
• Quantum simulators, continuous-time automata, and translationally invariant systems
• A quantum cellular automaton for universal quantum computation
• A universally programmable Quantum Cellular Automaton
• The Computational Power of Symmetric Hamiltonians

Cited by in corpus (4)

• The Complexity of Translationally-Invariant Spin Chains with Low Local Dimension
• The Complexity of Translationally-Invariant Low-Dimensional Spin Lattices in 3D
• Superconducting qubit circuit emulation of a vector spin-1/2
• Perturbation Gadgets: Arbitrary Energy Scales from a Single Strong Interaction