Implementing the quantum random walk

Recently, several groups have investigated quantum analogues of random walk algorithms, both on a line and on a circle. It has been found that the quantum versions have markedly different features to the classical versions. Namely, the variance on the line, and the mixing time on the circle increase quadratically faster in the quantum versions as compared to the classical versions. Here, we propose a scheme to implement the quantum random walk on a line and on a circle in an ion trap quantum computer. With current ion trap technology, the number of steps that could be experimentally implemented will be relatively small. However, we show how the enhanced features of these walks could be observed experimentally. In the limit of strong decoherence, the quantum random walk tends to the classical random walk. By measuring the degree to which the walk remains quantum, '' this algorithm could serve as an important benchmarking protocol for ion trap quantum computers.

The emergence of order in random walk resource discovery protocols

While others have attempted to determine, by way of mathematical formulae, optimal resource duplication strategies for random walk protocols, this paper is concerned with studying the emergent effects of dynamic resource propagation and replication. In particular, we show, via modelling and experimentation, that under any given decay (purge) rate the number of nodes that have knowledge of particular resource converges to a fixed point or a limit cycle. We also show that even for high rates of decay - that is, when few nodes have knowledge of a particular resource - the number of hops required to find that resource is small.

One-dimensional quantum walk with unitary noise

The effect of unitary noise on the discrete one-dimensional quantum walk is studied using computer simulations. For the noiseless quantum walk, starting at the origin (n=0) at time t=0, the position distribution P-t(n) at time t is very different from the Gaussian distribution obtained for the classical random walk. Furthermore, its standard deviation, sigma(t) scales as sigma(t)similar tot, unlike the classical random walk for which sigma(t)similar toroott. It is shown that when the quantum walk is exposed to unitary noise, it exhibits a crossover from quantum behavior for short times to classical-like behavior for long times. The crossover time is found to be Tsimilar toalpha(-2), where alpha is the standard deviation of the noise.

Pseudo memory effects, majorization and entropy in quantum random walks

A quantum random walk on the integers exhibits pseudo memory effects, in that its probability distribution after N steps is determined by reshuffling the first N distributions that arise in a classical random walk with the same initial distribution. In a classical walk, entropy increase can be regarded as a consequence of the majorization ordering of successive distributions. The Lorenz curves of successive distributions for a symmetric quantum walk reveal no majorization ordering in general. Nevertheless, entropy can increase, and computer experiments show that it does so on average. Varying the stages at which the quantum coin system is traced out leads to new quantum walks, including a symmetric walk for which majorization ordering is valid but the spreading rate exceeds that of the usual symmetric quantum walk.

Modelling dispersal behaviour on a fractal landscape

We use a spatially explicit population model to explore the population consequences of different habitat selection mechanisms on landscapes with fractal variation in habitat quality. We consider dispersal strategies ranging from random walks to perfect habitat selectors for two species of arboreal marsupial, the greater glider (Petauroides volans) and the mountain brushtail possum (Trichosurus caninus). In this model increasing habitat selection means individuals obtain higher quality territories, but experience increased mortality during dispersal. The net effect is that population sizes are smaller when individuals actively select habitat. We find positive relationships between habitat quality and population size can occur when individuals do not use information about the entire landscape when habitat quality is spatially autocorrelated. We also find that individual behaviour can mitigate the negative effects of spatial variation on population average survival and fecundity. (C) 1998 Elsevier Science Ltd. All rights reserved.

Short-term autocorrelation in Australian equities

This paper examines the statistical and economic significance of short-term autocorrelation in Australian equities. We document large negative first-order autocorrelation in individual stock returns. Preliminary results suggest this autocorrelation is economically significant, as two simple trading strategies based on the autocorrelation structure appear to yield large risk-adjusted returns. Further analysis, however, shows that these results are driven by the inclusion of small-capitalisation and low-priced stocks which are vulnerable to a number of market-microstructure-related problems. After revising the dataset to mitigate these problems, little evidence of economic significance remains.

On the inverse parabolicity of pdf equations in turbulent flows

The focus of the present work is the well-known feature of the probability density function (PDF) transport equations in turbulent flows-the inverse parabolicity of the equations. While it is quite common in fluid mechanics to interpret equations with direct (forward-time) parabolicity as diffusive (or as a combination of diffusion, convection and reaction), the possibility of a similar interpretation for equations with inverse parabolicity is not clear. According to Einstein's point of view, a diffusion process is associated with the random walk of some physical or imaginary particles, which can be modelled by a Markov diffusion process. In the present paper it is shown that the Markov diffusion process directly associated with the PDF equation represents a reasonable model for dealing with the PDFs of scalars but it significantly underestimates the diffusion rate required to simulate turbulent dispersion when the velocity components are considered.

Heavy tails, importance sampling and cross-entropy

We consider the problem of estimating P(Yi + (...) + Y-n > x) by importance sampling when the Yi are i.i.d. and heavy-tailed. The idea is to exploit the cross-entropy method as a toot for choosing good parameters in the importance sampling distribution; in doing so, we use the asymptotic description that given P(Y-1 + (...) + Y-n > x), n - 1 of the Yi have distribution F and one the conditional distribution of Y given Y > x. We show in some specific parametric examples (Pareto and Weibull) how this leads to precise answers which, as demonstrated numerically, are close to being variance minimal within the parametric class under consideration. Related problems for M/G/l and GI/G/l queues are also discussed.

