Quasi-Monte Carlo (QMC) methods are known to achieve faster convergence rates than Monte Carlo (MC), but their effectiveness in high dimensions often relies on additional structure, such as low effective dimension or carefully chosen coordinate weights. Moreover, in many applications one has access only to random samples rather than deterministic QMC constructions. In this work, we extend the recent method of N. Bansal and H. Jiang and construct high-dimensional QMC point sets from random samples via combinatorial discrepancy. We establish error bounds for these constructions in weighted function spaces, including settings with low effective dimension in both the superposition and truncation senses. We also implement the resulting Subgaussian Transference algorithm and present numerical experiments to assess empirically the performance of these constructions.
The quasi-Monte Carlo (QMC) methods use deterministic, usually low-discrepancy sequences, to improve the order of convergence when compared with Monte Carlo methods dealing with the same problem. Although this improved convergence depends on the smoothness properties of the functions under consideration and sometimes cannot be established theoretically, good practical results were obtained in many areas, notably in Financial Mathematics. Most of the QMC methods do not depend on particular properties of the sequences used beyond their good distribution in a suitable multidimensional space. Many families of low-discrepancy sequences have been studies, with the family of the Sobol sequences being not only one of the oldest but also the most popular in practical applications. Since these sequences have many free parameters, it is desirable to have methods to obtain a good set of parameters, suitable for a wide class of problems. In this work we propose a fully deterministic method for optimisation of the direction numbers of the Sobol sequences that is flexible in taking into account smoothness properties of the potential sub-integral functions. We demonstrate how by implementing this algorithm on modern GPUs it is possible to obtain good sets of direction numbers within a reasonable timeframe. The numerical tests demonstrate the significant advantage in terms of accuracy that is observed, which makes the corresponding QMC methods even more competitive.
We study the numerical approximation of high-dimensional integrals using randomized quasi-Monte Carlo (RQMC) methods, with a focus on scrambled Sobol' sequences. While asymptotically faster than Monte Carlo, classical RQMC suffers from error bounds that grow exponentially in the dimension
s, and its root mean squared error (RMSE) convergence rate is generally no better than
O(N−3/2). To overcome these limitations, we combine two recent developments: Suzuki's coarse scrambling and the median trick. Coarse scrambling randomizes Sobol' sequences according to their generating base polynomials and significantly reduces the maximal gain coefficient. By appropriately choosing the base polynomials, we show that the coefficient can be made uniformly bounded in
s, yielding an
O(N−1/2) RMSE for
L2 integrands with a dimension-independent constant. The median trick then enables near-optimal convergence for function classes beyond
L2: for
Lp integrands with
p∈(1,2), the median of independent coarsely scrambled estimates achieves an error of
O(N−1+1/p) with high probability; for integrands in the Haar wavelet space
Hwav,α,s,p,q with
αp:=α−(1/p−1/2)+>0, we prove a high-probability error bound of
O(N−αp−1/2+ε) for any
ε>0; the bound improves to
O(N−r−αp−1/2+ε) when the integrand has dominating mixed derivatives of order
r≥1 that belong to
Hwav,α,s,p,q. The latter two bounds are uniform in
s under suitable conditions on the ANOVA components of the integrands. Numerical experiments confirm the predicted convergence rates and demonstrate the robustness of the proposed approach.
Numerical integration with Monte Carlo methods is a central computational task in many scientific and industrial applications, including financial derivative pricing and risk management. Classical Monte Carlo algorithms are computationally demanding: achieving an accuracy
ε typically requires a number of function evaluations scaling as
O(1/ε2). Quantum-accelerated Monte Carlo methods based on quantum amplitude estimation can in principle quadratically improve this dependence. However, \textit{quasi}-Monte Carlo methods have not been explored in the quantum context. In this work, we introduce a quantum quasi-Monte Carlo algorithm that combines low-discrepancy nets with quantum amplitude estimation. The proposed method prepares the quasi-random point set coherently in superposition. The method does not yield an asymptotic improvement over classical quasi-Monte Carlo, since the total error separates into a discretization error, determined by the finite net, and a quantum estimation error. Instead, we explore a pre-asymptotic advantage window: for a target accuracy that would classically require
2q low discrepancy points, one can prepare a higher-resolution net of size
2Q, with
Q>q, in superposition and reach the same accuracy using significantly fewer function queries. This window can be controlled by tuning the circuit resolution and amplitude-estimation parameters, making the approach relevant for practical regimes where the number of queries is finite rather than asymptotically large.
Monte Carlo (MQ) method is a powerful tool to approximate high dimensional integrals. The disadvantage of ordinary MQ is the slow convergence rate by cause of the essential randomness of this method. Computations of this convergence can lead to pure time consuming. Quasi-Monte Carlo (QMC) method yields considerably better results since this method is a deterministic alternative which uses Low-Discrepancy sequences instead of random samples . There are a multiplicity of big open problems in QMC-methods, problems partly arising from applications and partly arising from theory. QMC are developed to integrate over unite cube, where it has much more accuracy than MC for integrands of bounded variation. Integration over more general spaces such as triangles, disks and Cartesian products of such spaces is more challenging for QMC. Nevertheless in real-world applications various problems are defined over such spaces. The aim of this thesis is to provide a survey of a solution of such problems of numerical integration defined over non-cubical spaces. We present QMC and randomised QMC (RQMC) constructions in the triangle with a vanishing discrepancy based on the recent work of Basu 2016. The QMC construction is a version of the Van der Corput-Halton sequences specially made to the unit triangle. The attraction of scrambled net is replication based error estimation for QMC with slightly the same accuracy as QMC, and for smooth enough integrands.
Abstract A crude Monte Carlo (MC) method allows to calculate integrals over a d-dimensional cube. As the number N of integration nodes becomes large, the rate of probable error of the MC method decreases as O ( 1 / N ) {O(1/\sqrt{N})} . The use of quasi-random points instead of random points in the MC algorithm converts it to the quasi-Monte Carlo (QMC) method. The asymptotic error estimate of QMC integration of d-dimensional functions contains a multiplier 1 / N {1/N} . However, the multiplier ( ln N ) d {(\ln N)^{d}} is also a part of the error estimate, which makes it virtually useless. We have proved that, in the general case, the QMC error estimate is not limited to the factor 1 / N {1/N} . However, our numerical experiments show that using quasi-random points of Sobol sequences with N = 2 m {N=2^{m}} with natural m makes the integration error approximately proportional to 1 / N {1/N} . In our numerical experiments, d ≤ 15 {d\leq 15} , and we used N ≤ 2 40 {N\leq 2^{40}} points generated by the SOBOLSEQ16384 code published in 2011. In this code, d ≤ 2 14 {d\leq 2^{14}} and N ≤ 2 63 {N\leq 2^{63}} .