We propose a simple quantum algorithm for simulating highly oscillatory quantum dynamics, which does not require complicated quantum control logic for handling time-ordering operators. To our knowledge, this is the first quantum algorithm that is both insensitive to the rapid changes of the time-dependent Hamiltonian and exhibits commutator scaling. Our method can be used for efficient Hamiltonian simulation in the interaction picture. In particular, we demonstrate that for the simulation of the Schr\"odinger equation, our method exhibits superconvergence and achieves a surprising second order convergence rate, of which the proof rests on a careful application of pseudo-differential calculus. Numerical results verify the effectiveness and the superconvergence property of our method.
相關內容
Bayesian inference for nonlinear diffusions, observed at discrete times, is a challenging task that has prompted the development of a number of algorithms, mainly within the computational statistics community. We propose a new direction, and accompanying methodology, borrowing ideas from statistical physics and computational chemistry, for inferring the posterior distribution of latent diffusion paths and model parameters, given observations of the process. Joint configurations of the underlying process noise and of parameters, mapping onto diffusion paths consistent with observations, form an implicitly defined manifold. Then, by making use of a constrained Hamiltonian Monte Carlo algorithm on the embedded manifold, we are able to perform computationally efficient inference for a class of discretely observed diffusion models. Critically, in contrast with other approaches proposed in the literature, our methodology is highly automated, requiring minimal user intervention and applying alike in a range of settings, including: elliptic or hypo-elliptic systems; observations with or without noise; linear or non-linear observation operators. Exploiting Markovianity, we propose a variant of the method with complexity that scales linearly in the resolution of path discretisation and the number of observation times. Python code reproducing the results is available at //doi.org/10.5281/zenodo.5796148
We study generalization bounds for noisy stochastic mini-batch iterative algorithms based on the notion of stability. Recent years have seen key advances in data-dependent generalization bounds for noisy iterative learning algorithms such as stochastic gradient Langevin dynamics (SGLD) based on stability (Mou et al., 2018; Li et al., 2020) and information theoretic approaches (Xu and Raginsky, 2017; Negrea et al., 2019; Steinke and Zakynthinou, 2020; Haghifam et al., 2020). In this paper, we unify and substantially generalize stability based generalization bounds and make three technical advances. First, we bound the generalization error of general noisy stochastic iterative algorithms (not necessarily gradient descent) in terms of expected (not uniform) stability. The expected stability can in turn be bounded by a Le Cam Style Divergence. Such bounds have a O(1/n) sample dependence unlike many existing bounds with O(1/\sqrt{n}) dependence. Second, we introduce Exponential Family Langevin Dynamics(EFLD) which is a substantial generalization of SGLD and which allows exponential family noise to be used with stochastic gradient descent (SGD). We establish data-dependent expected stability based generalization bounds for general EFLD algorithms. Third, we consider an important special case of EFLD: noisy sign-SGD, which extends sign-SGD using Bernoulli noise over {-1,+1}. Generalization bounds for noisy sign-SGD are implied by that of EFLD and we also establish optimization guarantees for the algorithm. Further, we present empirical results on benchmark datasets to illustrate that our bounds are non-vacuous and quantitatively much sharper than existing bounds.
The immersed boundary (IB) method is a non-body conforming approach to fluid-structure interaction (FSI) that uses an Eulerian description of the momentum, viscosity, and incompressibility of a coupled fluid-structure system and a Lagrangian description of the deformations, stresses, and resultant forces of the immersed structure. Integral transforms with Dirac delta function kernels couple Eulerian and Lagrangian variables. In practice, discretizations of these integral transforms use regularized delta function kernels, and although a number of different types of regularized delta functions have been proposed, there has been limited prior work to investigate the impact of the choice of kernel function on the accuracy of the methodology. This work systematically studies the effect of the choice of regularized delta function in several fluid-structure interaction benchmark tests using the immersed finite element/difference (IFED) method, which is an extension of the IB method that uses finite element structural discretizations combined with a Cartesian grid finite difference method for the incompressible Navier-Stokes equations. Further, many IB-type methods evaluate the delta functions at the nodes of the structural mesh, and this requires the Lagrangian mesh to be relatively fine compared to the background Eulerian grid to avoid leaks. The IFED formulation offers the possibility to avoid leaks with relatively coarse structural meshes by evaluating the delta function on a denser collection of interaction points. This study investigates the effect of varying the relative mesh widths of the Lagrangian and Eulerian discretizations. Although this study is done within the context of the IFED method, the effect of different kernels could be important not just for this method, but also for other IB-type methods more generally.
In this paper, we investigate local permutation tests for testing conditional independence between two random vectors $X$ and $Y$ given $Z$. The local permutation test determines the significance of a test statistic by locally shuffling samples which share similar values of the conditioning variables $Z$, and it forms a natural extension of the usual permutation approach for unconditional independence testing. Despite its simplicity and empirical support, the theoretical underpinnings of the local permutation test remain unclear. Motivated by this gap, this paper aims to establish theoretical foundations of local permutation tests with a particular focus on binning-based statistics. We start by revisiting the hardness of conditional independence testing and provide an upper bound for the power of any valid conditional independence test, which holds when the probability of observing collisions in $Z$ is small. This negative result naturally motivates us to impose additional restrictions on the possible distributions under the null and alternate. To this end, we focus our attention on certain classes of smooth distributions and identify provably tight conditions under which the local permutation method is universally valid, i.e. it is valid when applied to any (binning-based) test statistic. To complement this result on type I error control, we also show that in some cases, a binning-based statistic calibrated via the local permutation method can achieve minimax optimal power. We also introduce a double-binning permutation strategy, which yields a valid test over less smooth null distributions than the typical single-binning method without compromising much power. Finally, we present simulation results to support our theoretical findings.
We study the convergences of several FFT-based schemes that are widely applied in computational homogenization for deriving effective coefficients, and the term "convergence" here means the limiting behaviors as spatial resolutions going to infinity. Those schemes include Moulinec-Suquent's scheme [Comput Method Appl M, 157 (1998), pp. 69-94], Willot's scheme [Comptes Rendus M\'{e}canique, 343 (2015), pp. 232-245], and the FEM scheme [Int J Numer Meth Eng, 109 (2017), pp. 1461-1489]. Under some reasonable assumptions, we prove that the effective coefficients obtained by those schemes are all convergent to the theoretical ones. Moreover, for the FEM scheme, we can present several convergence rate estimates under additional regularity assumptions.
We propose a novel numerical method for high dimensional Hamilton--Jacobi--Bellman (HJB) type elliptic partial differential equations (PDEs). The HJB PDEs, reformulated as optimal control problems, are tackled by the actor-critic framework inspired by reinforcement learning, based on neural network parametrization of the value and control functions. Within the actor-critic framework, we employ a policy gradient approach to improve the control, while for the value function, we derive a variance reduced least-squares temporal difference method using stochastic calculus. To numerically discretize the stochastic control problem, we employ an adaptive step size scheme to improve the accuracy near the domain boundary. Numerical examples up to $20$ spatial dimensions including the linear quadratic regulators, the stochastic Van der Pol oscillators, the diffusive Eikonal equations, and fully nonlinear elliptic PDEs derived from a regulator problem are presented to validate the effectiveness of our proposed method.
Optimal experimental design (OED) plays an important role in the problem of identifying uncertainty with limited experimental data. In many applications, we seek to minimize the uncertainty of a predicted quantity of interest (QoI) based on the solution of the inverse problem, rather than the inversion model parameter itself. In these scenarios, we develop an efficient method for goal-oriented optimal experimental design (GOOED) for large-scale Bayesian linear inverse problem that finds sensor locations to maximize the expected information gain (EIG) for a predicted QoI. By deriving a new formula to compute the EIG, exploiting low-rank structures of two appropriate operators, we are able to employ an online-offline decomposition scheme and a swapping greedy algorithm to maximize the EIG at a cost measured in model solutions that is independent of the problem dimensions. We provide detailed error analysis of the approximated EIG, and demonstrate the efficiency, accuracy, and both data- and parameter-dimension independence of the proposed algorithm for a contaminant transport inverse problem with infinite-dimensional parameter field.
This paper presents a novel direct Jacobian total Lagrangian explicit dynamics (DJ-TLED) finite element algorithm for real-time nonlinear mechanics simulation. The nodal force contributions are expressed using only the Jacobian operator, instead of the deformation gradient tensor and finite deformation tensor, for fewer computational operations at run-time. Owing to this proposed Jacobian formulation, novel expressions are developed for strain invariants and constant components, which are also based on the Jacobian operator. Results show that the proposed DJ-TLED consumed between 0.70x and 0.88x CPU solution times compared to state-of-the-art TLED and achieved up to 121.72x and 94.26x speed improvements in tetrahedral and hexahedral meshes, respectively, using GPU acceleration. Compared to TLED, the most notable difference is that the notions of stress and strain are not explicitly visible in the proposed DJ-TLED but embedded implicitly in the formulation of nodal forces. Such a force formulation can be beneficial for fast deformation computation and can be particularly useful if the displacement field is of primary interest, which is demonstrated using a neurosurgical simulation of brain deformations for image-guided neurosurgery. The present work contributes towards a comprehensive DJ-TLED algorithm concerning isotropic and anisotropic hyperelastic constitutive models and GPU implementation. The source code is available at //github.com/jinaojakezhang/DJTLED.
The positive definiteness of discrete time-fractional derivatives is fundamental to the numerical stability (in the energy sense) for time-fractional phase-field models. A novel technique is proposed to estimate the minimum eigenvalue of discrete convolution kernels generated by the nonuniform L1, half-grid based L1 and time-averaged L1 formulas of the fractional Caputo's derivative. The main discrete tools are the discrete orthogonal convolution kernels and discrete complementary convolution kernels. Certain variational energy dissipation laws at discrete levels of the variable-step L1-type methods are then established for time-fractional Cahn-Hilliard model.They are shown to be asymptotically compatible, in the fractional order limit $\alpha\rightarrow1$, with the associated energy dissipation law for the classical Cahn-Hilliard equation. Numerical examples together with an adaptive time-stepping procedure are provided to demonstrate the effectiveness of the proposed methods.
We introduce a new family of deep neural network models. Instead of specifying a discrete sequence of hidden layers, we parameterize the derivative of the hidden state using a neural network. The output of the network is computed using a black-box differential equation solver. These continuous-depth models have constant memory cost, adapt their evaluation strategy to each input, and can explicitly trade numerical precision for speed. We demonstrate these properties in continuous-depth residual networks and continuous-time latent variable models. We also construct continuous normalizing flows, a generative model that can train by maximum likelihood, without partitioning or ordering the data dimensions. For training, we show how to scalably backpropagate through any ODE solver, without access to its internal operations. This allows end-to-end training of ODEs within larger models.
小貼士
登錄享
注冊地址： 北京市海淀區羊坊店路18號2幢3層301-191