**C**ame perchance upon this reminiscence about the generation of the 10⁶ random digits found in the book published by the RAND Corporation. It took them a month to produce half a million digits, exploiting a “random frequency pulse source gated by a constant frequency pulse” behaving like a “roulette wheel with 32 positions, making on the average 3000 revolutions on each turn”. As the outcome failed on the odd/even ratio test, the RAND engineers randomized further the outcome by adding “(mod 10) the digits in each card, digit by digits, to the corresponding digits of the previous card”. (Cards as in punched cards, the outcome being printed 50 digits at a time on I.B.M. cards.) A last piece of Monte Carlo trivia is that the electronic roulette at the basis of this random generator was devised by Hastings, Cecil not Wilfred Keith. (And RAND is an abbreviation of Research and Development, not of randomness!)

## Archive for IBM

## my own personal hope for the future is that we won’t have to build any more random number generators…

Posted in Books, Statistics, University life with tags cross validated, IBM, punched card, rand, random number generation, roulette, Wilfred Keith Hastings on April 19, 2020 by xi'an## quantum simulation or supremacy?

Posted in Books, Statistics, University life with tags Google, IBM, Nature, quantum computer, qubit, random number generation on November 11, 2019 by xi'an**N**ature this week contains a prominent paper by Arute et al. reporting an experiment on a quantum computer running a simulation on a state-space of dimension 2^{53} (which is the number of qubits in their machine, plus one dedicated to error correction if I get it right). With a million simulation of the computer state requiring 200 seconds. Which they claim would take 10,000 years (3 10¹¹ seconds) to run on a classical super-computer. And which could be used towards producing certified random numbers, an impressive claim given the intrinsic issue of qubit errors. (This part is not developed in the paper but I wonder how a random generator could handle such errors.)

“…a “challenger” generates a random quantum circuit C (i.e., a random sequence of 1-qubit and nearest-neighbor 2-qubit gates, of depth perhaps 20, acting on a 2D grid of n = 50 to 60 qubits). The challenger then sends C to the quantum computer, and asks it apply C to the all-0 initial state, measure the result in the {0,1} basis, send back whatever n-bit string was observed, and repeat some thousands or millions of times. Finally, using its knowledge of C, the classical challenger applies a statistical test to check whether the outputs are consistent with the QC having done this.” The blog of Scott Aaronson

I have tried reading the Nature paper but had trouble grasping the formidable nature of the simulation they were discussing, as it seems to be the reproduction by a simulation of a large quantum circuit of depth 20, as helpfully explained in the above quote. And checking the (non-uniform) distribution of the random simulation is the one expected. Which is the hard part and requires a classical (super-)computer to determine the theoretical distribution. And the News & Views entry in the same issue of Nature. According to Wikipedia, “the best known algorithm for simulating an arbitrary random quantum circuit requires an amount of time that scales exponentially with the number of qubits“. However, IBM (a competitor of Google in the quantum computer race) counter-claims that the simulation of the circuit takes only 2.5 days on a classical computer with optimised coding. (And this should be old news by the time this blog post comes out, since even a US candidate for the presidency has warned about it!)

## go, go, go…deeper!

Posted in pictures, Statistics with tags Deep Blue, deep learning, Go, Google, IBM, machine learning, Monte Carlo algorithm, neural network, reinforced learning, superintelligence, supervised learning on February 19, 2016 by xi'an**W**hile visiting Warwick, last week, I came across the very issue of Nature with the highly advertised paper of David Silver and co-authors from DeepMind detailing how they designed their Go player algorithm that bested a European Go master five games in a row last September. Which is a rather unexpected and definitely brilliant feat given the state of the art! And compares (in terms of importance, if not of approach) with the victory of IBM Deep Blue over Gary Kasparov 20 years ago… (Another *deep* algorithm, showing that the attraction of programmers for this label has not died off over the years!)This paper is not the easiest to read (especially over breakfast), with (obviously) missing details, but I gathered interesting titbits from this cursory read. One being the reinforced learning step where the predictor is improved by being applied against earlier versions. While this can lead to overfitting, the authors used randomisation to reduce this feature. This made me wonder if a similar step could be on predictors like random forests. E.g., by weighting the trees or the probability of including a predictor or another.Another feature of major interest is their parallel use of *two* neural networks in the decision-making, a first one estimating a probability distribution over moves learned from millions of human Go games and a second one returning a utility or value for each possible move. The first network is used for tree exploration with Monte Carlo steps, while the second leads to the final decision.

This is a fairly good commercial argument for machine learning techniques (and for DeepMind as well), but I do not agree with the doom-sayers predicting the rise of the machines and our soon to be annihilation! (Which is the major theme of Superintelligence.) This result shows that, with enough learning data and sufficiently high optimising power and skills, it is possible to produce an excellent predictor of the set of Go moves leading to a victory. Without the brute force strategy of Deep Blue that simply explored the tree of possible games to a much more remote future than a human player could do (along with the perfect memory of a lot of games). I actually wonder if DeepMind has also designed a chess algorithm on the same principles: there is no reason why it should no work. However, this success does not predict the soon to come emergence of AI’s able to deal with vaguer and broader scopes: in that sense, automated drivers are much more of an advance (unless they start bumping into other cars and pedestrians on a regular basis!).