Quantum integration in Sobolev classes

We study high-dimensional integration in the quantum model of computation. We develop quantum algorithms for integration of functions from Sobolev classes W_p^r([0,1]^d) and analyze their convergence rates. We also prove lower bounds which show that the proposed algorithms are, in many cases, optimal within the setting of quantum computing. This extends recent results of Novak on integration of functions from Hölder classes.     

On a problem in quantum summation

We consider the computation of the mean of sequences in the quantum model of computation. We determine the query complexity in the case of sequences which satisfy a p-summability condition for 1⩽p<2. This settles a problem left open in Heinrich (J. Complexity 18 (2002) 1).     

The Real Number Model in Numerical Analysis

In the real number model of computation one assumes that arithmetic operations with real numbers and comparisons can be done with unit cost. In numerical analysis one often deals with problems where the information is only partial. This is an essential assumption for problems defined on function spaces, such as numerical integration, zero finding, or optimization. For such problems we must usually deal with partial information consisting of function values or Fourier coefficients, because a digital computer can only handle finite sets of numbers instead of functions. In information-based complexity it is assumed that certain functionals can be evaluated by an oracle and each call of the oracle costs c, where c > 0. In this paper we describe this model of computation more carefully. We also define two variants of stochastic (or Monte Carlo) algorithms. We believe that the results of information-based complexity, see the book of Traub, Wasilkowski, and Woźniakowski (1988, "Information-Based Complexity," Academic Press, New York/London), can be reconstructed in our model with only minor changes. As an example we present a "uniform algorithm" for a "uniform problem" in numerical integration. We compare our model (in the case, where no oracle is used) with the model of Blum, Shub, and Smale (1989, Bull. Amer. Math. Soc.21, 1-46). These authors use a different cost function. Copy instructions are rather expensive in their model, while they are for free in our model. In spite of this difference we show that the sets P and NP coincide with respect to both cost functions.     

Quantum complexity of the approximation for the classes B(Wp ([0, 1])) and B(Hp ([0, 1]))

We study the approximation of functions from anisotropic Sobolev classes B(W^r_p([0,1]d)) and Hölder-Nikolskii classes B(H^r_p([0,1]d)) in the L_q([0,1]d) norm with q ≤ p in the quantum model of computation. We determine the quantum query complexity of this problem up to logarithmic factors. It shows that the quantum algorithms are significantly better than the classical deterministic or randomized algorithms.     

Quantum complexity of parametric integration

We study parametric integration of functions from the class C^r([0,1]^d₁+d₂) to C([0,1]^d₁) in the quantum model of computation. We analyze the convergence rate of parametric integration in this model and show that it is always faster than the optimal deterministic rate and in some cases faster than the rate of optimal randomized classical algorithms.     

Tractability and Strong Tractability of Linear Multivariate Problems

Linear multivariate problems are defined as the approximation of linear operators on functions of d variables. We study the complexity of computing an ϵ-approximation in different settings. We are particularly interested in large d and/or large ϵ⁻¹. Tractability means that the complexity is bounded by c(d) K(d, ϵ), where c(d) is the cost of one information operation and K(d, ϵ) is a polynomial in d and/or in ϵ⁻¹. Strong tractability means that K(d, ϵ) is a polynomial in ϵ⁻¹, independent of d. We provide necessary and sufficient conditions for linear multivariate problems to be tractable or strongly tractable in the worst case, average case, randomized, and probabilistic settings. This is done for the class Λ^all where an information operation is defined as the computation of any continuous linear functional. We also consider the class Λ^std where an information operation is defined as the computation of a function value. We show under mild assumptions that tractability in the class Λ^all is equivalent to tractability in the class Λ^std. The proof is, however, not constructive. Finally, we consider linear multivariate problems over reproducing kernel Hilbert spaces, showing that such problems are strongly tractable even in the worst case setting.     

An iterative computation of approximations on Korobov-like spaces

This paper treats the multidimensional application of a previous iterative Monte Carlo algorithm that enables the computation of approximations in L². The case of regular functions is studied using a Fourier basis on periodised functions, Legendre and Tchebychef polynomial bases. The dimensional effect is reduced by computing these approximations on Korobov-like spaces. Numerical results show the efficiency of the algorithm for both approximation and numerical integration.     

p-Adic valued quantization

