The Guided Local Hamiltonian problem for stoquastic Hamiltonians is promise BPP-hard (even 2-local on lattices), BQP-hard under fixed local constraints, and admits a deterministic classical approximation algorithm when promise gap, overlap, and spectral gap are constant with constant-depth local-pre
Quantum Computational Complexity
4 Pith papers cite this work. Polarity classification is still indexing.
4
Pith papers citing it
abstract
This article surveys quantum computational complexity, with a focus on three fundamental notions: polynomial-time quantum computations, the efficient verification of quantum proofs, and quantum interactive proof systems. Properties of quantum complexity classes based on these notions, such as BQP, QMA, and QIP, are presented. Other topics in quantum complexity, including quantum advice, space-bounded quantum computation, and bounded-depth quantum circuits, are also discussed.
fields
quant-ph 4verdicts
UNVERDICTED 4representative citing papers
Defines bosonic analogs of BQP and QMA, proves Gaussian dynamics equivalent to BQL, places expectation values in PSPACE, and shows stellar-rank-dependent complexity for bosonic energy minimization from NP-complete to undecidable.
Local quenches in chaotic quantum systems produce a Renyi-index-tuned hierarchy of entanglement transitions, with S_alpha>1 obeying area law while S_alpha<=1 is volume-law, carried by an O(1)-dimensional dominant Schmidt sector that itself exhibits similar transitions at lower critical indices.
The succinct state 2-local Hamiltonian problem for qubit Hamiltonians is promise-MA-complete.
citing papers explorer
-
The Guided Local Hamiltonian Problem for Stoquastic Hamiltonians
The Guided Local Hamiltonian problem for stoquastic Hamiltonians is promise BPP-hard (even 2-local on lattices), BQP-hard under fixed local constraints, and admits a deterministic classical approximation algorithm when promise gap, overlap, and spectral gap are constant with constant-depth local-pre
-
Bosonic Quantum Computational Complexity
Defines bosonic analogs of BQP and QMA, proves Gaussian dynamics equivalent to BQL, places expectation values in PSPACE, and shows stellar-rank-dependent complexity for bosonic energy minimization from NP-complete to undecidable.
-
Hierarchical entanglement transitions and hidden area-law sectors in quantum many-body dynamics
Local quenches in chaotic quantum systems produce a Renyi-index-tuned hierarchy of entanglement transitions, with S_alpha>1 obeying area law while S_alpha<=1 is volume-law, carried by an O(1)-dimensional dominant Schmidt sector that itself exhibits similar transitions at lower critical indices.
-
On the Complexity of the Succinct State Local Hamiltonian Problem
The succinct state 2-local Hamiltonian problem for qubit Hamiltonians is promise-MA-complete.