Read-only-memory-based quantum computation: Experimental explorations using nuclear magnetic resonance and future prospects

Read-only-memory-based (ROM-based) quantum computation (QC) is an alternative to oracle-based QC. It has the advantages of being less magical, and being more suited to implementing space-efficient computation (i.e., computation using the minimum number of writable qubits). Here we consider a number of small (one- and two-qubit) quantum algorithms illustrating different aspects of ROM-based QC. They are: (a) a one-qubit algorithm to solve the Deutsch problem; (b) a one-qubit binary multiplication algorithm; (c) a two-qubit controlled binary multiplication algorithm; and (d) a two-qubit ROM-based version of the Deutsch-Jozsa algorithm. For each algorithm we present experimental verification using nuclear magnetic resonance ensemble QC. The average fidelities for the implementation were in the ranges 0.9-0.97 for the one-qubit algorithms, and 0.84-0.94 for the two-qubit algorithms. We conclude with a discussion of future prospects for ROM-based quantum computation. We propose a four-qubit algorithm, using Grover's iterate, for solving a miniature real-world problem relating to the lengths of paths in a network.

Evolutionary experiments on mate recognition in the Drosophila serrata species complex

It is becoming increasingly apparent that at least some aspects of the evolution of mate recognition may be amenable to manipulation in evolutionary experiments. Quantitative genetic analyses that focus on the genetic consequences of evolutionary processes that result in mate recognition evolution may eventually provide an understanding of the genetic basis of the process of speciation. We review a series of experiments that have attempted to determine the genetic basis of the response to natural and sexual selection on mate recognition in the Drosophila serrata species complex. The genetic basis of mate recognition has been investigated at three levels: (1) between the species of D. serrata and D. birchii using interspecific hybrids, (2) between populations of D. serrata that are sympatric and allopatric with respect to D. birchii, and (3) within populations of D. serrata. These experiments suggest that it may be possible to use evolutionary experiments to observe important events such as the reinforcement of mate recognition, or the generation of the genetic associations that are central to many sexual selection models.

Evidence for an independent radiation of endosymbiotic litostome ciliates within Australian marsupial herbivores

The recent discovery of isotrichid-like ciliates occurring as endosymbionts in macropodid marsupials posed interesting questions in regard to both their phyletic origin (all previous records confined to eutherian mammals) and their morphological evolution (Australian forms possibly representing missing links between previously described genera). The SSU rRNA gene was sequenced for three species (Dasytricha dehorityi, D. dogieli, and Batricha tasmaniensis) and aligned against representatives of all major ciliate classes. The Australian species did not group with the other isotrichid species but instead formed an independent radiation. Discrepancies between recent global phylogenies of the phylum Ciliophora were examined by manipulation of the aligned sequence data set. Sources of conflict between these studies did not stem from differences in outgroup choice or phylogenetic reconstruction methods. Differences in the application of confidence limits and primary sequence alignment have probably resulted in the reporting of spurious associations which are not supported by more conservative confidence or alignment methodology. At present, the ciliate subphylum Intramacro-nucleata is an unresolved polytomy which may be due to deficiencies in the SSU rRNA gene sequence dataset or indicate that the ciliates radiated into their extant classes by rapid burst-like evolution. (C) 2001 academic Press.

A test of the hypothesis of ecological equivalence in an Australian subtropical rain forest

We tested the hypothesis that tree species in a subtropical rain forest in south-east Queensland are ecologically equivalent and therefore have identical environmental requirements for their regeneration. We assessed the evidence that juveniles of species differed in their distributions in treefall gap microsites and along gradients of light availability, soil pH, soil PO4-P availability and soil NO3-N availability. Pairwise comparisons were made on a subset of the common species selected on the basis that they showed a relatively high level of positive association, and would therefore, a priori, be expected to have similar regeneration requirements. Detailed comparisons between the species failed to demonstrate evidence for species differentiation with respect to their tolerance of the disturbance associated with gap microsites or to the gradient of NO3-N availability. However, species differed markedly in their distributions along the soil pH gradient and along the gradients of light availability and soil PO4-P availability. The overall level of ecological differentiation between the species is high: seven out of the 10 possible species pairings showed evidence for ecological differentiation. Such niche differentiation amongst the juveniles of tree species may play an important role in maintaining the species richness of rain-forest communities.

Computation of the linear elastic properties of random porous materials with a wide variety of microstructure

A finite-element method is used to study the elastic properties of random three-dimensional porous materials with highly interconnected pores. We show that Young's modulus, E, is practically independent of Poisson's ratio of the solid phase, nu(s), over the entire solid fraction range, and Poisson's ratio, nu, becomes independent of nu(s) as the percolation threshold is approached. We represent this behaviour of nu in a flow diagram. This interesting but approximate behaviour is very similar to the exactly known behaviour in two-dimensional porous materials. In addition, the behaviour of nu versus nu(s) appears to imply that information in the dilute porosity limit can affect behaviour in the percolation threshold limit. We summarize the finite-element results in terms of simple structure-property relations, instead of tables of data, to make it easier to apply the computational results. Without using accurate numerical computations, one is limited to various effective medium theories and rigorous approximations like bounds and expansions. The accuracy of these equations is unknown for general porous media. To verify a particular theory it is important to check that it predicts both isotropic elastic moduli, i.e. prediction of Young's modulus alone is necessary but not sufficient. The subtleties of Poisson's ratio behaviour actually provide a very effective method for showing differences between the theories and demonstrating their ranges of validity. We find that for moderate- to high-porosity materials, none of the analytical theories is accurate and, at present, numerical techniques must be relied upon.

