Complexity order of multiple resource algorithms

Abstract

Algorithmic efficiency is essential to reducing energy and time usage for computational problems. Optimizing efficiency is important for tasks involving multiple resources, for example in stochastic calculations where the size of the random ensemble competes with the time-step. We define the complexity order of an algorithm needing multiple resources as the exponent of inverse total error with respect to the total resources used. The optimum order is predicted for independent, factorable resources. We show that it equals the inverse sum of the inverse resource orders. This is applied to computing averages in a stochastic differential equation. We treat numerical examples for multiple different algorithms and for stochastic partial differential equations, all giving quantitative results in excellent agreement with our more general analytic theory.

This version includes a stochastic partial differential equation numerical example and improved optimisation results

References in corpus (14)

• Supplementary information for "Quantum supremacy using a programmable superconducting processor"
• Dynamical quantum noise in Bose-Einstein condensates
• Experimental Quantum Switching for Exponentially Superior Quantum Communication Complexity
• Numerical Methods for Stochastic Differential Equations
• Canonical Bose gas simulations with stochastic gauges
• Nonadiabatic dynamics of a Bose-Einstein condensate in an optical lattice
• Quantum software for linear photonic simulations
• Simulating and assessing boson sampling experiments with phase-space representations
• Nonlocal pair correlations in a higher-order Bose gas soliton
• Fisher Waves: an individual based stochastic model
• Continuum of classical-field ensembles from canonical to grand canonical and the onset of their equivalence
• Unbounded quantum advantage in communication complexity measured by distinguishability
• Parallel optimized sampling for stochastic equations
• Non-local SPDE limits of spatially-correlated-noise driven spin systems derived to sample a canonical distribution