@article {1991, title = {Fast optimization algorithms and the cosmological constant}, journal = {Physical Review D}, volume = {96}, year = {2017}, month = {2017/11/13}, pages = {103512}, 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 109 -dimensional ADK landscape.

}, doi = {10.1103/PhysRevD.96.103512}, url = {https://arxiv.org/abs/1706.08503}, author = {Ning Bao and Raphael Bousso and Stephen P. Jordan and Brad Lackey} } @article {1948, title = {Fast quantum computation at arbitrarily low energy}, journal = {Physical Review A}, volume = {95}, year = {2017}, month = {2017/03/06}, pages = {032305}, abstract = {

One version of the energy-time uncertainty principle states that the minimum time\ T\⊥\ for a quantum system to evolve from a given state to any orthogonal state is\ h/(4ΔE), where\ ΔE\ is the energy uncertainty. A related bound called the Margolus-Levitin theorem states that\ T\⊥\≥h/(2\⟨E\⟩), where\ \⟨E\⟩\ is the expectation value of energy and the ground energy is taken to be zero. Many subsequent works have interpreted\ T\⊥\ as defining a minimal time for an elementary computational operation and correspondingly a fundamental limit on clock speed determined by a system\&$\#$39;s energy. Here we present local time-independent Hamiltonians in which computational clock speed becomes arbitrarily large relative to\ \⟨E\⟩\ and\ ΔE\ as the number of computational steps goes to infinity. We argue that energy considerations alone are not sufficient to obtain an upper bound on computational speed, and that additional physical assumptions such as limits to information density and information transmission speed are necessary to obtain such a bound.

}, doi = {10.1103/PhysRevA.95.032305}, url = {http://link.aps.org/doi/10.1103/PhysRevA.95.032305}, author = {Stephen P. Jordan} } @article {1389, title = {The Fundamental Gap for a Class of Schr{\"o}dinger Operators on Path and Hypercube Graphs}, journal = {Journal of Mathematical Physics}, volume = {55}, year = {2014}, month = {2014/03/06}, pages = {052104}, abstract = { We consider the difference between the two lowest eigenvalues (the fundamental gap) of a Schr\"{o}dinger operator acting on a class of graphs. In particular, we derive tight bounds for the gap of Schr\"{o}dinger operators with convex potentials acting on the path graph. Additionally, for the hypercube graph, we derive a tight bound for the gap of Schr\"{o}dinger operators with convex potentials dependent only upon vertex Hamming weight. Our proof makes use of tools from the literature of the fundamental gap theorem as proved in the continuum combined with techniques unique to the discrete case. We prove the tight bound for the hypercube graph as a corollary to our path graph results. }, doi = {10.1063/1.4878120}, url = {http://arxiv.org/abs/1403.1473v1}, author = {Michael Jarret and Stephen P. Jordan} } @article {1379, title = {Fast quantum algorithms for approximating some irreducible representations of groups }, year = {2008}, month = {2008/11/04}, abstract = { We consider the quantum complexity of estimating matrix elements of unitary irreducible representations of groups. For several finite groups including the symmetric group, quantum Fourier transforms yield efficient solutions to this problem. Furthermore, quantum Schur transforms yield efficient solutions for certain irreducible representations of the unitary group. Beyond this, we obtain poly(n)-time quantum algorithms for approximating matrix elements from all the irreducible representations of the alternating group A_n, and all the irreducible representations of polynomial highest weight of U(n), SU(n), and SO(n). These quantum algorithms offer exponential speedup in worst case complexity over the fastest known classical algorithms. On the other hand, we show that average case instances are classically easy, and that the techniques analyzed here do not offer a speedup over classical computation for the estimation of group characters. }, url = {http://arxiv.org/abs/0811.0562v2}, author = {Stephen P. Jordan} } @article {1377, title = {Fast quantum algorithm for numerical gradient estimation}, journal = {Physical Review Letters}, volume = {95}, year = {2005}, month = {2005/7/28}, abstract = { Given a blackbox for f, a smooth real scalar function of d real variables, one wants to estimate the gradient of f at a given point with n bits of precision. On a classical computer this requires a minimum of d+1 blackbox queries, whereas on a quantum computer it requires only one query regardless of d. The number of bits of precision to which f must be evaluated matches the classical requirement in the limit of large n. }, doi = {10.1103/PhysRevLett.95.050501}, url = {http://arxiv.org/abs/quant-ph/0405146v2}, author = {Stephen P. Jordan} }