Fugu-MT 論文翻訳(概要): Towards a universal gateset for $\mathsf{QMA}

論文の概要: Towards a universal gateset for $\mathsf{QMA}_1$

arxiv url: http://arxiv.org/abs/2411.02681v1
Date: Mon, 04 Nov 2024 23:39:27 GMT
ステータス: 翻訳完了
システム内更新日: 2024-11-06 14:58:51.307709
Title: Towards a universal gateset for $\mathsf{QMA}_1$
Title（参考訳）: $\mathsf{QMA}_1$ の普遍ゲートセットに向けて
Authors: Dorian Rudolph,
Abstract要約: 我々は、シクロトミック場 $mathbbQ(zeta_2k),zeta_2k=e2pi i/2k$, $G_2k$ のすべてのゲートセットに対して、$mathbbQ(zeta_2k),zeta_2k=e2pi i/2k$ のすべてのゲートセットが普遍であることを証明する。また、キングによって定義されたガッペド・クリッドホモロジー問題も証明する。
参考スコア（独自算出の注目度）: 0.0
License:
Abstract: $\mathsf{QMA}_1$ is $\mathsf{QMA}$ with perfect completeness, i.e., the prover must accept with a probability of exactly $1$ in the YES-case. Whether $\mathsf{QMA}_1$ and $\mathsf{QMA}$ are equal is still a major open problem. It is not even known whether $\mathsf{QMA}_1$ has a universal gateset; Solovay-Kitaev does not apply due to perfect completeness. Hence, we do not generally know whether $\mathsf{QMA}_1^G=\mathsf{QMA}_1^{G'}$ (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\in\mathbb N$, the gateset $G_{2^k}$ (Amy et al., RC 2024) is universal for all gatesets in the cyclotomic field $\mathbb{Q}(\zeta_{2^k}),\zeta_{2^k}=e^{2\pi i/2^k}$, i.e. $\mathsf{QMA}_1^G\subseteq\mathsf{QMA}_1^{G_{2^k}}$ for all gatesets $G$ in $\mathbb{Q}(\zeta_{2^k})$. For $\mathsf{BQP}_1$, we can even show that $G_2$ suffices for all $2^k$-th cyclotomic fields. We exhibit complete problems for all $\mathsf{QMA}_1^{G_{2^k}}$: Quantum $l$-SAT in $\mathbb{Q}(\zeta_{2^k})$ is complete for $\mathsf{QMA}_1^{G_{2^k}}$ for all $l\ge4$, and $l=3$ if $k\ge3$, 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 $\mathsf{QMA}_1$-complete $2$-local Hamiltonian problem: It is $\mathsf{QMA}_1^{G_{2^k}}$-complete (for $k\ge3$) to decide whether a given $2$-local Hamiltonian $H$ in $\mathbb{Q}(\zeta_{2^k})$ has a nonempty nullspace. Our techniques also extend to sparse Hamiltonians, and so we can prove the first $\mathsf{QMA}_1(2)$-complete (i.e. $\mathsf{QMA}_1$ with two unentangled provers) Hamiltonian problem. Finally, we prove that the Gapped Clique Homology problem defined by King and Kohler (FOCS 2024) is $\mathsf{QMA}_1^{G_2}$-complete, and the Clique Homology problem without promise gap is PSPACE-complete.
Abstract（参考訳）: $\mathsf{QMA}_1$ is $\mathsf{QMA}$ with perfect completeness, すなわち、証明者はYESケースで正確に1ドルという確率で受け入れなければならない。 $\mathsf{QMA}_1$ と $\mathsf{QMA}$ が等しいかどうかは依然として主要な開問題である。 $\mathsf{QMA}_1$ が普遍ゲートセットを持つかどうかさえ分かっていないが、Solovay-Kitaev は完全性のために適用されない。したがって、一般に$\mathsf{QMA}_1^G=\mathsf{QMA}_1^{G'}$ (superscript denoting gateset) が2つの普遍ゲートセットに対して$G,G'$であるかどうかを知らない。本稿では、すべての$k\in\mathbb N$に対して、ゲートセット$G_{2^k}$ (Amy et al , RC 2024) がシクロトミック場$\mathbb{Q}(\zeta_{2^k}),\zeta_{2^k}=e^{2\pi i/2^k}$、すなわち$\mathsf{QMA}_1^G\subseteq\mathsf{QMA}_1^{G_{2^k}}$ のすべてのゲートセット$G$に対して普遍であることを証明する。 $\mathsf{BQP}_1$ に対して、$G_2$ suffices for all $2^k$-th cyclotomic field を示すこともできる。すべての$\mathsf{QMA}_1^{G_{2^k}}$: Quantum $l$-SAT in $\mathbb{Q}(\zeta_{2^k})$ is complete for $\mathsf{QMA}_1^{G_{2^k}}$ for all $l\ge4$, and $l=3$ if $k\ge3$。さらに、最初の$\mathsf{QMA}_1$-complete $2-local Hamiltonian problem: $\mathsf{QMA}_1^{G_{2^k}}$-complete ($k\ge3$) を与え、与えられた2$-local Hamiltonian $H$ in $\mathbb{Q}(\zeta_{2^k})$ が空でないヌル空間を持つかどうかを決定する。我々の手法はスパースハミルトニアンにも拡張されるので、最初の$\mathsf{QMA}_1(2)$-complete(つまり、2つのアンタングルプローバーを持つ$\mathsf{QMA}_1$)を証明できる。最後に、King and Kohler (FOCS 2024) が定義したGapped Clique Homology 問題は $\mathsf{QMA}_1^{G_2}$-complete であり、約束ギャップのないClique Homology 問題は PSPACE-complete であることを示す。

論文の概要: Towards a universal gateset for $\mathsf{QMA}_1$

関連論文リスト