In traditional interval computations, we assume that the interval data correspond to guaranteed interval bounds, and that fuzzy estimates provided by experts are correct. In practice, measuring instruments are not 100% reliable, and experts are not 100% reliable, we may have estimates which are ‘way off’, intervals which do not contain the actual values at all. Usually, we know the percentage of such outlier un-reliable measurements. However, it is desirable to check that the reliability of the actual data is indeed within the given percentage. The problem of checking (gauging) this reliability is, in general, NP-hard; in reasonable cases, there exist feasible algorithms for solving this problem. In this paper, we show that quantum computation techniques can drastically speed up the computation of reliability of the given data.
In traditional interval computations, we assume that the interval data correspond to guaranteed interval bounds, and that fuzzy estimates provided by experts are correct. In practice, measuring instruments are not 100% reliable, and experts are not 100% reliable, we may have estimates which are ‘way off’, intervals which do not contain the actual values at all. Usually, we know the percentage of such outlier un-reliable measurements. However, it is desirable to check that the reliability of the actual data is indeed within the given percentage. The problem of checking (gauging) this reliability is, in general, NP-hard; in reasonable cases, there exist feasible algorithms for solving this problem. In this paper, we show that quantum computation techniques can drastically speed up the computation of reliability of the given data.
In traditional interval computations, we assume that the interval data corresponds to guaranteed interval bounds, and that fuzzy estimates provided by experts are correct. In practice, measuring instruments are not 100% reliable, and experts are not 100% reliable, we may have estimates which are "way off", intervals which do not contain the actual values at all. Usually, we know the percentage of such outlier un-reliable measurements. However, it is desirable to check that the reliability of the actual data is indeed within the given percentage. The problem of checking (gauging) this reliability is, in general, NP-hard; in reasonable cases, there exist feasible algorithms for solving this problem. In this paper, we show that quantum computations techniques can drastically speed up the computation of reliability of given data.
In traditional interval computations, we assume that the interval data corresponds to guaranteed interval bounds, and that fuzzy estimates provided by experts are correct. In practice, measuring instruments are not 100% reliable, and experts are not 100% reliable, we may have estimates which are \way ofi, intervals which do not contain the actual values at all. Usually, we know the percentage of such outlier un-reliable measurements. However, it is desirable to check that the reliability of the actual data is indeed within the given percentage. The problem of checking (gauging) this reliability is, in general, NP-hard; in reasonable cases, there exist feasible algorithms for solving this problem. In this paper, we show that quantum computations techniques can drastically speed up the computation of reliability of given data.
In data processing, we input the results xi of measuring easy-to-measure quantities xi and use these results to find estimates y = f (x1, . . ., xn) for difficult-to-measure quantities y which are related to xi by a known relation y = f(x1, . . ., xn). Due to measurement inaccuracy, the measured values xi are, in general, different from the (unknown) actual values xi of the measured quantities, hence the result y of data processing is different from the actual value of the quantity y.In many practical situations, we only know the bounds Δi on the measurement errors Δxi [EQUATION] xi - xi. In such situations, we only know that the actual value xi belongs to the interval [xi - Δi, xi + Δi], and we want to know the range of possible values of y. The corresponding problems of interval computations are NP-hard, so solving these problems may take an unrealistically long time. One way to speed up computations is to use quantum computing, and quantum versions of interval computations algorithms have indeed been developed.In many practical situations, we also know some constraints on the possible values of the directly measured quantities x1, . . ., xn. In such situations, we must combine interval techniques with constraint satisfaction techniques. It is therefore desirable to extend quantum interval algorithms to such combinations. As a first step towards this combination, in this paper, we consider quantum algorithms for discrete constraint satisfaction problems.
These notes discuss the quantum algorithms we know of that can solve problems significantly faster than the corresponding classical algorithms.So far, we have only discovered a few techniques which can produce speed up versus classical algorithms.It is not clear yet whether the reason for this is that we do not have enough intuition to discover more techniques, or that there are only a few problems for which quantum computers can significantly speed up the solution.In the first section of these notes, I try to explain why the recent results about quantum computing have been so surprising.This section comes from a talk I have been giving for several years now, and discusses the history of quantum computing and its relation to the mathematical foundations of computer science.In Sections 2 and 3, I talk about the quantum computing model and its relationship to physics.These sections rely heavily on two of my papers [SIAM J. Comp.26 (1997), 1484-1509; Doc.Math.Extra Vol.ICM I (1998), 467-486].Sections 4 and 5 illustrate the general technique of using quantum Fourier transforms to find periodicity.Section 4 contains an algorithm of Dan Simon showing that quantum computers are likely to be exponentially faster than classical computers for some problems.Section 5 discusses my factoring algorithm, which was inspired in part by Dan Simon's paper.In the final section, I discuss Lov Grover's search algorithm, which illustrates a different technique for speeding up classical algorithms.These techniques for constructing faster algorithms for classical problems on quantum computers are the only two significant ones which have been discovered so far.