Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Journal of Complexity

Exact cubature for a class of functions of maximum effective dimension

Shu Tezuka, Anargyros Papageorgiou

Published Jun 14, 2006• 2 citations
Publisher
DOI
10.1016/j.jco.2006.04.002

Related papers

Lower and upper bounds for the error of optimal cubature in Besov spaces of mixed smoothness

Ðinh Dũng, Tino Ullrich

We prove lower bounds for the error of optimal cubature formulas for $d$-variate functions from Besov spaces of mixed smoothness $B^{\alpha}_{p,\theta}({\mathbb G}^d)$ in the case $0 1/p$, and upper bounds for QMC methods on the Fibonacci lattice for two-variate periodic functions from $B^{\alpha}_{p,\theta}({\mathbb G}^2)$ in the case $1\leq p \leq \infty$, $0 1/p$, where ${\mathbb G}^d$ is either the $d$-dimensional torus ${\mathbb T}^d$ or the $d$-dimensional cube $[0,1]^d$. In combination these results yield the correct asymptotic of the error of optimal cubature formulas for functions from $B^{\alpha}_{p,\theta}({\mathbb G}^2)$ and indicate that a corresponding results is most likely also true in case $d>2$. This is compared to the obtained correct asymptotic of optimal cubature formulas on Smolyak grids which results in the observation that any cubature formula on Smolyak grids is never optimal for the general setting.

arXiv:1311.1563•Nov 7, 2013•0 citations

An Effective Dimension from Finite Size Scaling

M. A. Novotny

Springer proceedings in physics•Jan 1, 1993•0 citations

Advanced Quasi-Monte Carlo Algorithms for High-dimensional Integration and Approximation

Gowri Suryanarayana

The aim of this research is to develop algorithms to approximate the solutions of problems defined on spaces of d-variate functions, where d can be arbitrarily large. We study quasi-Monte Carlo methods, which in contrast to Monte Carlo methods, use deterministic point sets. These methods converge significantly faster with well chosen points that minimize deterministic error bounds. Additionally, we require that the computational hardness of these methods has only a moderate or no dependence on d. We study this using the information complexity n(d, epsilon), the minimal number of information operations required to achieve an approximation with an error of epsilon or less. If n(d, epsilon) grows exponentially in d, the problem is said to have the 'curse of dimension' and the goal is to vanquish this curse. Our research resulted in several contributions. We studied multivariate integration for a Hilbert space of functions that are invariant under permutations of the variables; this is inspired from the symmetry constraints induced on solutions of the Schrödinger equation for indistinguishable particles. We showed that there exist quasi-Monte Carlo methods that achieve a convergence rate of O(n^−1/2) with the implied constant depending only polynomially on d and under some conditions independent of d (and that shifted rank-1 lattice rules can attain the same). We then provided a construction algorithm for a shifted rank-1 lattice that obtains the (almost) optimal rate of convergence. Next, we extended the use of rank-1 lattice points, traditionally used for the cubature and approximation of periodic functions, to the non-periodic setting. We did this in the cosine space setting, where we extensively studied the use of tent-transformed lattice points for cubature and approximation of nonperiodic functions. We were able to reuse algorithms from the periodic setting by establishing relations between the cosine space and the Korobov space of periodic functions. Finally we studied some special cases of approximation in two dimensions. We derived explicit expressions for various degrees of exactness for the Fibonacci lattice points. We end the thesis with an insight on the Lebesgue constant of trigonometric interpolation using lattice points as interpolation nodes.

•May 27, 2016•0 citations

Liberating the dimension for function approximation

G.W. Wasilkowski, H. Woźniakowski

Journal of Complexity•Sep 17, 2010•22 citations

Coherent state phase estimation based on digital nonlinear phase-locked loop

Xu Han, Shuxin Chen, Hao Wu +2 more

The navigation mechanism of obtaining phase parameters based on quantum theory can break through the limitation of classical physical limit to navigation accuracy. In order to achieve the accurate estimation of the coherent state phase, it is usually assumed that the local oscillator phase must be orthogonal to the coherent state phase in the method of quantum homodyne detection. However, the coherent state phase is unknown and the hypothesis cannot be guaranteed to be correct in practice. In this paper we design a nonlinear phase-locked loop to solve the problem. Firstly, in order to obtain the Wigner distribution for a coherent state, we start with the Wigner distribution for the vacuum state and analyze the noise characteristics according to Wigner distribution of coherent state, then the output of homodyne detection is derived. Secondly, in order to avoid introducing errors in theory, caused by linearization and cope with the limiting requirement between local oscillator phase and coherent state phase in the phase tracking of coherent state, we design an orthogonal simplex cubature Kalman filter (OSCKF) algorithm to achieve the function of the nonlinear phase-locked loop. The algorithm converges by updating the state of the local oscillator phase multiple times, and then, the accurate coherent phase is obtained. Finally, according to the design of the phase-locked loop, we observe the data of homodyne detection and then verify the correctness of the OSCKF algorithm. The simulation results show that the OSCKF can converge to the real phase after observing 200 sampled data and the accuracy is higher than extended Kalmn filter (EKF) and cubature Kalman filter (CKF), and the real phase can be obtained under different local oscillator phase. In conclusion, the nonlinear phase-locked loop based on OSCKF algorithm breaks the limitation of traditional way in which the initial local oscillator phase is required to be orthogonal to the coherent state phase, and effectively avoid the linearization error and improve the anti-nonlinear ability. It is very significant in theory and application .

