Non-Unitary Quantum Computation in the Ground Space of Local Hamiltonians
arXiv:1703.08118 · doi:10.1103/PhysRevA.96.032321
Abstract
A central result in the study of Quantum Hamiltonian Complexity is that the k-Local hamiltonian problem is QMA-complete. In that problem, we must decide if the lowest eigenvalue of a Hamiltonian is bounded below some value, or above another, promised one of these is true. Given the ground state of the Hamiltonian, a quantum computer can determine this question, even if the ground state itself may not be efficiently quantum preparable. Kitaev's proof of QMA-completeness encodes a unitary quantum circuit in QMA into the ground space of a Hamiltonian. However, we now have quantum computing models based on measurement instead of unitary evolution, furthermore we can use post-selected measurement as an additional computational tool. In this work, we generalise Kitaev's construction to allow for non-unitary evolution including post-selection. Furthermore, we consider a type of post-selection under which the construction is consistent, which we call tame post-selection. We consider the computational complexity consequences of this construction and then consider how the probability of an event upon which we are post-selecting affects the gap between the ground state energy and the energy of the first excited state of its corresponding Hamiltonian. We provide numerical evidence that the two are not immediately related, by giving a family of circuits where the probability of an event upon which we post-select is exponentially small, but the gap in the energy levels of the Hamiltonian decreases as a polynomial.
arXiv comment14 pages, 6 figures
References in corpus (8)
- Measurement-based quantum computation
- Classical simulation of commuting quantum computations implies collapse of the polynomial hierarchy
- How hard is it to approximate the Jones polynomial?
- Measurement-based classical computation
- Space-Time Circuit-to-Hamiltonian Construction and Its Applications
- Commutative version of the k-local Hamiltonian problem and common eigenspace problem
- The Complexity of Stoquastic Local Hamiltonian Problems
- Quantum Merlin Arthur with Exponentially Small Gap
Cited by in corpus (13)
- Importance of the spectral gap in estimating ground-state energies
- Analysis and limitations of modified circuit-to-Hamiltonian constructions
- Engineering Yang-Lee anyons via Majorana bound states
- Non-Abelian Anyons and Non-Abelian Vortices in Topological Superconductors
- Detailed Analysis of Circuit-to-Hamiltonian Mappings
- Translationally-Invariant Universal Quantum Hamiltonians in 1D
- Perturbation Gadgets: Arbitrary Energy Scales from a Single Strong Interaction
- Unextendible product operator basis
- Rewindable Quantum Computation and Its Equivalence to Cloning and Adaptive Postselection
- Tunable Tradeoff between Quantum and Classical Computation via Nonunitary Zeno-like Dynamics
- Nonunitary gates using measurements only
- Hardness of efficiently generating ground states in postselected quantum computation
- QMA(2) with postselection equals to NEXP