Detailed Analysis of Circuit-to-Hamiltonian Mappings
arXiv:1910.01481
Abstract
The circuit-to-Hamiltonian construction has found widespread use within the field of Hamiltonian complexity, particularly for proving QMA-hardness results. In this work we examine the ground state energies of the Hamiltonian for standard clock constructions and those which require dynamic initialisation. We put exponentially tight bounds on these ground state energies and also determine improved scaling bounds in the case where there is a constant probability of the computation being rejected. Furthermore, we prove a collection of results concerning the low-energy subspace of quantum walks on a line with energy penalties appearing at any point along the walk and introduce some general tools that may be useful for such analyses.
arXiv comment43 pages, 3 figures. arXiv admin note: text overlap with arXiv:1502.04573 by other authors
References in corpus (9)
- Undecidability of the Spectral Gap (short version)
- The power of quantum systems on a line
- Computational Difficulty of Computing the Density of States
- The Feynman-Kitaev computer's clock: bias, gaps, idling and pulse tuning
- Non-Unitary Quantum Computation in the Ground Space of Local Hamiltonians
- Good approximate quantum LDPC codes from spacetime circuit Hamiltonians
- Quantum ground state isoperimetric inequalities for the energy spectrum of local Hamiltonians
- Complexity classification of local Hamiltonian problems
- History-state Hamiltonians are critical