A quantum full adder for a scalable nuclear spin quantum computer

We demonstrate a strategy for implementation a quantum full adder in a spin chain quantum computer. As an example, we simulate a quantum full adder in a chain containing 201 spins. Our simulations also demonstrate how one can minimize errors generated by non-resonant effects.     

One-dimensional quantum walks with absorbing boundaries

In this paper we analyze the behavior of quantum random walks. In particular, we present several new results for the absorption probabilities in systems with both one and two absorbing walls for the one-dimensional case. We compute these probabilities both by employing generating functions and by use of an eigenfunction approach. The generating function method is used to determine some simple properties of the walks we consider, but appears to have limitations. The eigenfunction approach works by relating the problem of absorption to a unitary problem that has identical dynamics inside a certain domain, and can be used to compute several additional interesting properties, such as the time dependence of absorption. The eigenfunction method has the distinct advantage that it can be extended to arbitrary dimensionality. We outline the solution of the absorption probability problem of a (D−1)-dimensional wall in a D-dimensional space.     

Efficient implementation of parallel three-dimensional FFT on clusters of PCs

In this paper, we propose a high-performance parallel three-dimensional fast Fourier transform (FFT) algorithm on clusters of PCs. The three-dimensional FFT algorithm can be altered into a block three-dimensional FFT algorithm to reduce the number of cache misses. We show that the block three-dimensional FFT algorithm improves performance by utilizing the cache memory effectively. We use the block three-dimensional FFT algorithm to implement the parallel three-dimensional FFT algorithm. We succeeded in obtaining performance of over 1.3 GFLOPS on an 8-node dual Pentium III 1 GHz PC SMP cluster.     

Physical quantum algorithms

I review the differences between classical and quantum systems, emphasizing the connection between no-hidden variable theorems and superior computational power of quantum computers. Using quantum lattice gas automata as examples, I describe possibilities for efficient simulation of quantum and classical systems with a quantum computer. I conclude with a list of research directions.     

Pathfinder: A parallel search algorithm for concerted atomistic events

An algorithm has been designed to search for the escape paths with the lowest activation barriers when starting from a local minimum-energy configuration of a many-atom system. The pathfinder algorithm combines: (1) a steered eigenvector-following method that guides a constrained escape from the convex region and subsequently climbs to a transition state tangentially to the eigenvector corresponding to the lowest negative Hessian eigenvalue; (2) discrete abstraction of the atomic configuration to systematically enumerate concerted events as linear combinations of atomistic events; (3) evolutionary control of the population dynamics of low activation-barrier events; and (4) hybrid task + spatial decompositions to implement massive search for complex events on parallel computers. The program exhibits good scalability on parallel computers and has been used to study concerted bond-breaking events in the fracture of alumina.     

Deterministic event-based simulation of quantum phenomena

We propose and analyse simple deterministic algorithms that can be used to construct machines that have primitive learning capabilities. We demonstrate that locally connected networks of these machines can be used to perform blind classification on an event-by-event basis, without storing the information of the individual events. We also demonstrate that properly designed networks of these machines exhibit behavior that is usually only attributed to quantum systems. We present networks that simulate quantum interference on an event-by-event basis. In particular we show that by using simple geometry and the learning capabilities of the machines it is possible to simulate single-photon interference in a Mach-Zehnder interferometer. The interference pattern generated by the network of deterministic learning machines is in perfect agreement with the quantum theoretical result for the single-photon Mach-Zehnder interferometer. To illustrate that networks of these machines are indeed capable of simulating quantum interference we simulate, event-by-event, a setup involving two chained Mach-Zehnder interferometers, and demonstrate that also in this case the simulation results agree with quantum theory.     

A scalable parallel algorithm for large-scale reactive force-field molecular dynamics simulations

A scalable parallel algorithm has been designed to perform multimillion-atom molecular dynamics (MD) simulations, in which first principles-based reactive force fields (ReaxFF) describe chemical reactions. Environment-dependent bond orders associated with atomic pairs and their derivatives are reused extensively with the aid of linked-list cells to minimize the computation associated with atomic n-tuple interactions (n?4 explicitly and ?6 due to chain-rule differentiation). These n-tuple computations are made modular, so that they can be reconfigured effectively with a multiple time-step integrator to further reduce the computation time. Atomic charges are updated dynamically with an electronegativity equalization method, by iteratively minimizing the electrostatic energy with the charge-neutrality constraint. The ReaxFF-MD simulation algorithm has been implemented on parallel computers based on a spatial decomposition scheme combined with distributed n-tuple data structures. The measured parallel efficiency of the parallel ReaxFF-MD algorithm is 0.998 on 131,072 IBM BlueGene/L processors for a 1.01 billion-atom RDX system.     

A space-time-ensemble parallel nudged elastic band algorithm for molecular kinetics simulation

