A single-shot measurement of the energy of product states in a translation invariant spin chain can replace any quantum computation
arXiv:0710.1615 · doi:10.1088/1367-2630/10/9/093004
Abstract
In measurement-based quantum computation, quantum algorithms are implemented via sequences of measurements. We describe a translationally invariant finite-range interaction on a one-dimensional qudit chain and prove that a single-shot measurement of the energy of an appropriate computational basis state with respect to this Hamiltonian provides the output of any quantum circuit. The required measurement accuracy scales inverse polynomially with the size of the simulated quantum circuit. This shows that the implementation of energy measurements on generic qudit chains is as hard as the realization of quantum computation. Here a ''measurement'' is any procedure that samples from the spectral measure induced by the observable and the state under consideration. As opposed to measurement-based quantum computation, the post-measurement state is irrelevant.
arXiv comment19 pages, transition rules for the CA corrected
References in corpus (12)
- Two-Bit Gates are Universal for Quantum Computation
- Efficient quantum algorithms for simulating sparse Hamiltonians
- The power of quantum systems on a line
- Unified derivations of measurement-based schemes for quantum computation
- Quantum computing via measurements only
- Quantum simulators, continuous-time automata, and translationally invariant systems
- A universally programmable Quantum Cellular Automaton
- Several natural BQP-Complete problems
- Spin-1/2 particles moving on a 2D lattice with nearest-neighbor interactions can realize an autonomous quantum computer
- Generation of eigenstates using the phase-estimation algorithm
- BQP-complete Problems Concerning Mixing Properties of Classical Random Walks on Sparse Graphs
- Measuring 4-local n-qubit observables could probabilistically solve PSPACE
Cited by in corpus (8)
- Adiabatic Quantum Computing
- The power of quantum systems on a line
- Hamiltonian Quantum Cellular Automata in 1D
- Ground State Entanglement in One Dimensional Translationally Invariant Quantum Systems
- The Quantum and Classical Complexity of Translationally Invariant Tiling and Hamiltonian Problems
- Local Hamiltonians in Quantum Computation
- Quantum advantage from energy measurements of many-body quantum systems
- A PromiseBQP-complete String Rewriting Problem