eprintid: 1556721 rev_number: 27 eprint_status: archive userid: 608 dir: disk0/01/55/67/21 datestamp: 2017-05-20 22:05:48 lastmod: 2021-09-19 23:39:25 status_changed: 2017-10-17 13:27:18 type: article metadata_visibility: show creators_name: Usher, N creators_name: Hoban, MJ creators_name: Browne, DE title: Nonunitary quantum computation in the ground space of local Hamiltonians ispublished: pub divisions: UCL divisions: B04 divisions: C05 divisions: C06 divisions: F60 keywords: Science & Technology, Physical Sciences, Optics, Physics, Atomic, Molecular & Chemical, Physics, LINEAR OPTICS, COMPLEXITY note: ©2017 American Physical Society. This version is the version of record. For information on re-use, please refer to the publisher’s terms and conditions. abstract: A central result in the study of quantum Hamiltonian complexity is that the k-local Hamiltonian problem is quantum-Merlin-Arthur–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 postselected measurement as an additional computational tool. In this work, we generalize Kitaev’s construction to allow for nonunitary evolution including postselection. Furthermore, we consider a type of postselection under which the construction is consistent, which we call tame postselection. We consider the computational complexity consequences of this construction and then consider how the probability of an event upon which we are postselecting 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 postselect is exponentially small, but the gap in the energy levels of the Hamiltonian decreases as a polynomial. date: 2017-09-12 date_type: published publisher: AMER PHYSICAL SOC official_url: http://doi.org/10.1103/PhysRevA.96.032321 oa_status: green full_text_type: pub language: eng primo: open primo_central: open_green article_type_text: Article verified: verified_manual elements_id: 1282238 doi: 10.1103/PhysRevA.96.032321 lyricists_name: Browne, Daniel lyricists_name: Usher, Nairi lyricists_id: DEBRO32 lyricists_id: USHER51 actors_name: Browne, Daniel actors_name: Laslett, David actors_id: DEBRO32 actors_id: DLASL34 actors_role: owner actors_role: impersonator full_text_status: public publication: Physical Review A volume: 96 number: 3 article_number: 032321 pages: 12 issn: 2469-9934 citation: Usher, N; Hoban, MJ; Browne, DE; (2017) Nonunitary quantum computation in the ground space of local Hamiltonians. Physical Review A , 96 (3) , Article 032321. 10.1103/PhysRevA.96.032321 <https://doi.org/10.1103/PhysRevA.96.032321>. Green open access document_url: https://discovery.ucl.ac.uk/id/eprint/1556721/1/Browne_PhysRevA.96.032321.pdf