Fast quantum algorithms for handling probabilistic and interval uncertainty

In many real‐life situations, we are interested in the value of a physical quantity y that is difficult or impossible to measure directly. To estimate y , we find some easier‐to‐measure quantities x 1 , … , x n which are related to y by a known relation y = f ( x 1 , … , x n ). Measurements are never 100% accurate; hence, the measured values $ \tilde {x} _{i} $ are different from x i , and the resulting estimate $ \tilde {y} = f( \tilde {x} _{1} \ldots , \tilde {x} _{n}) $ is different from the desired value y = f ( x 1 , … , x n ). How different can it be? Traditional engineering approach to error estimation in data processing assumes that we know the probabilities of different measurement errors $ \Delta x_i {\mathop {=} \limits ^{\rm def}} \tilde x _i - x_i $ . In many practical situations, we only know the upper bound Δ i for this error; hence, after the measurement, the only information that we have about x i is that it belongs to the interval $ {\bf x}_i {\mathop {=} \limits ^{\rm def}} [ \tilde x _i - \Delta _i, \tilde x_i + \Delta _i] $ . In this case, it is important to find the range y of all possible values of y = f ( x 1 , … , x n ) when x i ∈ x i . We start the paper with a brief overview of the computational complexity of the corresponding interval computation problems: Most of the related problems turn out to be, in general, at least NP‐hard. In this paper, we show how the use of quantum computing can speed up some computations related to interval and probabilistic uncertainty. We end the paper with speculations on whether (and how) “hypothetic” physical devices can compute NP‐hard problems faster than in exponential time. Most of the paper's results were first presented at NAFIPS'2003 [30]. (© 2004 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)