This review covers an important domain of p-adic mathematical physics — quantum mechanics with p-adic valued wave functions. We start with basic mathematical constructions of this quantum model: Hilbert spaces over quadratic extensions of the field of p-adic numbers ? _p , operators — symmetric, unitary, isometric, one-parameter groups of unitary isometric operators, the p-adic version of Schrödinger’s quantization, representation of canonical commutation relations in Heisenberg andWeyl forms, spectral properties of the operator of p-adic coordinate.We also present postulates of p-adic valued quantization. Here observables as well as probabilities take values in ? _p . A physical interpretation of p-adic quantities is provided through approximation by rational numbers.     

Optimal query error of quantum approximation on some Sobolev classes

We study the approximation of the imbedding of functions from anisotropic and general-ized Sobolev classes into Lq([0,1]d) space in the quantum model of computation. Based on the quantum algorithms for approximation of finite imbedding from LpN to LNq , we develop quantum algorithms for approximating the imbedding from anisotropic Sobolev classes B(Wpr ([0,1]d)) to Lq([0,1]d) space for all 1 q,p ∞ and prove their optimality. Our results show that for p < q the quantum model of computation can bring a speedup roughly up to a squaring of the rate in the classical deterministic and randomized settings.     

When Are Quasi-Monte Carlo Algorithms Efficient for High Dimensional Integrals?

Recently, quasi-Monte Carlo algorithms have been successfully used for multivariate integration of high dimensiond, and were significantly more efficient than Monte Carlo algorithms. The existing theory of the worst case error bounds of quasi-Monte Carlo algorithms does not explain this phenomenon. This paper presents a partial answer to why quasi-Monte Carlo algorithms can work well for arbitrarily larged. It is done by identifying classes of functions for which the effect of the dimensiondis negligible. These areweightedclasses in which the behavior in the successive dimensions is moderated by a sequence of weights. We prove that the minimalworst caseerror of quasi-Monte Carlo algorithms does not depend on the dimensiondiff the sum of the weights is finite. We also prove that the minimal number of function values in the worst case setting needed to reduce the initial error by ε is bounded byCε^−p, where the exponentp∈ [1, 2], andCdepends exponentially on the sum of weights. Hence, the relatively small sum of the weights makes some quasi-Monte Carlo algorithms strongly tractable. We show in a nonconstructive way that many quasi-Monte Carlo algorithms are strongly tractable. Even random selection of sample points (done once for the whole weighted class of functions and then the worst case error is established for that particular selection, in contrast to Monte Carlo where random selection of sample points is carried out for a fixed function) leads to strong tractable quasi-Monte Carlo algorithms. In this case the minimal number of function values in theworst casesetting is of order ε^−pwith the exponentp= 2. The deterministic construction of strongly tractable quasi-Monte Carlo algorithms as well as the minimal exponentpis open.     

On functions in p-adic BMO and the distribution of prime integers

We study the spaces BMOp of functions of bounded mean oscillation modeled on a p-adic martingale, and determine their relationship with the ordinary, continuous space BMO of functions of bounded mean oscillation. Somewhat surprisingly, these results are related to information about the distribution of primes.     

On bounded multilinear forms on a class of lp spaces

In this paper we generalize an old result of Littlewood and Hardy about bilinear forms defined in a class of sequence spaces. Historically, Littlewood [Quart. J. Math.1 (1930)] first proved a result on bilinear forms on bounded sequences and this result was then generalized by Hardy and Littlewood in a joint paper [Quart. J. Math.5(1934)] to bilinear forms on a class of l^p spaces. Later Davie and Kaijser proved Littlewood's results for multilinear forms. In this paper, Theorems A and B generalize the results to multilinear forms on l^p spaces. All the results are stated at the end of Section 1. Theorems A and B are proved, respectively, in Sections 2 and 3.     

Computational Complexity over thep-adic Numbers

A model of computation over thep-adic numbers, for odd primesp, is defined following the approach of Blum, Shub, and Smale. This model employs branching on the property of being a square inQ_pand unit height. The feasibility of systems of quadratic polynomials is shown to be NP-complete in this model. A polynomial time algorithm is given for feasibility of a single quadratic polynomial overQ_p.     

Un algorithme probabiliste de calcul d'approximations polynômiales sur un hypercube

We describe a Monte Carlo method which enables an iterative computation of the L² approximation of a function on any orthonormal basis. We use it for the approximation of smooth functions on an hypercube with the help of multidimensional orthogonal polynomial basis containing only few terms. The algorithm is both a tool for approximation and numerical integration. To cite this article: S. Maire, C. R. Acad. Sci. Paris, Ser. I 336 (2003).     