Complex language functions and subcortical mechanisms: evidence from Huntington's disease and patients with non-thalamic subcortical lesions

The neuropathological changes associated with Huntington's disease (HD) are most marked in the head of the caudate nucleus and, to a lesser extent, in the putamen and globus pallidus, suggesting that at least part of the language impairments found in patients with HD may result from non-thalamic subcortical (NTS) pathology. The present study aimed to test the hypothesis that a signature profile of impaired language functions is found in patients who have sustained damage to the non-thalamic subcortex, either focally induced or resulting from neurodegenerative pathology. The language abilities of a group of patients with Huntington's disease (n=13) were compared with those of an age- and education-matched group of patients with chronic NTS lesions following stroke (n=13) and a non-neurologically impaired control group (n=13). The three groups were compared on language tasks that assessed both primary and more complex language abilities. The primary language battery consisted of The Western Aphasia Battery and The Boston Naming Test, whilst the more complex cognitive-linguistic battery employed selected subtests from The Test of Language Competence-Expanded, The Test of Word Knowledge and The Word Test-Revised. On many of the tests of primary language function from the Western Aphasia Battery, both the HD and NTS participants performed in a similar manner to the control participants. The language performances of the HD participants were significantly more impaired (p<0.05 using modified Bonferroni adjustments) than the control group, however, on various lexico-semantic tasks (e. g. the Boston Naming Test and providing definitions), on both single-word and sentence-level generative tasks (e. g. category fluency and formulating sentences), and on tasks which required interpretation of ambiguous, figurative and inferential meaning. The difficulties that patients with HD experienced with tasks assessing complex language abilities were strikingly similar, both qualitatively and quantitatively, to the language profile produced by NTS participants. The results provide evidence to suggest that a signature language profile is associated with damage to the non-thalamic subcortex resulting from either focal neurological insult or a degenerative disease.

A monolithic smoothing-gap algorithm for contact-impact based on the signed distance function

A new algorithm has been developed for smoothing the surfaces in finite element formulations of contact-impact. A key feature of this method is that the smoothing is done implicitly by constructing smooth signed distance functions for the bodies. These functions are then employed for the computation of the gap and other variables needed for implementation of contact-impact. The smoothed signed distance functions are constructed by a moving least-squares approximation with a polynomial basis. Results show that when nodes are placed on a surface, the surface can be reproduced with an error of about one per cent or less with either a quadratic or a linear basis. With a quadratic basis, the method exactly reproduces a circle or a sphere even for coarse meshes. Results are presented for contact problems involving the contact of circular bodies. Copyright (C) 2002 John Wiley Sons, Ltd.

Universal quantum computation and simulation using any entangling Hamiltonian and local unitaries

What interactions are sufficient to simulate arbitrary quantum dynamics in a composite quantum system? We provide an efficient algorithm to simulate any desired two-body Hamiltonian evolution using any fixed two-body entangling n-qubit Hamiltonian and local unitary operations. It follows that universal quantum computation can be performed using any entangling interaction and local unitary operations.

Practical scheme for quantum computation with any two-qubit entangling gate

Which gates are universal for quantum computation? Although it is well known that certain gates on two-level quantum systems (qubits), such as the controlled-NOT, are universal when assisted by arbitrary one-qubit gates, it has only recently become clear precisely what class of two-qubit gates is universal in this sense. We present an elementary proof that any entangling two-qubit gate is universal for quantum computation, when assisted by one-qubit gates. A proof of this result for systems of arbitrary finite dimension has been provided by Brylinski and Brylinski; however, their proof relies on a long argument using advanced mathematics. In contrast, our proof provides a simple constructive procedure which is close to optimal and experimentally practical.

ROM-based computation: Quantum versus classical

We introduce a model of computation based on read only memory (ROM), which allows us to compare the space-efficiency of reversible, error-free classical computation with reversible, error-free quantum computation. We show that a ROM-based quantum computer with one writable qubit is universal, whilst two writable bits are required for a universal classical ROM-based computer. We also comment on the time-efficiency advantages of quantum computation within this model.

A framework for table driven testing of Java classes

With the advent of object-oriented languages and the portability of Java, the development and use of class libraries has become widespread. Effective class reuse depends on class reliability which in turn depends on thorough testing. This paper describes a class testing approach based on modeling each test case with a tuple and then generating large numbers of tuples to thoroughly cover an input space with many interesting combinations of values. The testing approach is supported by the Roast framework for the testing of Java classes. Roast provides automated tuple generation based on boundary values, unit operations that support driver standardization, and test case templates used for code generation. Roast produces thorough, compact test drivers with low development and maintenance cost. The framework and tool support are illustrated on a number of non-trivial classes, including a graphical user interface policy manager. Quantitative results are presented to substantiate the practicality and effectiveness of the approach. Copyright (C) 2002 John Wiley Sons, Ltd.

An augmented Lanczos algorithm for the efficient computation of a dot-product of a function of a large sparse symmetric matrix

The Lanczos algorithm is appreciated in many situations due to its speed. and economy of storage. However, the advantage that the Lanczos basis vectors need not be kept is lost when the algorithm is used to compute the action of a matrix function on a vector. Either the basis vectors need to be kept, or the Lanczos process needs to be applied twice. In this study we describe an augmented Lanczos algorithm to compute a dot product relative to a function of a large sparse symmetric matrix, without keeping the basis vectors.