Discrete Bulk Reconstruction
- URL: http://arxiv.org/abs/2210.15601v2
- Date: Sun, 6 Nov 2022 21:48:33 GMT
- Title: Discrete Bulk Reconstruction
- Authors: Scott Aaronson and Jason Pollack
- Abstract summary: We show that the AdS/CFT can be exponentially complex if one wants to reconstruct regions such as the interiors of black holes.
We also make initial progress on the case of multiple 1D boundaries, where the boundaries could be connected via wormholes.
- Score: 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}$).
Related papers
- Information-Theoretic Thresholds for Planted Dense Cycles [52.076657911275525]
We study a random graph model for small-world networks which are ubiquitous in social and biological sciences.
For both detection and recovery of the planted dense cycle, we characterize the information-theoretic thresholds in terms of $n$, $tau$, and an edge-wise signal-to-noise ratio $lambda$.
arXiv Detail & Related papers (2024-02-01T03:39:01Z) - Gaussian Entanglement Measure: Applications to Multipartite Entanglement
of Graph States and Bosonic Field Theory [50.24983453990065]
An entanglement measure based on the Fubini-Study metric has been recently introduced by Cocchiarella and co-workers.
We present the Gaussian Entanglement Measure (GEM), a generalization of geometric entanglement measure for multimode Gaussian states.
By providing a computable multipartite entanglement measure for systems with a large number of degrees of freedom, we show that our definition can be used to obtain insights into a free bosonic field theory.
arXiv Detail & Related papers (2024-01-31T15:50:50Z) - Quantum computing algorithms for inverse problems on graphs and an
NP-complete inverse problem [2.107421958337625]
We consider an inverse problem for a finite graph $(X,E)$ where we are given a subset of vertices.
We show that this problem has unique solution under certain conditions and develop quantum computing methods to solve it.
arXiv Detail & Related papers (2023-06-08T14:48:48Z) - Planted Bipartite Graph Detection [13.95780443241133]
We consider the task of detecting a hidden bipartite subgraph in a given random graph.
Under the null hypothesis, the graph is a realization of an ErdHosR'enyi random graph over $n$ with edge density $q$.
Under the alternative, there exists a planted $k_mathsfR times k_mathsfL$ bipartite subgraph with edge density $p>q$.
arXiv Detail & Related papers (2023-02-07T18:18:17Z) - Efficient Graph Field Integrators Meet Point Clouds [59.27295475120132]
We present two new classes of algorithms for efficient field integration on graphs encoding point clouds.
The first class, SeparatorFactorization(SF), leverages the bounded genus of point cloud mesh graphs, while the second class, RFDiffusion(RFD), uses popular epsilon-nearest-neighbor graph representations for point clouds.
arXiv Detail & Related papers (2023-02-02T08:33:36Z) - Near-optimal fitting of ellipsoids to random points [68.12685213894112]
A basic problem of fitting an ellipsoid to random points has connections to low-rank matrix decompositions, independent component analysis, and principal component analysis.
We resolve this conjecture up to logarithmic factors by constructing a fitting ellipsoid for some $n = Omega(, d2/mathrmpolylog(d),)$.
Our proof demonstrates feasibility of the least squares construction of Saunderson et al. using a convenient decomposition of a certain non-standard random matrix.
arXiv Detail & Related papers (2022-08-19T18:00:34Z) - Graph Neural Network Bandits [89.31889875864599]
We consider the bandit optimization problem with the reward function defined over graph-structured data.
Key challenges in this setting are scaling to large domains, and to graphs with many nodes.
We show that graph neural networks (GNNs) can be used to estimate the reward function.
arXiv Detail & Related papers (2022-07-13T18:12:36Z) - Shortest Paths in Graphs with Matrix-Valued Edges: Concepts, Algorithm
and Application to 3D Multi-Shape Analysis [69.08838724594584]
Finding shortest paths in a graph is relevant for numerous problems in computer vision and graphics.
We introduce the novel graph-theoretic concept of a shortest path in a graph with matrix-valued edges.
arXiv Detail & Related papers (2021-12-08T08:23:37Z) - Inferring Hidden Structures in Random Graphs [13.031167737538881]
We study the two inference problems of detecting and recovering an isolated community of emphgeneral structure planted in a random graph.
We derive lower bounds for detecting/recovering the structure $Gamma_k$ in terms of the parameters $(n,k,q)$, as well as certain properties of $Gamma_k$, and exhibit computationally optimal algorithms that achieve these lower bounds.
arXiv Detail & Related papers (2021-10-05T09:39:51Z) - Improved Reconstruction of Random Geometric Graphs [3.930410971186142]
We consider the classic model of random geometric graphs where $n$ points are scattered uniformly in a square of area $n$.
We use a hybrid of graph distances and short-range estimates based on the number of common neighbors to estimate Euclidean distances.
Our method estimates Euclidean distances using a hybrid of graph distances and short-range estimates based on the number of common neighbors.
arXiv Detail & Related papers (2021-07-29T20:37:28Z) - Settling the Sharp Reconstruction Thresholds of Random Graph Matching [19.54246087326288]
We study the problem of recovering the hidden correspondence between two edge-correlated random graphs.
For dense graphs with $p=n-o(1)$, we prove that there exists a sharp threshold.
For sparse ErdHos-R'enyi graphs with $p=n-Theta(1)$, we show that the all-or-nothing phenomenon no longer holds.
arXiv Detail & Related papers (2021-01-29T21:49:50Z)
This list is automatically generated from the titles and abstracts of the papers in this site.
This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.