Fast optimization algorithms and the cosmological constant

Abstract

Denef and Douglas have observed that in certain landscape models the problem of finding small values of the cosmological constant is a large instance of an NP-hard problem. The number of elementary operations (quantum gates) needed to solve this problem by brute force search exceeds the estimated computational capacity of the observable universe. Here we describe a way out of this puzzling circumstance: despite being NP-hard, the problem of finding a small cosmological constant can be attacked by more sophisticated algorithms whose performance vastly exceeds brute force search. In fact, in some parameter regimes the average-case complexity is polynomial. We demonstrate this by explicitly finding a cosmological constant of order $10^{-120}$ in a randomly generated $10^9$-dimensional ADK landscape.

19 pages, 5 figures

References in corpus (35)

• Observational Evidence from Supernovae for an Accelerating Universe and a Cosmological Constant
• Measurements of Omega and Lambda from 42 High-Redshift Supernovae
• Planck 2015 results. XIII. Cosmological parameters
• de Sitter Vacua in String Theory
• Quantization of Four-form Fluxes and Dynamical Neutralization of the Cosmological Constant
• A Covariant Entropy Conjecture
• Flux Compactification
• Quantum Networks for Elementary Arithmetic Operations
• Complexity, action, and black holes
• Computational capacity of the universe
• Holography in General Space-times
• A new quantum ripple-carry addition circuit
• What is the Computational Value of Finite Range Tunneling?
• Positive vacuum energy and the N-bound
• Nonlinear quantum mechanics implies polynomial-time solution for NP-complete and #P problems
• Quantum Computation vs. Firewalls
• Phase Transition in the Number Partitioning Problem
• Addition on a Quantum Computer
• TASI Lectures on the Cosmological Constant
• The Cosmological Constant and the String Landscape
• NP-complete Problems and Physical Reality
• Computational complexity of the landscape I
• The Multiverse Interpretation of Quantum Mechanics
• Predicting the Cosmological Constant from the Causal Entropic Principle
• Random Costs in Combinatorial Optimization
• Can closed timelike curves or nonlinear quantum mechanics improve quantum state discrimination or help solve hard problems?
• Complementarity in the Multiverse
• Predictive Landscapes and New Physics at a TeV
• Number partitioning as random energy model
• A geometric solution to the coincidence problem, and the size of the landscape as the origin of hierarchy
• Analysis of the Karmarkar-Karp Differencing Algorithm
• Grover search and the no-signaling principle
• Closed Timelike Curves Make Quantum and Classical Computing Equivalent
• Rescuing Complementarity With Little Drama
• Simulations of closed timelike curves

Cited by in corpus (16)

• Small Cosmological Constants in String Theory
• Searching the Landscape of Flux Vacua with Genetic Algorithms
• Computational Complexity of Vacua and Near-Vacua in Field and String Theory
• Estimating Calabi-Yau Hypersurface and Triangulation Counts with Equation Learners
• Search Optimization, Funnel Topography, and Dynamical Criticality on the String Landscape
• Accessibility Measure for Eternal Inflation: Dynamical Criticality and Higgs Metastability
• Revealing systematics in phenomenologically viable flux vacua with reinforcement learning
• Artificial Neural Network in Cosmic Landscape
• Early-Time Measure in Eternal Inflation
• Kahler Moduli Stabilization and the Propagation of Decidability
• Energy stored on a cosmological horizon and its thermodynamic fluctuations in holographic equipartition law
• Near-horizon symmetries of the Schwarzschild black hole with supertranslation field
• Dark Horse, Dark Matter: Revisiting the SO(16)x SO(16)' Nonsupersymmetric Model in the LHC and Dark Energy Era
• Topological Data Analysis for the String Landscape
• Cosmological scenario based on the first and second laws of thermodynamics: Thermodynamic constraints on a generalized cosmological model
• Probing the Structure of String Theory Vacua with Genetic Algorithms and Reinforcement Learning