Uncomputably Complex Renormalisation Group Flows

• URL: http://arxiv.org/abs/2102.05145v1
• Date: Tue, 9 Feb 2021 21:46:55 GMT
• Title: Uncomputably Complex Renormalisation Group Flows
• Authors: James D. Watson, Emilio Onorati, Toby S. Cubitt
• Abstract summary: We show that important physical properties of quantum many-body systems, such as its spectral gap and phase diagram, can be uncomputable. The structure of such uncomputable RG flows is so complex that it cannot be computed or approximated, even in principle.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Renormalisation group (RG) methods provide one of the most important techniques for analysing the physics of many-body systems, both analytically and numerically. By iterating an RG map, which "course-grains" the description of a many-body system and generates a flow in the parameter space, physical properties of interest can be extracted even for complex models. RG analysis also provides an explanation of physical phenomena such as universality. Many systems exhibit simple RG flows, but more complicated -- even chaotic -- behaviour is also known. Nonetheless, the structure of such RG flows can still be analysed, elucidating the physics of the system, even if specific trajectories may be highly sensitive to the initial point. In contrast, recent work has shown that important physical properties of quantum many-body systems, such as its spectral gap and phase diagram, can be uncomputable. In this work, we show that such undecidable systems exhibit a novel type of RG flow, revealing a qualitatively different and more extreme form of unpredictability than chaotic RG flows. In contrast to chaotic RG flows in which initially close points can diverge exponentially, trajectories under these novel uncomputable RG flows can remain arbitrarily close together for an uncomputable number of iterations, before abruptly diverging to different fixed points that are in separate phases. The structure of such uncomputable RG flows is so complex that it cannot be computed or approximated, even in principle. We give a mathematically rigorous construction of the block-renormalisation-group map for the original undecidable many-body system that appeared in the literature (Cubitt, P\'erez-Garcia, Wolf, Nature 528, 207-211 (2015)). We prove that each step of this RG map is computable, and that it converges to the correct fixed points, yet the resulting RG flow is uncomputable.

Related papers

• Wilsonian Renormalization of Neural Network Gaussian Processes [1.8749305679160366]
  We demonstrate a practical approach to performing Wilsonian RG in the context of Gaussian Process (GP) Regression. We systematically integrate out the unlearnable modes of the GP kernel, thereby obtaining an RG flow of the GP in which the data sets the IR scale. This approach goes beyond structural analogies between RG and neural networks by providing a natural connection between RG flow and learnable vs. unlearnable modes.
  arXiv  Detail & Related papers  (2024-05-09T18:00:00Z)
• Renormalized Graph Neural Networks [4.200261123369236]
  Graph Neural Networks (GNNs) have become essential for studying complex data, particularly when represented as graphs. This paper proposes a new approach that applies renormalization group theory to improve GNNs' performance on graph-related tasks.
  arXiv  Detail & Related papers  (2023-06-01T14:16:43Z)
• DynGFN: Towards Bayesian Inference of Gene Regulatory Networks with GFlowNets [81.75973217676986]
  Gene regulatory networks (GRN) describe interactions between genes and their products that control gene expression and cellular function. Existing methods either focus on challenge (1), identifying cyclic structure from dynamics, or on challenge (2) learning complex Bayesian posteriors over DAGs, but not both. In this paper we leverage the fact that it is possible to estimate the "velocity" of gene expression with RNA velocity techniques to develop an approach that addresses both challenges.
  arXiv  Detail & Related papers  (2023-02-08T16:36:40Z)
• Wavelet Conditional Renormalization Group [7.775545390766461]
  We develop a multiscale approach to estimate high-dimensional probability distributions from a dataset of physical fields or configurations observed in experiments or simulations. Our method -- the Wavelet Conditional Renormalization Group (WC-RG) -- proceeds scale by scale, estimating models for the conditional probabilities of "fast degrees of freedom" conditioned by coarse-grained fields.
  arXiv  Detail & Related papers  (2022-07-11T15:18:08Z)
• Simple and Efficient Heterogeneous Graph Neural Network [55.56564522532328]
  Heterogeneous graph neural networks (HGNNs) have powerful capability to embed rich structural and semantic information of a heterogeneous graph into node representations. Existing HGNNs inherit many mechanisms from graph neural networks (GNNs) over homogeneous graphs, especially the attention mechanism and the multi-layer structure. This paper conducts an in-depth and detailed study of these mechanisms and proposes Simple and Efficient Heterogeneous Graph Neural Network (SeHGNN)
  arXiv  Detail & Related papers  (2022-07-06T10:01:46Z)
• Deep Architecture Connectivity Matters for Its Convergence: A Fine-Grained Analysis [94.64007376939735]
  We theoretically characterize the impact of connectivity patterns on the convergence of deep neural networks (DNNs) under gradient descent training. We show that by a simple filtration on "unpromising" connectivity patterns, we can trim down the number of models to evaluate.
  arXiv  Detail & Related papers  (2022-05-11T17:43:54Z)
• Categorical Representation Learning and RG flow operators for algorithmic classifiers [0.7519268719195278]
  We construct a new natural language processing architecture, called the RG-flow categorifier or for short the RG categorifier, which is capable of data classification and generation in all layers. In particular we apply the RG categorifier to particular genomic sequences of flu viruses and show how our technology is capable of extracting information from given genomic sequences.
  arXiv  Detail & Related papers  (2022-03-15T15:04:51Z)
• Dist2Cycle: A Simplicial Neural Network for Homology Localization [66.15805004725809]
  Simplicial complexes can be viewed as high dimensional generalizations of graphs that explicitly encode multi-way ordered relations. We propose a graph convolutional model for learning functions parametrized by the $k$-homological features of simplicial complexes.
  arXiv  Detail & Related papers  (2021-10-28T14:59:41Z)
• Fractal Structure and Generalization Properties of Stochastic Optimization Algorithms [71.62575565990502]
  We prove that the generalization error of an optimization algorithm can be bounded on the complexity' of the fractal structure that underlies its generalization measure. We further specialize our results to specific problems (e.g., linear/logistic regression, one hidden/layered neural networks) and algorithms.
  arXiv  Detail & Related papers  (2021-06-09T08:05:36Z)
• Performance of the rigorous renormalization group for first order phase transitions and topological phases [0.0]
  The density matrix renormalization group (DMRG) has been established as a practically useful algorithm for finding the ground state in 1D systems. We study the accuracy and performance of a numerical implementation of RRG at first order phase transitions and in symmetry protected topological phases.
  arXiv  Detail & Related papers  (2020-10-29T18:00:07Z)
• AM-GCN: Adaptive Multi-channel Graph Convolutional Networks [85.0332394224503]
  We study whether Graph Convolutional Networks (GCNs) can optimally integrate node features and topological structures in a complex graph with rich information. We propose an adaptive multi-channel graph convolutional networks for semi-supervised classification (AM-GCN) Our experiments show that AM-GCN extracts the most correlated information from both node features and topological structures substantially.
  arXiv  Detail & Related papers  (2020-07-05T08:16:03Z)

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.