Encounter success of free-ranging marine predator movements across a dynamic prey landscape

Movements of wide-ranging top predators can now be studied effectively using satellite and archival telemetry. However, the motivations underlying movements remain difficult to determine because trajectories are seldom related to key biological gradients, such as changing prey distributions. Here, we use a dynamic prey landscape of zooplankton biomass in the north-east Atlantic Ocean to examine active habitat selection in the plankton-feeding basking shark Cetorhinus maximus. The relative success of shark searches across this landscape was examined by comparing prey biomass encountered by sharks with encounters by random-walk simulations of ‘model’ sharks. Movements of transmitter-tagged sharks monitored for 964 days (16754km estimated minimum distance) were concentrated on the European continental shelf in areas characterized by high seasonal productivity and complex prey distributions. We show movements by adult and sub-adult sharks yielded consistently higher prey encounter rates than 90% of random-walk simulations. Behavioural patterns were consistent with basking sharks using search tactics structured across multiple scales to exploit the richest prey areas available in preferred habitats. Simple behavioural rules based on learned responses to previously encountered prey distributions may explain the high performances. This study highlights how dynamic prey landscapes enable active habitat selection in large predators to be investigated from a trophic perspective, an approach that may inform conservation by identifying critical habitat of vulnerable species.

A modified discrete random pore model allowing for different initial surface reactivity

We investigate here a modification of the discrete random pore model [Bhatia SK, Vartak BJ, Carbon 1996;34:1383], by including an additional rate constant which takes into account the different reactivity of the initial pore surface having attached functional groups and hydrogens, relative to the subsequently exposed surface. It is observed that the relative initial reactivity has a significant effect on the conversion and structural evolution, underscoring the importance of initial surface chemistry. The model is tested against experimental data on chemically controlled char oxidation and steam gasification at various temperatures. It is seen that the variations of the reaction rate and surface area with conversion are better represented by the present approach than earlier random pore models. The results clearly indicate the improvement of model predictions in the low conversion region, where the effect of the initially attached functional groups and hydrogens is more significant, particularly for char oxidation. It is also seen that, for the data examined, the initial surface chemistry is less important for steam gasification as compared to the oxidation reaction. Further development of the approach must also incorporate the dynamics of surface complexation, which is not considered here.

Random numbers from astronomical imaging

This article describes a method to turn astronomical imaging into a random number generator by using the positions of incident cosmic rays and hot pixels to generate bit streams. We subject the resultant bit streams to a battery of standard benchmark statistical tests for randomness and show that these bit streams are statistically the same as a perfect random bit stream. Strategies for improving and building upon this method are outlined.

The collision branching process

We consider a branching model, which we call the collision branching process (CBP), that accounts for the effect of collisions, or interactions, between particles or individuals. We establish that there is a unique CBP, and derive necessary and sufficient conditions for it to be nonexplosive. We review results on extinction probabilities, and obtain explicit expressions for the probability of explosion and the expected hitting times. The upwardly skip-free case is studied in some detail.

Isolation of genotype- and chromosome-specific DNA markers in a biotype of Colletotrichum gloeosporioides using random amplified polymorphic DNA analysis

Genetic markers that distinguish fungal genotypes are important tools for genetic analysis of heterokaryosis and parasexual recombination in fungi. Random amplified polymorphic DNA (RAPD) markers that distinguish two races of biotype B of Colletotrichum gloeosporioides infecting the legume Stylosanthes guianensis were sought. Eighty-five arbitrary oligonucleotide primers were used to generate 895 RAPD bands but only two bands were found to be specifically amplified from DNA of the race 3 isolate. These two RAPD bands were used as DNA probes and hybridised only to DNA of the race 3 isolate. Both RAPD bands hybridised to a dispensable 1.2 Mb chromosome of the race 3 isolate. No other genotype-specific chromosomes or DNA sequences were identified in either the race 2 or race 3 isolates. The RAPD markers hybridised to a 2 Mb chromosome in all races of the genetically distinct biotype A pathogen which infects other species of Stylosanthes as well as S. guianensis. The experiments indicate that RAPD analysis is a potentially useful tool for obtaining genotype-and chromosome-specific DNA probes in closely related isolates of one biotype of this fungal pathogen.

Quasispin graded-fermion formalism and gl(m vertical bar n)down arrow osp(m vertical bar n) branching rules

The graded-fermion algebra and quasispin formalism are introduced and applied to obtain the gl(m\n)down arrow osp(m\n) branching rules for the two- column tensor irreducible representations of gl(m\n), for the case m less than or equal to n(n > 2). In the case m < n, all such irreducible representations of gl(m\n) are shown to be completely reducible as representations of osp(m\n). This is also shown to be true for the case m=n, except for the spin-singlet representations, which contain an indecomposable representation of osp(m\n) with composition length 3. These branching rules are given in fully explicit form. (C) 1999 American Institute of Physics. [S0022-2488(99)04410-2].