A Caltech Library Service

Fast optimization algorithms and the cosmological constant

Bao, Ning and Bousso, Raphael and Jordan, Stephen and Lackey, Brad (2017) Fast optimization algorithms and the cosmological constant. Physical Review D, 96 (10). Art. No. 103512. ISSN 2470-0010. doi:10.1103/PhysRevD.96.103512.

[img] PDF - Published Version
See Usage Policy.

[img] PDF - Submitted Version
See Usage Policy.


Use this Persistent URL to link to this item:


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 a problem that is hard for the complexity class NP (Nondeterministic Polynomial-time). 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 Arkani-Hamed–Dimopoulos–Kachru landscape.

Item Type:Article
Related URLs:
URLURL TypeDescription Paper
Bao, Ning0000-0002-3296-1039
Additional Information:© 2017 American Physical Society. Received 27 July 2017; published 13 November 2017. We would like to thank Scott Aaronson, Adam Bouland, and Liam McAllister for discussions. N. B. is supported in part by the DuBridge Fellowship of the Walter Burke Institute for Theoretical Physics. R. B. is supported in part by the Berkeley Center for Theoretical Physics, by the National Science Foundation (Grants No. PHY-1521446 and No. PHY-1316783), by FQXi, and by the U.S. Department of Energy under Contract No. DE-AC02-05CH11231. S. J. and B. L. thank U. Maryland for use of the Deepthought2 high performance computing cluster. Parts of this manuscript are a contribution of NIST, an agency of the U.S. government, and are not subject to U.S. copyright.
Group:Institute for Quantum Information and Matter, Walter Burke Institute for Theoretical Physics
Funding AgencyGrant Number
Lee A. DuBridge FoundationUNSPECIFIED
Berkeley Center for Theoretical PhysicsUNSPECIFIED
Foundational Questions Institute (FQXi)UNSPECIFIED
Department of Energy (DOE)DE-AC02-05CH11231
Issue or Number:10
Record Number:CaltechAUTHORS:20171114-150959412
Persistent URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:83204
Deposited By: Tony Diaz
Deposited On:14 Nov 2017 23:16
Last Modified:15 Nov 2021 19:56

Repository Staff Only: item control page