In this dissertation we study the tractability of the information-based complexity n(ε,d) for d-variate function approximation problems. In the deterministic setting for many unweighted problems the curse of dimensionality holds, that means, for some fixed error tolerance ε>0 the complexity n(ε,d) grows exponentially in d. For integration problems one can usually break the curse with the standard Monte Carlo method. For function approximation problems, however, similar effects of randomization have been unknown so far. The thesis contains results on three more or less stand-alone topics. For an extended five page abstract, see the section "Introduction and Results". Chapter 2 is concerned with lower bounds for the Monte Carlo error for general linear problems via Bernstein numbers. This technique is applied to the L∞-approximation of certain classes of C∞-functions, where it turns out that randomization does not affect the tractability classification of the problem. Chapter 3 studies the L∞-approximation of functions from Hilbert spaces with methods that may use arbitrary linear functionals as information. For certain classes of periodic functions from unweighted periodic tensor product spaces, in particular Korobov spaces, we observe the curse of dimensionality in the deterministic setting, while with randomized methods we achieve polynomial tractability. Chapter 4 deals with the L1-approximation of monotone functions via function values. It is known that this problem suffers from the curse in the deterministic setting. An improved lower bound shows that the problem is still intractable in the randomized setting. However, Monte Carlo breaks the curse, in detail, for any fixed error tolerance ε>0 the complexity n(ε,d) grows exponentially in d only.
The convergence of full configuration interaction quantum Monte Carlo (FCIQMC) is accelerated using a quasi-Newton propagation (QN) which can also be applied to coupled cluster Monte Carlo (CCMC). The computational scaling of this optimized propagation is, keeping the additional computational cost to a bare minimum. Its effects are investigated deterministically and stochastically on a model system, the uniform electron gas, with Hilbert space size up to 10 40, and shown to accelerate convergence of the instantaneous projected energy by over an order of magnitude in the FCIQMC test case. Its capabilities are then demonstrated with FCIQMC on an archetypical quantum chemistry problem, the chromium dimer, in an all-electron basis set with Hilbert space size of about 10 22 yielding highly accurate FCI energies.
We study non-linear bandit optimization where the learner maximizes a black-box function with zeroth order function oracle, which has been successfully applied in many critical applications such as drug discovery and materials design. Existing works have showed that with the aid of quantum computing, it is possible to break the classical Ω(T) regret lower bound and achieve the new O(polylogT) upper bound. However, they usually assume that the objective function sits within the reproducing kernel Hilbert space and their algorithms suffer from the curse of dimensionality. In this paper, we propose the new Q-NLB-UCB algorithm which enjoys an \emph{input dimension-free} O(polylogT) upper bound, making it applicable for high-dimensional tasks. At the heart of our algorithm design are quantum Monte Carlo mean estimator, parametric function approximation technique, and a new quantum non-linear regression oracle, which can be of independent interests in more quantum machine learning problems. Our algorithm is also validated for its efficiency compared with other quantum algorithms on both high-dimensional synthetic and real-world tasks.