A scalable parallel algorithm has been designed to study long-time dynamics of many-atom systems based on the nudged elastic band method, which performs mutually constrained molecular dynamics simulations for a sequence of atomic configurations (or states) to obtain a minimum energy path between initial and final local minimum-energy states. A directionally heated nudged elastic band method is introduced to search for thermally activated events without the knowledge of final states, which is then applied to an ensemble of bands in a path ensemble method for long-time simulation in the framework of the transition state theory. The resulting molecular kinetics (MK) simulation method is parallelized with a space-time-ensemble parallel nudged elastic band (STEP-NEB) algorithm, which employs spatial decomposition within each state, while temporal parallelism across the states within each band and band-ensemble parallelism are implemented using a hierarchy of communicator constructs in the Message Passing Interface library. The STEP-NEB algorithm exhibits good scalability with respect to spatial, temporal and ensemble decompositions on massively parallel computers. The MK simulation method is used to study low strain-rate deformation of amorphous silica.     

Simulation of n-qubit quantum systems. II. Separability and entanglement

Studies on the entanglement of n-qubit quantum systems have attracted a lot of interest during recent years. Despite the central role of entanglement in quantum information theory, however, there are still a number of open problems in the theoretical characterization of entangled systems that make symbolic and numerical simulation on n-qubit quantum registers indispensable for present-day research.To facilitate the investigation of the separability and entanglement properties of n-qubit quantum registers, here we present a revised version of the Feynman program in the framework of the computer algebra system Maple. In addition to all previous capabilities of this Maple code for defining and manipulating quantum registers, the program now provides various tools which are necessary for the qualitative and quantitative analysis of entanglement in n-qubit quantum registers. A simple access, in particular, is given to several algebraic separability criteria as well as a number of entanglement measures and related quantities. As in the previous version, symbolic and numeric computations are equally supported.

Program summary

Title of program:FeynmanCatalogue identifier:ADWE_v2_0Program summary URL:http://cpc.cs.qub.ac.uk/summaries/ADWE_v2_0Program obtainable from: CPC Program Library, Queen's University of Belfast, N. IrelandLicensing provisions:NoneComputers for which the program is designed: All computers with a license of the computer algebra system Maple [Maple is a registered trademark of Waterloo Maple Inc.]Operating systems under which the program has been tested: Linux, MS Windows XPProgramming language used:Maple 10Typical time and memory requirements:Most commands acting on quantum registers with five or less qubits take ?10 seconds of processor time (on a Pentium 4 with ?2 GHz or equivalent) and 5-20 MB of memory. However, storage and time requirements critically depend on the number of qubits, n, in the quantum registers due to the exponential increase of the associated Hilbert space.No. of lines in distributed program, including test data, etc.:3107No. of bytes in distributed program, including test data, etc.:13 859Distribution format:tar.gzReasons for new version:The first program version established the data structures and commands which are needed to build and manipulate quantum registers. Since the (evolution of) entanglement is a central aspect in quantum information processing the current version adds the capability to analyze separability and entanglement of quantum registers by implementing algebraic separability criteria and entanglement measures and related quantities.Does this version supersede the previous version: YesNature of the physical problem: Entanglement has been identified as an essential resource in virtually all aspects of quantum information theory. Therefore, the detection and quantification of entanglement is a necessary prerequisite for many applications, such as quantum computation, communications or quantum cryptography. Up to the present, however, the multipartite entanglement of n-qubit systems has remained largely unexplored owing to the exponential growth of complexity with the number of qubits involved.Method of solution: Using the computer algebra system Maple, a set of procedures has been developed which supports the definition and manipulation of n-qubit quantum registers and quantum logic gates [T. Radtke, S. Fritzsche, Comput. Phys. Comm. 173 (2005) 91]. The provided hierarchy of commands can be used interactively in order to simulate the behavior of n-qubit quantum systems (by applying a number of unitary or non-unitary operations) and to analyze their separability and entanglement properties.Restrictions onto the complexity of the problem: The present version of the program facilitates the setup and the manipulation of quantum registers by means of (predefined) quantum logic gates; it now also provides the tools for performing a symbolic and/or numeric analysis of the entanglement for the quantum states of such registers. Owing to the rapid increase in the computational complexity of multi-qubit systems, however, the time and memory requirements often grow rapidly, especially for symbolic computations. This increase of complexity limits the application of the program to about 6 or 7 qubits on a standard single processor (Pentium 4 with ?2 GHz or equivalent) machine with ?1 GB of memory.Unusual features of the program: The Feynman program has been designed within the framework of Maple for interactive (symbolic or numerical) simulations on n-qubit quantum registers with no other restriction than given by the memory and processor resources of the computer. Whenever possible, both representations of quantum registers in terms of their state vectors and/or density matrices are equally supported by the program. Apart from simulating quantum gates and quantum operations, the program now facilitates also investigations on the separability and the entanglement properties of quantum registers.     

Efficient data processing and quantum phenomena: Single-particle systems

