Fast optimization algorithms and the cosmological constant
-
1.
California Institute of Technology
-
2.
University of California, Berkeley
-
3.
Lawrence Berkeley National Laboratory
-
4.
Joint Center for Quantum Information and Computer Science
-
5.
National Institute of Standards and Technology
-
6.
University of Maryland, College Park
-
7.
National Security Agency
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.
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.Attached Files
Published - PhysRevD.96.103512.pdf
Submitted - 1706.08503.pdf
Files
1706.08503.pdf
Additional details
Identifiers
- Eprint ID
- 83204
- Resolver ID
- CaltechAUTHORS:20171114-150959412
Related works
- Describes
- https://arxiv.org/abs/1706.08503 (URL)
Funding
- Lee A. DuBridge Foundation
- Berkeley Center for Theoretical Physics
- NSF
- PHY-1521446
- NSF
- PHY-1316783
- Foundational Questions Institute (FQXi)
- Department of Energy (DOE)
- DE-AC02-05CH11231
Dates
- Created
-
2017-11-14Created from EPrint's datestamp field
- Updated
-
2021-11-15Created from EPrint's last_modified field