論文の概要: Quantum 2-SAT on low dimensional systems is $\mathsf{QMA}_1$-complete: Direct embeddings and black-box simulation

• arxiv url: http://arxiv.org/abs/2401.02368v1
• Date: Thu, 4 Jan 2024 17:19:44 GMT
• ステータス: 処理完了
• システム内更新日: 2024-01-05 14:34:25.007654
• Title: Quantum 2-SAT on low dimensional systems is $\mathsf{QMA}_1$-complete: Direct embeddings and black-box simulation
• Title（参考訳）: 低次元系の量子2-SATは$\mathsf{QMA}_1$-complete:直接埋め込みとブラックボックスシミュレーション
• Authors: Dorian Rudolph, Sevag Gharibian, Daniel Nagaj
• Abstract要約: 量子満足度問題は、各制約が$k$-dimensionalと$l$-dimensionalのquditペアに作用し、$(k,l)$-QSATと表される。 最初の結果は、qubits上のQSATが$mathsfQMA_1$-hardであり、$(2,5)$-QSATは$mathsfQMA_1$-completeであることを示している。 2つ目の結果はブラックボックス還元による:$d'$-dimensional qudits上の任意の1Dハミルトニアン$H$を与えられる。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Despite the fundamental role the Quantum Satisfiability (QSAT) problem has played in quantum complexity theory, a central question remains open: At which local dimension does the complexity of QSAT transition from "easy" to "hard"? Here, we study QSAT with each constraint acting on a $k$-dimensional and $l$-dimensional qudit pair, denoted $(k,l)$-QSAT. Our first main result shows that, surprisingly, QSAT on qubits can remain $\mathsf{QMA}_1$-hard, in that $(2,5)$-QSAT is $\mathsf{QMA}_1$-complete. In contrast, $2$-SAT on qubits is well-known to be poly-time solvable [Bravyi, 2006]. Our second main result proves that $(3,d)$-QSAT on the 1D line with $d\in O(1)$ is also $\mathsf{QMA}_1$-hard. Finally, we initiate the study of 1D $(2,d)$-QSAT by giving a frustration-free 1D Hamiltonian with a unique, entangled ground state. Our first result uses a direct embedding, combining a novel clock construction with the 2D circuit-to-Hamiltonian construction of [Gosset, Nagaj, 2013]. Of note is a new simplified and analytic proof for the latter (as opposed to a partially numeric proof in [GN13]). This exploits Unitary Labelled Graphs [Bausch, Cubitt, Ozols, 2017] together with a new "Nullspace Connection Lemma", allowing us to break low energy analyses into small patches of projectors, and to improve the soundness analysis of [GN13] from $\Omega(1/T^6)$ to $\Omega(1/T^2)$, for $T$ the number of gates. Our second result goes via black-box reduction: Given an arbitrary 1D Hamiltonian $H$ on $d'$-dimensional qudits, we show how to embed it into an effective null-space of a 1D $(3,d)$-QSAT instance, for $d\in O(1)$. Our approach may be viewed as a weaker notion of "simulation" (\`a la [Bravyi, Hastings 2017], [Cubitt, Montanaro, Piddock 2018]). As far as we are aware, this gives the first "black-box simulation"-based $\mathsf{QMA}_1$-hardness result, i.e. for frustration-free Hamiltonians.
• Abstract（参考訳）: qsat(quantum satisfiability)問題は量子複雑性理論において基本的な役割を担っているが、中心的な疑問は、どの局所次元において、qsatの複雑性は「容易」から「ハード」に変化するのか、という点にある。 ここでは、各制約が$k$-dimensionalと$l$-dimensionalのquditペアに作用し、QSATを$(k,l)$-QSATと表す。 最初の主要な結果は、驚くほど、量子ビット上の QSAT が $\mathsf{QMA}_1$-hard であり、$(2,5)$-QSAT は $\mathsf{QMA}_1$-complete であることを示している。 対照的に、qubits 上の 2$-SAT はポリ時間可解であることが知られている [Bravyi, 2006]。 2つ目の結果は、$(3,d)$-qsat 1d 行の $d\in o(1)$ もまた $\mathsf{qma}_1$-hard であることを示している。 最後に、1D $(2,d)$-QSATの研究を開始する。 最初の結果は直接埋め込みを使用し,[gosset, nagaj, 2013]の2次元回路からハミルトニアンへの新規なクロック構成を組み合わせる。 注目すべきは、([GN13]の部分的に数値的な証明とは対照的に)後者の新しい単純化された解析的な証明である。 これにより、新しい"Nullspace Connection Lemma"とともにUnitary Labelled Graphs [Bausch, Cubitt, Ozols, 2017] を利用し、低エネルギー解析をプロジェクタの小さなパッチに分割し、[GN13] の音質解析を$\Omega(1/T^6)$から$\Omega(1/T^2)$に改善し、$T$のゲート数を求める。 任意の 1d hamiltonian $h$ on $d'$-dimensional qudits が与えられたとき、それを $d\in o(1)$ に対して 1d $(3,d)$-qsat インスタンスの有効なnull空間に埋め込む方法を示します。 私たちのアプローチは、"シミュレート"(\`a la [Bravyi, Hastings 2017], [Cubitt, Montanaro, Piddock 2018])の弱い概念として見ることができます。 我々の知る限り、これは最初の「ブラックボックスシミュレーション」ベースの$\mathsf{qma}_1$-hardness結果、すなわちフラストレーションのないハミルトニアンを与える。

関連論文リスト

• Efficiency of k-Local Quantum Search and its Adiabatic Variant on Random k-SAT [0.0]
  本稿では、$k$-local quantum searchと呼ばれる、構造化量子探索アルゴリズムのファミリーを紹介する。 最大$k$-SSATは、平均ケース複雑性理論に基づく$m=Omega(n2+epsilon)$が平均であることを証明する。
  論文  参考訳（メタデータ） (2024-03-05T15:03:47Z)
• Parity vs. AC0 with simple quantum preprocessing [0.0]
  我々は、$mathsfAC0$が$mathsfQNC0$回路の測定結果に作用するハイブリッド回路モデルについて検討する。 私たちは、$mathsfQNC0$が、タスクの検索とサンプリングに驚くほど強力なのに対して、その出力のグローバルな相関において、そのパワーは"ロックアウト"されていることに気付きました。
  論文  参考訳（メタデータ） (2023-11-22T20:27:05Z)
• Simulating LDPC code Hamiltonians on 2D lattices [0.0]
  システムサイズにおけるエネルギーペナルティを犠牲にして, 2次元近傍相互作用のみを用いたLDPC符号のシミュレーションを構築した。 我々は、ハミルトニアン符号の基底状態をおよそ再現できるシミュレーションの保証を導出する。
  論文  参考訳（メタデータ） (2023-08-25T09:59:47Z)
• Horizon-free Reinforcement Learning in Adversarial Linear Mixture MDPs [72.40181882916089]
  我々のアルゴリズムが $tildeObig((d+log (|mathcalS|2 |mathcalA|))sqrtKbig)$ regret with full-information feedback, where $d$ is the dimension of a known feature mapping is linearly parametrizing the unknown transition kernel of the MDP, $K$ is the number of episodes, $|mathcalS|$ and $|mathcalA|$ is the standardities of the state and action space。
  論文  参考訳（メタデータ） (2023-05-15T05:37:32Z)
• Near-optimal fitting of ellipsoids to random points [68.12685213894112]
  楕円体をランダムな点に合わせるという基本的な問題は、低ランク行列分解、独立成分分析、主成分分析に関係している。 我々はこの予想を、ある$n = Omega(, d2/mathrmpolylog(d))$ に対する適合楕円体を構成することで対数的因子まで解決する。 我々の証明は、ある非標準確率行列の便利な分解を用いて、サンダーソン等最小二乗構成の実現可能性を示す。
  論文  参考訳（メタデータ） (2022-08-19T18:00:34Z)
• Cryptographic Hardness of Learning Halfspaces with Massart Noise [59.8587499110224]
  マスアートノイズの存在下でのPAC学習ハーフスペースの複雑さについて検討した。 我々は,最適0-1誤差が小さい場合でも,リアルタイムのMassartハーフスペース学習者が$Omega(eta)$よりも良い誤差を得られることを示す。
  論文  参考訳（メタデータ） (2022-07-28T17:50:53Z)
• Learning (Very) Simple Generative Models Is Hard [45.13248517769758]
  我々は,$mathbbRdtobbRd'$の出力座標が$mathrmpoly(d)$ニューロンを持つ一層ReLUネットワークである場合でも,リアルタイムアルゴリズムが問題を解決可能であることを示す。 我々の証明の鍵となる要素は、コンパクトに支持されたピースワイズ線形関数$f$をニューラルネットワークで束ねたスロープで構築することであり、$mathcalN(0,1)$のプッシュフォワードは$mathcalのすべての低度モーメントと一致する。
  論文  参考訳（メタデータ） (2022-05-31T17:59:09Z)
• Threshold Phenomena in Learning Halfspaces with Massart Noise [56.01192577666607]
  ガウス境界の下でのマスアートノイズ付きmathbbRd$におけるPAC学習ハーフスペースの問題について検討する。 この結果は,Massartモデルにおける学習ハーフスペースの複雑さを定性的に特徴づけるものである。
  論文  参考訳（メタデータ） (2021-08-19T16:16:48Z)
• Quantum double aspects of surface code models [77.34726150561087]
  基礎となる量子double $D(G)$対称性を持つ正方格子上でのフォールトトレラント量子コンピューティングの北エフモデルを再検討する。 有限次元ホップ代数$H$に基づいて、我々の構成がどのように$D(H)$モデルに一般化するかを示す。
  論文  参考訳（メタデータ） (2021-06-25T17:03:38Z)
• An Optimal Separation of Randomized and Quantum Query Complexity [67.19751155411075]
  すべての決定木に対して、与えられた順序 $ellsqrtbinomdell (1+log n)ell-1,$ sum to at least $cellsqrtbinomdell (1+log n)ell-1,$ where $n$ is the number of variables, $d$ is the tree depth, $c>0$ is a absolute constant。
  論文  参考訳（メタデータ） (2020-08-24T06:50:57Z)
• Quantum Lower and Upper Bounds for 2D-Grid and Dyck Language [1.0118253437732931]
  2つの問題の量子クエリ複雑性について検討する。 グリッドのエッジのいくつかが欠落している場合、グリッドグラフ上の2次元の接続問題を考える。 平衡括弧」問題をグリッドに埋め込むことで、有向2Dグリッドに対して$Omega(n1.5-epsilon)$、無向2Dグリッドに対して$Omega(n2-epsilon)$の低い境界を示す。
  論文  参考訳（メタデータ） (2020-07-06T09:51:41Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。