論文の概要: Discrete Bulk Reconstruction
- arxiv url: http://arxiv.org/abs/2210.15601v2
- Date: Sun, 6 Nov 2022 21:48:33 GMT
- ステータス: 処理完了
- システム内更新日: 2023-01-21 08:05:00.231676
- Title: Discrete Bulk Reconstruction
- Title（参考訳）: 離散バルク再構成
- Authors: Scott Aaronson and Jason Pollack
- Abstract要約: ブラックホールの内部などの領域を再構築したい場合,AdS/CFTは指数関数的に複雑であることを示す。
また,複数の1次元境界がワームホールを介して接続される場合にも,初期進行が見られた。
- 参考スコア（独自算出の注目度）: 4.467248776406005
- License: http://creativecommons.org/licenses/by-nc-sa/4.0/
- Abstract: According to the AdS/CFT correspondence, the geometries of certain spacetimes
are fully determined by quantum states that live on their boundaries -- indeed,
by the von Neumann entropies of portions of those boundary states. This work
investigates to what extent the geometries can be reconstructed from the
entropies in polynomial time. Bouland, Fefferman, and Vazirani (2019) argued
that the AdS/CFT map can be exponentially complex if one wants to reconstruct
regions such as the interiors of black holes. Our main result provides a sort
of converse: we show that, in the special case of a single 1D boundary, if the
input data consists of a list of entropies of contiguous boundary regions, and
if the entropies satisfy a single inequality called Strong Subadditivity, then
we can construct a graph model for the bulk in linear time. Moreover, the bulk
graph is planar, it has $O(N^2)$ vertices (the information-theoretic minimum),
and it's ``universal,'' with only the edge weights depending on the specific
entropies in question. From a combinatorial perspective, our problem boils down
to an ``inverse'' of the famous min-cut problem: rather than being given a
graph and asked to find a min-cut, here we're given the values of min-cuts
separating various sets of vertices, and need to find a weighted undirected
graph consistent with those values. Our solution to this problem relies on the
notion of a ``bulkless'' graph, which might be of independent interest for
AdS/CFT. We also make initial progress on the case of multiple 1D boundaries --
where the boundaries could be connected via wormholes -- including an upper
bound of $O(N^4)$ vertices whenever a planar bulk graph exists (thus putting
the problem into the complexity class $\mathsf{NP}$).
- Abstract（参考訳）: ads/cft対応によれば、ある時空の幾何学は、その境界上に存在する量子状態によって完全に決定され、実際、これらの境界状態の一部のフォン・ノイマンのエントロピーによって決定される。
この研究は、多項式時間におけるエントロピーから測地がどの程度再構成できるかを調査する。
Bouland, Fefferman, Vazirani (2019) は、ブラックホールの内部のような領域を再構築したい場合、AdS/CFTマップは指数関数的に複雑になると主張した。
一つの1次元境界の特別な場合、入力データが連続した境界領域のエントロピーのリストで構成され、エントロピーが強い部分加法的と呼ばれる単一の不等式を満たすならば、線形時間でバルクのグラフモデルを構築することができる。
さらに、バルクグラフは平面であり、$O(N^2)$ vertices (情報理論の最小値)を持ち、それは'universal' であり、問題の特定のエントロピーに依存するエッジウェイトのみである。
組み合わせの観点からすると、我々の問題は有名なミンカット問題の 'inverse'' に端を発する: グラフを与えてミンカットを見つける代わりに、ミンカットの値が様々な頂点の集合を分離し、それらの値と整合した重み付けのないグラフを見つける必要がある。
この問題に対する我々の解決策は ``bulkless'' グラフの概念に依存しており、ads/cft には独立した関心があるかもしれない。
また、平面バルクグラフが存在するとき、その問題を複雑性クラス$\mathsf{NP}$に置けば、その上界の$O(N^4)$頂点を含む、複数の1D境界がワームホールを介して接続できるような場合の初期進行も行う。
関連論文リスト
- Information-Theoretic Thresholds for Planted Dense Cycles [52.076657911275525]
本研究では,社会科学や生物科学においてユビキタスな小世界ネットワークのランダムグラフモデルについて検討する。
植え込み高密度サイクルの検出と回復の両面において、情報理論の閾値を$n$, $tau$、エッジワイド信号対雑音比$lambda$で特徴づける。
論文 参考訳（メタデータ） (2024-02-01T03:39:01Z) - Gaussian Entanglement Measure: Applications to Multipartite Entanglement
of Graph States and Bosonic Field Theory [50.24983453990065]
フービニ・スタディ計量に基づく絡み合い尺度は、Cocchiarellaと同僚によって最近導入された。
本稿では,多モードガウス状態に対する幾何絡み合いの一般化であるガウスエンタングルメント尺度(GEM)を提案する。
自由度の高い系に対する計算可能な多部絡み合わせ測度を提供することにより、自由なボゾン場理論の洞察を得るために、我々の定義が利用できることを示す。
論文 参考訳（メタデータ） (2024-01-31T15:50:50Z) - Quantum computing algorithms for inverse problems on graphs and an
NP-complete inverse problem [2.107421958337625]
有限グラフ $(X,E)$ に対する逆問題を考える。
この問題には特定の条件下でのユニークな解法があることを示し、量子計算法を開発した。
論文 参考訳（メタデータ） (2023-06-08T14:48:48Z) - Planted Bipartite Graph Detection [13.95780443241133]
ランダムグラフに隠れた二部グラフを検出するタスクについて検討する。
ヌル仮説の下では、このグラフは、エッジ密度$q$の$n$上のアードホスラーイランダムグラフの実現である。
k_mathsfR times k_mathsfL$ bipartite subgraph with edge density $p>q$。
論文 参考訳（メタデータ） (2023-02-07T18:18:17Z) - Efficient Graph Field Integrators Meet Point Clouds [59.27295475120132]
点雲を符号化するグラフ上での効率的な場積分のためのアルゴリズムを2種類提案する。
第1のクラスであるSeparatorFactorization(SF)は、ポイントメッシュグラフの有界属を利用するが、第2のクラスであるRFDiffusion(RFD)は、ポイントクラウドの一般的なepsilon-nearest-neighborグラフ表現を使用する。
論文 参考訳（メタデータ） (2023-02-02T08:33:36Z) - Near-optimal fitting of ellipsoids to random points [68.12685213894112]
楕円体をランダムな点に合わせるという基本的な問題は、低ランク行列分解、独立成分分析、主成分分析に関係している。
我々はこの予想を、ある$n = Omega(, d2/mathrmpolylog(d))$ に対する適合楕円体を構成することで対数的因子まで解決する。
我々の証明は、ある非標準確率行列の便利な分解を用いて、サンダーソン等最小二乗構成の実現可能性を示す。
論文 参考訳（メタデータ） (2022-08-19T18:00:34Z) - Graph Neural Network Bandits [89.31889875864599]
グラフ構造データ上で定義された報酬関数を用いた帯域最適化問題を考察する。
この設定の主な課題は、大きなドメインへのスケーリングと、多くのノードを持つグラフへのスケーリングである。
グラフニューラルネットワーク(GNN)を用いて報酬関数を推定できることを示す。
論文 参考訳（メタデータ） (2022-07-13T18:12:36Z) - Shortest Paths in Graphs with Matrix-Valued Edges: Concepts, Algorithm
and Application to 3D Multi-Shape Analysis [69.08838724594584]
グラフ内の最短経路を見つけることは、コンピュータビジョンやグラフィックスにおける多くの問題に関係している。
本稿では,行列値のエッジを持つグラフにおいて,最短経路のグラフ理論を新たに導入する。
論文 参考訳（メタデータ） (2021-12-08T08:23:37Z) - Inferring Hidden Structures in Random Graphs [13.031167737538881]
本研究では,ランダムなグラフ上に植えられた群集群集の検出と復元の2つの推論問題について検討する。
我々は、パラメータ $(n,k,q)$ や $Gamma_k$ の特定の性質の観点から、構造を検出・復元するための下限を導出し、これらの下限を達成するための計算学的に最適なアルゴリズムを示す。
論文 参考訳（メタデータ） (2021-10-05T09:39:51Z) - Improved Reconstruction of Random Geometric Graphs [3.930410971186142]
ランダムな幾何グラフの古典的モデルを考えると、$n$の点が一様に領域$n$の正方形に散らばっている。
グラフ距離と近距離推定のハイブリッドを用いてユークリッド距離を推定する。
本手法は, グラフ距離と近辺点数に基づく短距離推定のハイブリッドを用いてユークリッド距離を推定する。
論文 参考訳（メタデータ） (2021-07-29T20:37:28Z) - Settling the Sharp Reconstruction Thresholds of Random Graph Matching [19.54246087326288]
2つのエッジ関連ランダムグラフ間の隠れた対応を復元する問題について検討する。
p=n-o(1)$のグラフに対して、鋭いしきい値が存在することが証明される。
sparse ErdHos-R'enyi graphs with $p=n-Theta(1)$ に対して、オール・オー・ナッシング現象はもはや成り立たないことを示す。
論文 参考訳（メタデータ） (2021-01-29T21:49:50Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。