CaltechAUTHORS
  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. http://resolver.caltech.edu/CaltechAUTHORS:20171114-150959412

[img] PDF - Published Version
See Usage Policy.

461Kb
[img] PDF - Submitted Version
See Usage Policy.

329Kb

Use this Persistent URL to link to this item: http://resolver.caltech.edu/CaltechAUTHORS:20171114-150959412

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 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
https://doi.org/10.1103/PhysRevD.96.103512DOIArticle
https://journals.aps.org/prd/abstract/10.1103/PhysRevD.96.103512PublisherArticle
https://arxiv.org/abs/1706.08503arXivDiscussion Paper
ORCID:
AuthorORCID
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:IQIM, Institute for Quantum Information and Matter, Walter Burke Institute for Theoretical Physics
Funders:
Funding AgencyGrant Number
Lee A. DuBridge FoundationUNSPECIFIED
Berkeley Center for Theoretical PhysicsUNSPECIFIED
NSFPHY-1521446
NSFPHY-1316783
Foundational Questions Institute (FQXi)UNSPECIFIED
Department of Energy (DOE)DE-AC02-05CH11231
Record Number:CaltechAUTHORS:20171114-150959412
Persistent URL:http://resolver.caltech.edu/CaltechAUTHORS:20171114-150959412
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:83204
Collection:CaltechAUTHORS
Deposited By: Tony Diaz
Deposited On:14 Nov 2017 23:16
Last Modified:14 Nov 2017 23:16

Repository Staff Only: item control page