The local Hamiltonian problem is the canonical QMA-complete problem, and O(2n) time classical algorithms and O(2n/2) time quantum algorithms are known to solve the problem in the worst case. It is not clear how to improve these brute force strategies for a broad class of the problem because ground states are highly entangled in general, and we cannot directly apply known strategies for classical CSPs.
In this work, we present exponentially faster classical and quantum algorithms under two mild assumptions: (1) the Hamiltonian is frustration-free on YES instances, and (2) it is approximately regular, meaning that every qubit is acted upon by approximately the same number of constraints.
We complement these upper bounds by showing that, assuming (Q)SETH, quantum 5-SAT admits no non-trivial worst-case speedup. Our lower bound further demonstrates that the dependence of our algorithms on regularity is in some sense nearly optimal. Specifically, quantum 5-SAT remains (Q)SETH-hard even for Hamiltonians in which all but O(n) qubits participate in only constantly many constraints, while the remaining O(n) qubits each participate in O(n) constraints. By contrast, if either the size of this high-degree subset or the degrees of its qubits is reduced by a factor of nδ, for any δ>0, our algorithm solves the problem in time O(2(1−ε)n) for some ε>0.
Together, our upper and lower bounds establish a fine-grained complexity dichotomy for quantum satisfiability.
Fine-grained quantum supremacy is a study of proving (nearly) tight time lower bounds for classical simulations of quantum computing under "fine-grained complexity" assumptions. We show that under conjectures on Orthogonal Vectors (OV), 3-SUM, All-Pairs Shortest Paths (APSP) and their variants, strong and weak classical simulations of quantum computing are impossible in certain exponential time with respect to the number of qubits. Those conjectures are widely used in classical fine-grained complexity theory in which polynomial time hardness is conjectured. All previous results of fine-grained quantum supremacy are based on ETH, SETH, or their variants that are conjectures for SAT in which exponential time hardness is conjectured. We show that there exist quantum circuits which cannot be classically simulated in certain exponential time with respect to the number of qubits first by considering a Quantum Random Access Memory (QRAM) based quantum computing model and next by considering a non-QRAM model quantum computation. In the case of the QRAM model, the size of quantum circuits is linear with respect to the number of qubits and in the case of the non-QRAM model, the size of the quantum circuits is exponential with respect to the number of qubits but the results are still non-trivial.
In classical fine-grained complexity, the 3SUM Conjecture is used to prove a variety of conditional lower bounds on data structure and graph problems via an initial reduction to the SetDisjointness problem. However, there is an O~(n)-time quantum algorithm for 3SUM and a direct application of Grover's algorithm to SetDisjointness queries beats the state-of-the-art classical conditional bound by Kopelowitz, Pettie, and Porat (SODA 2016); this shows that these classical bounds do not apply in the quantum setting. Thus establishing analogous conditional lower bounds in the quantum setting requires applying the quantum 3SUM Conjecture to a \emph{quantum} fine-grained reduction from 3SUM to SetDisjointness.
We give the first sub-linear time quantum reductions from 3SUM to online SetDisjointness. Via our reduction, the quantum 3SUM conjecture implies a p+2q⩾1 tradeoff bound for quantum SetDisjointness algorithms with O(Np) preprocessing time and O(Nq) query time. We also give an analogous reduction from 3XOR. These results are derived from a general framework for fine-grained reductions to SetDisjointness which applies to any Abelian 3-Orthogonal Array (3OA) problem with suitable almost-linear hash functions.