2024/11/04 by Dorian Rudolph, Rudolph, Dorian · 2 citations
Computer Science · Engineering · #Coding theory and cryptography #Cellular Automata and Applications #graph theory and CDMA systems
paper · pdf · doi:10.48550/arxiv.2411.02681
QMA1 is QMA with perfect completeness, i.e., the prover must accept with a probability of exactly 1 in the YES-case. Whether QMA1 and QMA are equal is still a major open problem. It is not even known whether QMA1 has a universal gateset; Solovay-Kitaev does not apply due to perfect completeness. Hence, we do not generally know whether QMA1G=QMA1G' (superscript denoting gateset), given two universal gatesets G,G'. In this paper, we make progress towards the gateset question by proving that for all k∈\mathbb N, the gateset G2k (Amy et al., RC 2024) is universal for all gatesets in the cyclotomic field ℚ(ζ2k),ζ2k=e2πi/2k, i.e. QMA1G\subseteqQMA1^G2k for all gatesets G in ℚ(ζ2k). For BQP1, we can even show that G2 suffices for all 2k-th cyclotomic fields. We exhibit complete problems for all QMA1^G2k: Quantum l-SAT in ℚ(ζ2k) is complete for QMA1^G2k for all l≥4, and l=3 if k≥3, where quantum l-SAT is the problem of deciding whether a set of l-local Hamiltonians has a common ground state. Additionally, we give the first QMA1-complete 2-local Hamiltonian problem: It is QMA1^G2k-complete (for k≥3) to decide whether a given 2-local Hamiltonian H in ℚ(ζ2k) has a nonempty nullspace. Our techniques also extend to sparse Hamiltonians, and so we can prove the first QMA1(2)-complete (i.e. QMA1 with two unentangled provers) Hamiltonian problem. Finally, we prove that the Gapped Clique Homology problem defined by King and Kohler (FOCS 2024) is QMA1G2-complete, and the Clique Homology problem without promise gap is PSPACE-complete.