We study the relation between the acquisition and analysis of data and quantum theory using a probabilistic and deterministic model for photon polarizers. We introduce criteria for efficient processing of data and then use these criteria to demonstrate that efficient processing of the data contained in single events is equivalent to the observation that Malus' law holds. A strictly deterministic process that also yields Malus' law is analyzed in detail. We present a performance analysis of the probabilistic and deterministic model of the photon polarizer. The latter is an adaptive dynamical system that has primitive learning capabilities. This additional feature has recently been shown to be sufficient to perform event-by-event simulations of interference phenomena, without using concepts of wave mechanics. We illustrate this by presenting results for a system of two chained Mach-Zehnder interferometers, suggesting that systems that perform efficient data processing and have learning capability are able to exhibit behavior that is usually attributed to quantum systems only.     

Scalable and portable implementation of the fast multipole method on parallel computers

A scalable and portable Fortran code is developed to calculate Coulomb interaction potentials of charged particles on parallel computers, based on the fast multipole method. The code has a unique feature to calculate microscopic stress tensors due to the Coulomb interactions, which is useful in constant-pressure simulations and local stress analyses. The code is applicable to various boundary conditions, including periodic boundary conditions in two and three dimensions, corresponding to slab and bulk systems, respectively. Numerical accuracy of the code is tested through comparison of its results with those obtained by the Ewald summation method and by direct calculations. Scalability tests show the parallel efficiency of 0.98 for 512 million charged particles on 512 IBM SP3 processors. The timing results on IBM SP3 are also compared with those on IBM SP4.     

Dynamic procedures of image reconstruction from projections (computer tomography)

A method of reconstruction of images from projections is suggested. In contrast to the static procedure conventionally used for the solution of problems of image reconstruction from projections, this method presupposes the use of a dynamic procedure. Such an approach, in combination with the use of special noise-immune algorithms of image reconstruction, permits obtaining images of the internal structure of the object under study of a high quality by irradiating it sequentially in time by the flows of photons of a small intensity. The effectiveness of the suggested method is illustrated by the example of results of a computer experiment.     

On time-step bounds in unitary quantum evolution using the Lanczos method

To solve the non-relativistic time dependent Schrödinger equation using the Lanczos method, Park and Light have provided an approximate expression for the time step for a given accuracy. We provide an exact expression for the time step in terms of the eigenvalues and eigenvectors of the resulting tridiagonal matrix. For two test problems, the values of the time step provided by Park and Light differ significantly from the exact values provided by the present method. We also indicate upper and lower bounds for the time step in terms of the maximum and minimum eigenvalues. These bounds indicate the possibility of using a new time step given by the geometric mean of the eigenvalues of the tridiagonal matrix.     

Embedded divide-and-conquer algorithm on hierarchical real-space grids: parallel molecular dynamics simulation based on linear-scaling density functional theory

A linear-scaling algorithm has been developed to perform large-scale molecular-dynamics (MD) simulations, in which interatomic forces are computed quantum mechanically in the framework of the density functional theory. A divide-and-conquer algorithm is used to compute the electronic structure, where non-additive contribution to the kinetic energy is included with an embedded cluster scheme. Electronic wave functions are represented on a real-space grid, which is augmented with coarse multigrids to accelerate the convergence of iterative solutions and adaptive fine grids around atoms to accurately calculate ionic pseudopotentials. Spatial decomposition is employed to implement the hierarchical-grid algorithm on massively parallel computers. A converged solution to the electronic-structure problem is obtained for a 32,768-atom amorphous CdSe system on 512 IBM POWER4 processors. The total energy is well conserved during MD simulations of liquid Rb, showing the applicability of this algorithm to first principles MD simulations. The parallel efficiency is 0.985 on 128 Intel Xeon processors for a 65,536-atom CdSe system.     

The solution of stationary ODE problems in quantum mechanics by Magnus methods with stepsize control

In solid state physics the solution of the Dirac and Schrödinger equation by operator splitting methods leads to differential equations with oscillating solutions for the radial direction. For standard time integrators like Runge-Kutta or multistep methods the stepsize is restricted approximately by the length of the period. In contrast the recently developed Magnus methods allow stepsizes that are substantially larger than one period. They are based on a Lie group approach and incorporate exponential functions and matrix commutators. A stepsize control is implemented and tested. As numerical examples eigenvalue problems for the radial Schrödinger equation and the radial Dirac equation are solved. Further, phase shifts for scattering solutions for hydrogen atoms and copper are computed.     

Linearization methods in classical and quantum mechanics

The applicability and accuracy of linearization methods for initial-value problems in ordinary differential equations are verified on examples that include the nonlinear Duffing equation, the Lane-Emden equation, and scattering length calculations. Linearization methods provide piecewise linear ordinary differential equations which can be easily integrated, and provide accurate answers even for hypersingular potentials, for which perturbation methods diverge. It is shown that the accuracy of linearization methods can be substantially improved by employing variable steps which adjust themselves to the solution.     

Lattice Boltzmann schemes for quantum applications

We review the basic ideas behind the quantum lattice Boltzmann equation (LBE), and present a few thoughts on the possible use of such an equation for simulating quantum many-body problems on both (parallel) electronic and quantum computers.