Behavior of O(log n) local commuting hamiltonians

Mehta, 2016

Category: Quantum Information

Overall Rating

2.3/5 (16/35 pts)

The primary potential for modern, unconventional research lies in utilizing the explicit Hamiltonian constructions detailed in Sections 5.4 and 5.5 for the ground space traversal problem.
These specific, structured sets of commuting Hamiltonians can serve as unique benchmarks for evaluating the performance and capabilities of emerging quantum algorithms like Variational Quantum Eigensolvers or algorithms for adiabatic state preparation on complex, theoretically hard instances.
The paper contains specific Hamiltonian constructions that could be useful for benchmarking quantum algorithms, but its contributions to the core theoretical problem of O(log n)-CLHP complexity are inconclusive...
...rely on adapted techniques with noted limitations for broader applicability.

The thesis explores the boundary between NP-hard and QMA-hard problems by focusing on the k-local commuting Hamiltonian problem (k-CLHP) at O(log n) locality.
The proof of the generalized area law for commuting Hamiltonians (Lemma 12)... provides a formal technique for bounding entanglement entropy in structured quantum systems.
The specific constructions used in the proofs, particularly the 2-layered O(log n) local commuting Hamiltonian system in the traversal hardness proof, could serve as blueprints for novel algorithmic test cases.
VQAs and adiabatic algorithms directly tackle the problem of finding ground states and traversing energy landscapes. The QCMA hardness result from the thesis provides a strong theoretical benchmark for these new algorithmic approaches.

The primary methods explored lean heavily on the Bravyi-Vyalyi Structure Theorem (BVST)... its direct applicability to general O(log n) local Hamiltonians... has proven challenging for settling the main decision problem.
The area law (Lemma 12) is explicitly described as a "folklore result," its proof presented as "simple," diminishing its originality as a primary contribution.
The most technical result (GSCON hardness in Theorem 25) is an adaptation of a known proof technique from [10] for general local Hamiltonians to the commuting case.
The application of BVST to the O(log n) setting (Lemma 6 proof sketch) is severely limited by the assumption that "any pair of hamiltonians act only one edge (one qudit)." This is not representative of general O(log n) locality.

Watch