Acta Physica Sinica•Jan 1, 2019•2 citations

On the necessity of low-effective dimension

Shu Tezuka

Journal of Complexity•Aug 26, 2005•15 citations
We prove lower bounds for the error of optimal cubature formulas for ddd-variate functions from Besov spaces of mixed smoothness Bp,θα(Gd)B^{\alpha}_{p,\theta}({\mathbb G}^d)Bp,θα​(Gd) in the case 01/p0 1/p01/p, and upper bounds for QMC methods on the Fibonacci lattice for two-variate periodic functions from Bp,θα(G2)B^{\alpha}_{p,\theta}({\mathbb G}^2)Bp,θα​(G2) in the case 1≤p≤∞1\leq p \leq \infty1≤p≤∞, 01/p0 1/p01/p, where Gd{\mathbb G}^dGd is either the ddd-dimensional torus Td{\mathbb T}^dTd or the ddd-dimensional cube [0,1]d[0,1]^d[0,1]d. In combination these results yield the correct asymptotic of the error of optimal cubature formulas for functions from Bp,θα(G2)B^{\alpha}_{p,\theta}({\mathbb G}^2)Bp,θα​(G2) and indicate that a corresponding results is most likely also true in case d>2d>2d>2. This is compared to the obtained correct asymptotic of optimal cubature formulas on Smolyak grids which results in the observation that any cubature formula on Smolyak grids is never optimal for the general setting.
The aim of this research is to develop algorithms to approximate the solutions of problems defined on spaces of d-variate functions, where d can be arbitrarily large. We study quasi-Monte Carlo methods, which in contrast to Monte Carlo methods, use deterministic point sets. These methods converge significantly faster with well chosen points that minimize deterministic error bounds. Additionally, we require that the computational hardness of these methods has only a moderate or no dependence on d. We study this using the information complexity n(d, epsilon), the minimal number of information operations required to achieve an approximation with an error of epsilon or less. If n(d, epsilon) grows exponentially in d, the problem is said to have the 'curse of dimension' and the goal is to vanquish this curse. Our research resulted in several contributions. We studied multivariate integration for a Hilbert space of functions that are invariant under permutations of the variables; this is inspired from the symmetry constraints induced on solutions of the Schrödinger equation for indistinguishable particles. We showed that there exist quasi-Monte Carlo methods that achieve a convergence rate of O(n^−1/2) with the implied constant depending only polynomially on d and under some conditions independent of d (and that shifted rank-1 lattice rules can attain the same). We then provided a construction algorithm for a shifted rank-1 lattice that obtains the (almost) optimal rate of convergence. Next, we extended the use of rank-1 lattice points, traditionally used for the cubature and approximation of periodic functions, to the non-periodic setting. We did this in the cosine space setting, where we extensively studied the use of tent-transformed lattice points for cubature and approximation of nonperiodic functions. We were able to reuse algorithms from the periodic setting by establishing relations between the cosine space and the Korobov space of periodic functions. Finally we studied some special cases of approximation in two dimensions. We derived explicit expressions for various degrees of exactness for the Fibonacci lattice points. We end the thesis with an insight on the Lebesgue constant of trigonometric interpolation using lattice points as interpolation nodes.
The navigation mechanism of obtaining phase parameters based on quantum theory can break through the limitation of classical physical limit to navigation accuracy. In order to achieve the accurate estimation of the coherent state phase, it is usually assumed that the local oscillator phase must be orthogonal to the coherent state phase in the method of quantum homodyne detection. However, the coherent state phase is unknown and the hypothesis cannot be guaranteed to be correct in practice. In this paper we design a nonlinear phase-locked loop to solve the problem. Firstly, in order to obtain the Wigner distribution for a coherent state, we start with the Wigner distribution for the vacuum state and analyze the noise characteristics according to Wigner distribution of coherent state, then the output of homodyne detection is derived. Secondly, in order to avoid introducing errors in theory, caused by linearization and cope with the limiting requirement between local oscillator phase and coherent state phase in the phase tracking of coherent state, we design an orthogonal simplex cubature Kalman filter (OSCKF) algorithm to achieve the function of the nonlinear phase-locked loop. The algorithm converges by updating the state of the local oscillator phase multiple times, and then, the accurate coherent phase is obtained. Finally, according to the design of the phase-locked loop, we observe the data of homodyne detection and then verify the correctness of the OSCKF algorithm. The simulation results show that the OSCKF can converge to the real phase after observing 200 sampled data and the accuracy is higher than extended Kalmn filter (EKF) and cubature Kalman filter (CKF), and the real phase can be obtained under different local oscillator phase. In conclusion, the nonlinear phase-locked loop based on OSCKF algorithm breaks the limitation of traditional way in which the initial local oscillator phase is required to be orthogonal to the coherent state phase, and effectively avoid the linearization error and improve the anti-nonlinear ability. It is very significant in theory and application .