Guidable Local Hamiltonian Problems with Implications to Heuristic Ansatz State Preparation and Quantum PCP
Explore a conference talk from TQC 2024 examining 'Merlinized' versions of Guided Local Hamiltonian problems and their implications for quantum computing. Delve into the study of Guidable Local Hamiltonian problems, focusing on two classes of guiding states: those prepared efficiently by quantum circuits and classically evaluatable states. Learn how these problems are QCMA-complete in inverse-polynomial precision settings while falling within NP or NqP for constant precision when using classically evaluatable guiding states. Discover the complexity-theoretic implications showing classical Ansätze with classical heuristics match quantum Ansätze with quantum heuristics when quantum phase estimation is available. Examine contributions to the quantum PCP conjecture, including the definition of quantum-classical probabilistically checkable proof systems, limitations of quantum reduction dequantization, constraints on quantum gap amplification, and proposed stronger versions of the NLTS theorem. Presented at the 19th Conference on Theory of Quantum Computation, Communication and Cryptography at OIST, Japan, this research advances theoretical quantum information science understanding. Read more