Commuting local Hamiltonian problem unlikely to be as hard as quantum computing
The Commuting Local Hamiltonian Problem: Relativized Evidence Against BQP-Hardness
Computational Complexity
Summary
The commuting local Hamiltonian problem is a simplified version of a puzzle in quantum physics and computer science. This work shows that this problem is probably not as hard as some of the toughest problems related to quantum computers. They do this by creating a scenario with a special kind of helper (called an oracle) that makes it clear the simpler problem is easier than general quantum problems. This suggests you shouldn't expect to solve these simpler problems using the full power of quantum computers.
What this means in practice
- •For quantum algorithm designers: Know that commuting local Hamiltonian problems are unlikely to encode the hardest quantum computations, guiding focus towards more challenging problems for quantum advantage.
- •For quantum hardware developers: Avoid targeting commuting local Hamiltonian problems when seeking benchmarks that demonstrate full quantum computational power.
A theory result. No direct application yet.
Authors
Itay Shalit, Mark Zhandry
Abstract
The commuting local-Hamiltonian (CLH) problem is a restriction of the local-Hamiltonian problem, in which the terms of the Hamiltonian are required to pairwise commute. A long line of work has shown that the problem lies in $\mathsf{NP}$ for certain families of commuting local Hamiltonians. Nevertheless, there has been no formal evidence against the possibility that the general CLH problem is $\mathsf{QMA}$-complete. CLH is complete for the complexity class $\mathsf{QIMA}$, defined through quantum verifiers whose local gates commute. Therefore, CLH is $\mathsf{QMA}$-complete if and only if $\mathsf{QIMA}=\mathsf{QMA}$. In this work, we introduce a classical-oracle analogue $\mathsf{QIMA}^{\mathcal{O}}$ and construct a classical oracle $\mathcal{O}$ such that $\mathsf{BQP}^{\mathcal{O}}\not\subseteq\mathsf{QIMA}^{\mathcal{O}}$. Since $\mathsf{BQP}^{\mathcal{O}}\subseteq\mathsf{QMA}^{\mathcal{O}}$ for any classical oracle $\mathcal{O}$, this implies $\mathsf{QIMA}^{\mathcal{O}}\neq\mathsf{QMA}^{\mathcal{O}}$ for our constructed oracle. Thus, our result provides relativized evidence against the possibility that the general commuting local-Hamiltonian problem is $\mathsf{BQP}$-hard, and hence also against the possibility that it is $\mathsf{QMA}$-complete.