Tractability of Multivariate Integration for Periodic Functions

We study multivariate integration in the worst case setting for weighted Korobov spaces of smooth periodic functions of d variables. We wish to reduce the initial error by a factor ε for functions from the unit ball of the weighted Korobov space. Tractability means that the minimal number of function samples needed to solve the problem is polynomial in ε⁻¹ and d. Strong tractability means that we have only a polynomial dependence in ε⁻¹. This problem has been recently studied for quasi-Monte Carlo quadrature rules and for quadrature rules with non-negative coefficients. In this paper we study arbitrary quadrature rules. We show that tractability and strong tractability in the worst case setting hold under the same assumptions on the weights of the Korobov space as for the restricted classes of quadrature rules. More precisely, let γ_j moderate the behavior of functions with respect to the jth variable in the weighted Korobov space. Then strong tractability holds iff ∑^∞_j=1 γ_j<∞, whereas tractability holds iff lim sup_d→∞ ∑^d_j=1 γ_j/ln d<∞. We obtain necessary conditions on tractability and strong tractability by showing that multivariate integration for the weighted Korobov space is no easier than multivariate integration for the corresponding weighted Sobolev space of smooth functions with boundary conditions. For the weighted Sobolev space we apply general results from E. Novak and H. Woźniakowski (J. Complexity17 (2001), 388–441) concerning decomposable kernels.     

Dirichlet problem at infinity on Gromov hyperbolic metric measure spaces

We study the asymptotic Dirichlet problem for p-harmonic functions in a very general setting of Gromov hyperbolic metric measure spaces.     

Spline Methods Using Integration Lattices and Digital Nets

Splines are minimum-norm approximations of functions that interpolate the given data (x _l ,f(x _l )),l=0,…,N?1. This paper considers spline approximations to functions in certain reproducing kernel Hilbert spaces, with special choices of the designs {x _l ,l=0,…,N?1}. The designs considered here are node sets of integration lattices and digital nets, and the domain of the functions to be approximated, f is the d-dimensional unit cube. The worst-case errors (in the L _∞ norm) of the splines are shown to depend on the smoothness or digital smoothness of the functions being approximated. Although the convergence rates may be less than ideal, the algorithms are constructive and they do not suffer from a curse of dimensionality.     

Computing the matrix sign and absolute value functions

We present two algorithms for the computation of the matrix sign and absolute value functions. Both algorithms avoid a complete diagonalisation of the matrix, but they however require some informations regarding the eigenvalues location. The first algorithm consists in a sequence of polynomial iterations based on appropriate estimates of the eigenvalues, and converging to the matrix sign if all the eigenvalues are real. Convergence is obtained within a finite number of steps when the eigenvalues are exactly known. Nevertheless, we present a second approach for the computation of the matrix sign and absolute value functions, when the eigenvalues are exactly known. This approach is based on the resolution of an interpolation problem, can handle the case of complex eigenvalues and appears to be faster than the iterative approach. To cite this article: M. Ndjinga, C. R. Acad. Sci. Paris, Ser. I 346 (2008).     

Weak convergence theorems for strict pseudo-contractions in Banach spaces

In this paper, it is shown that there is a gap in the paper [Chidume, C. E., Shahzad, N.: Weak convergence theorems for a finite family of strict pseudo-contractions. Nonlinear Anal., 72, 1257–1265(2010)], consequently, the main results of the paper do not hold in uniformly smooth Banach spaces. Meanwhile, it is also shown that the main results(Lemma 3.4, Theorems 3.5–3.6, 3.8–3.9) in the paper [Cholamjiak, P., Suantai, S.: Weak convergence theorems for a countable family of strict pseudo-contractions in Banach spaces. Fixed Point Theory Appl., 2010, Article ID 632137, 16 pages(2010)] do not hold in Lpfor p 3. Finally, some modified results are presented in the setting of uniformly smooth and uniformly convex Banach spaces which include Lpfor p ≥ 2 as special cases. Furthermore, our arguments are also different from the ones given by the authors above.     

Banach frames for multivariate α-modulation spaces

The α-modulation spaces , α∈[0,1], form a family of spaces that include the Besov and modulation spaces as special cases. This paper is concerned with construction of Banach frames for α-modulation spaces in the multivariate setting. The frames constructed are unions of independent Riesz sequences based on tensor products of univariate brushlet functions, which simplifies the analysis of the full frame. We show that the multivariate α-modulation spaces can be completely characterized by the Banach frames constructed.