Quantum Computing Challenges
Recent discoveries in quantum information processing have brought a variety of deep, important and exciting challenges which need to be faced by physics, informatics and mathematics. The impact of these discoveries is broad and is reflected in new importa
- PDF / 1,209,010 Bytes
- 9 Pages / 547.087 x 685.984 pts Page_size
- 17 Downloads / 235 Views
1. Overview In the last decades of the twientieth century an area has developed studying the properties and uses of large random structures. Probability naturally plays a central role in these investigations but it is probability of a somewhat special sort. First of all, the objects are finite. This removes questions of measurability that so bedevil many probabilists. Second of all, the objects are large. One is interested in the asymptotics as the size (here n) of the random object goes to infinity. Thus one is rarely interested [and can rarely obtain] exact forms for the relevant probabilities but instead is very interested in their asymptotics. Indeed, even the asymptotics can prove to be difficult in which case one struggles with improving lower and upper bounds. The area draws heavily on Discrete Math, particularly Graph Theory. A key structure is the random graph G(n, p). Here there are n labelled vertices and any unordered pair of vertices is adjacent with probability p. The adjacencies are mutually independent events. The random graph was first developed by Paul Erdos and Alfred Renyi with a monumental paper in 1961. The probabilistic method is a general methodology developed by the late Paul Erdos. Its use can be traced to a three page paper of his on the Ramsey function R(k, k) given in 1947. Basically, to prove the existence of a combinatorial object Erdos (and his many followers) create a Gedankenexperimentin more modern terms a randomized algorithm - that might produce an object with the desired properties. One shows that the failure probability is less than one and hence the success probability is positive. Then the Platonic existence of the object is guaranteed, even if algorithmic questions for its construction still remain. Discrete Probability has natural connections to the analysis of algorithms. Many randomized algorithms, such as Quicksort, leave a random variable T for the time (however measured) of the algorithm. Further, there are surprising applications to Computational Complexity, to proving, for example, that no circuit of appropriately limited complexity can be used to calculate a particular Boolean function. Discrete Probability has recently developed strong ties with the study of percolation in mathematical physics. In the random graph model G(n, p) describe above a sudden shift around p = was already detected by Erdos and Renyi. More recent studies open the window of this shift. Very recently these ideas have been applied very successfully to studying Random 2-SAT. Results
*
B. Engquist et al. (eds.), Mathematics Unlimited — 2001 and Beyond © Springer-Verlag Berlin Heidelberg 2001
1096
J.
SPENCER
have been given indicating that sharp concentration is a usual phenomenon in large discrete systems. Calculation of mean and variance playa natural role in Discrete probability, as they do in all of Probability Theory. But Discrete probability is particularly interested in large deviations: If X has mean /-L what can we say about Pr[X > /-L + a] when this probability is extremely small
Data Loading...
