Guidable Local Hamiltonian Problems with Implications | Jordi , Marten Folkertsma and Cade| TQC 2024

Guidable Local Hamiltonian Problems with Implications to Heuristic Ansatz State Preparation and the Quantum PCP Conjecture | Jordi Weggemans, Marten Folkertsma and Chris Cade We study 'Merlinized' versions of the recently defined Guided Local Hamiltonian problem, which we call 'Guidable Local Hamiltonian' problems. Unlike their guided counterparts, these problems do not have a guiding state provided as a part of the input, but merely come with the promise that one exists. We consider in particular two classes of guiding states: those that can be prepared efficiently by a quantum circuit; and those belonging to a class of quantum states we call classically evaluatable, for which it is possible to efficiently compute expectation values of local observables classically. We show that guidable local Hamiltonian problems for both classes of guiding states are 𝖰𝖢𝖬𝖠-complete in the inverse-polynomial precision setting, but lie within 𝖭𝖯 (or 𝖭𝗊𝖯) in the constant precision regime when the guiding state is classically evaluatable. Our completeness results show that, from a complexity-theoretic perspective, classical Ansätze selected by classical heuristics are just as powerful as quantum Ansätze prepared by quantum heuristics, as long as one has access to quantum phase estimation. In relation to the quantum PCP conjecture, we (i) define a complexity class capturing quantum-classical probabilistically checkable proof systems and show that it is contained in BQP^NP[1] for constant proof queries; (ii) give a no-go result on 'dequantizing' the known quantum reduction which maps a 𝖰𝖯𝖢𝖯-verification circuit to a local Hamiltonian with constant promise gap; (iii) give several no-go results for the existence of quantum gap amplification procedures that preserve certain ground state properties; and (iv) propose two conjectures that can be viewed as stronger versions of the NLTS theorem. Finally, we show that many of our results can be directly modified to obtain similar results for the class 𝖬𝖠. TQC 2024 | 9-13 September 2024 at OIST, Japan http://tqc-conference.org 19th Conference on the Theory of Quantum Computation, Communication and Cryptography. TQC is a leading annual international conference for students and researchers working in the theoretical aspects of quantum information science. The scientific objective is to bring together the theoretical quantum information science community to present and discuss the latest advances in the field. Organisation: OIST: Okinawa Institute for Science and Technology Squids: Schools for Quantum Information Development Sponsors: JPMorganChase Google Quantum AI Horizon Quantum Computing Quantinuum Japan National Tourism Organization