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.     

Simulation of n-qubit quantum systems. V. Quantum measurements

The Feynman program has been developed during the last years to support case studies on the dynamics and entanglement of n-qubit quantum registers. Apart from basic transformations and (gate) operations, it currently supports a good number of separability criteria and entanglement measures, quantum channels as well as the parametrizations of various frequently applied objects in quantum information theory, such as (pure and mixed) quantum states, hermitian and unitary matrices or classical probability distributions. With the present update of the Feynman program, we provide a simple access to (the simulation of) quantum measurements. This includes not only the widely-applied projective measurements upon the eigenspaces of some given operator but also single-qubit measurements in various pre- and user-defined bases as well as the support for two-qubit Bell measurements. In addition, we help perform generalized and POVM measurements. Knowing the importance of measurements for many quantum information protocols, e.g., one-way computing, we hope that this update makes the Feynman code an attractive and versatile tool for both, research and education.

New version program summary

Program title: FEYNMANCatalogue identifier: ADWE_v5_0Program summary URL:http://cpc.cs.qub.ac.uk/summaries/ADWE_v5_0.htmlProgram obtainable from: CPC Program Library, Queen's University, Belfast, N. IrelandLicensing provisions: Standard CPC licence, http://cpc.cs.qub.ac.uk/licence/licence.htmlNo. of lines in distributed program, including test data, etc.: 27 210No. of bytes in distributed program, including test data, etc.: 1 960 471Distribution format: tar.gzProgramming language: Maple 12Computer: Any computer with Maple software installedOperating system: Any system that supports Maple; the program has been tested under Microsoft Windows XP and LinuxClassification: 4.15Catalogue identifier of previous version: ADWE_v4_0Journal reference of previous version: Comput. Phys. Commun. 179 (2008) 647Does the new version supersede the previous version?: YesNature of problem: During the last decade, the field of quantum information science has largely contributed to our understanding of quantum mechanics, and has provided also new and efficient protocols that are used on quantum entanglement. To further analyze the amount and transfer of entanglement in n-qubit quantum protocols, symbolic and numerical simulations need to be handled efficiently.Solution method: Using the computer algebra system Maple, we developed a set of procedures in order to support the definition, manipulation and analysis of n-qubit quantum registers. These procedures also help to deal with (unitary) logic gates and (nonunitary) quantum operations and measurements that act upon the quantum registers. All commands are organized in a hierarchical order and can be used interactively in order to simulate and analyze the evolution of n-qubit quantum systems, both in ideal and noisy quantum circuits.Reasons for new version: Until the present, the FEYNMAN program supported the basic data structures and operations of n-qubit quantum registers [1], a good number of separability and entanglement measures [2], quantum operations (noisy channels) [3] as well as the parametrizations of various frequently applied objects, such as (pure and mixed) quantum states, hermitian and unitary matrices or classical probability distributions [4]. With the current extension, we here add all necessary features to simulate quantum measurements, including the projective measurements in various single-qubit and the two-qubit Bell basis, and POVM measurements. Together with the previously implemented functionality, this greatly enhances the possibilities of analyzing quantum information protocols in which measurements play a central role, e.g., one-way computation.Running time: Most commands require ?10 seconds of processor time on a Pentium 4 processor with ?2 GHz RAM or newer, if they work with quantum registers with five or less qubits. Moreover, about 5-20 MB of working memory is typically needed (in addition to the memory for the Maple environment itself). However, especially when working with symbolic expressions, the requirements on the CPU time and memory critically depend on the size of the quantum registers owing to the exponential growth of the dimension of the associated Hilbert space. For example, complex (symbolic) noise models, i.e. with several Kraus operators, may result in very large expressions that dramatically slow down the evaluation of e.g. distance measures or the final-state entropy, etc. In these cases, Maple's assume facility sometimes helps to reduce the complexity of the symbolic expressions, but more often than not only a numerical evaluation is feasible. Since the various commands can be applied to quite different scenarios, no general scaling rule can be given for the CPU time or the request of memory.References:

[1] T. Radtke, S. Fritzsche, Comput. Phys. Commun. 173 (2005) 91.

[2] T. Radtke, S. Fritzsche, Comput. Phys. Commun. 175 (2006) 145.

[3] T. Radtke, S. Fritzsche, Comput. Phys. Commun. 176 (2007) 617.

[4] T. Radtke, S. Fritzsche, Comput. Phys. Commun. 179 (2008) 647.

     

Effective RCA design using quantum dot cellular automata

Quantum dot Cellular Automata (QCA) is a transistor less technology alternative to CMOS for developing low-power, high speed digital circuits. Adder circuits are broadly employed in all digital computation systems. In this paper, a novel coplanar QCA full adder circuit is proposed which is designed with minimum number of QCA cells. The proposed full adder requires only 13 QCA cells, an area of 0.008 μm² and delay of about 2 clock cycles to implement its function. Then an efficient 4-bit Ripple Carry Adder (RCA) is designed based on the proposed full adder that performs higher end addition in an effective way. Simulations results are obtained precisely using QCA designer tool version 2.0.3. Also the simulation results shows that the proposed 4-bit Ripple Carry Adder (RCA) requires only 70 QCA cells, an area of 0.18 μm² and delay of about 5 clock cycles to implement its function with enhanced performance in terms of latency, area and QCA Cost. From the comparisons, it is found that our work achieves over 55% improvement in QCA cell count.     

Simulation of forest fire fronts using cellular automata

In this work a new model for fire front spreading based on two-dimensional cellular automata is proposed. It is a more realistic modification of the model introduced by Karafyllidis and Thanailakis (see [Karafyllidis I, Thanailakis A. A model for predicting forest fire spreading using cellular automata. Ecol Model 1997;99:87–97]), which is based on the transfer of fractional burned area. Specifically, the model proposed in this work introduces a more accurate factor of propagation from a diagonal neighbor cell and includes, in a detailed form, the rate of fire spread. Moreover, the model is useful for both homogeneous and inhomogeneous environments. Some tests have been passed in order to determine the goodness of the method.     

An overview of quantum cellular automata

Quantum cellular automata are arrays of identical finite-dimensional quantum systems, evolving in discrete-time steps by iterating a unitary operator G. Moreover the global evolution G is required to be causal (it propagates information at a bounded speed) and translation-invariant (it acts everywhere the same). Quantum cellular automata provide a model/architecture for distributed quantum computation. More generally, they encompass most of discrete-space discrete-time quantum theory. We give an overview of their theory, with particular focus on structure results; computability and universality results; and quantum simulation results.

     

Quantum game simulator, using the circuit model of quantum computation

We present a general two-player quantum game simulator that can simulate any two-player quantum game described by a 2×2 payoff matrix (two strategy games).The user can determine the payoff matrices for both players, their strategies and the amount of entanglement between their initial strategies. The outputs of the simulator are the expected payoffs of each player as a function of the other player's strategy parameters and the amount of entanglement. The simulator also produces contour plots that divide the strategy spaces of the game in regions in which players can get larger payoffs if they choose to use a quantum strategy against any classical one. We also apply the simulator to two well-known quantum games, the Battle of Sexes and the Chicken game.

Program summary

Program title: Quantum Game Simulator (QGS)Catalogue identifier: AEED_v1_0Program summary URL:http://cpc.cs.qub.ac.uk/summaries/AEED_v1_0.htmlProgram obtainable from: CPC Program Library, Queen's University, Belfast, N. IrelandLicensing provisions: Standard CPC licence, http://cpc.cs.qub.ac.uk/licence/licence.htmlNo. of lines in distributed program, including test data, etc.: 3416No. of bytes in distributed program, including test data, etc.: 583 553Distribution format: tar.gzProgramming language: Matlab R2008a (C)Computer: Any computer that can sufficiently run Matlab R2008aOperating system: Any system that can sufficiently run Matlab R2008aClassification: 4.15Nature of problem: Simulation of two player quantum games described by a payoff matrix.Solution method: The program calculates the matrices that comprise the Eisert setup for quantum games based on the quantum circuit model. There are 5 parameters that can be altered. We define 3 of them as constant. We play the quantum game for all possible values for the other 2 parameters and store the results in a matrix.Unusual features: The software provides an easy way of simulating any two-player quantum games.Running time: Approximately 0.4 sec (Region Feature) and 0.3 sec (Payoff Feature) on a Intel Core 2 Duo GHz with 2 GB of memory under Windows XP.     

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.     

Intrinsically universal n-dimensional quantum cellular automata

Several non-axiomatic approaches have been taken to define Quantum Cellular Automata (QCA); Partitioned QCA (PQCA) are the most canonical. Here we show any QCA can be put into PQCA form. Our construction reconciles the non-axiomatic definitions of QCA, showing that they can all simulate one another, thus they are all equivalent to the axiomatic definition. A simple n-dimensional QCA capable of simulating all others to arbitrary precision is described, where the initial configuration and the evolution of any QCA can be encoded within the initial configuration of the intrinsically universal QCA. Several steps then correspond to one step of the simulated QCA, achieved via a non-trivial reduction of the problem to universality in quantum circuits. Results are formalised by defining generalised n-dimensional intrinsic simulation, preserving topology in that each cell of the simulated QCA is encoded as a group of adjacent cells in the universal QCA. Implications are discussed.     

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.     

Partitioned quantum cellular automata are intrinsically universal

There have been several non-axiomatic approaches taken to define quantum cellular automata (QCA). Partitioned QCA (PQCA) are the most canonical of these non-axiomatic definitions. In this work we show that any QCA can be put into the form of a PQCA. Our construction reconciles all the non-axiomatic definitions of QCA, showing that they can all simulate one another, and hence that they are all equivalent to the axiomatic definition. This is achieved by defining generalised n-dimensional intrinsic simulation, which brings the computer science based concepts of simulation and universality closer to theoretical physics. The result is not only an important simplification of the QCA model, it also plays a key role in the identification of a minimal n-dimensional intrinsically universal QCA.     

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.     

Static hazard elimination for a logical circuit using quantum dot cellular automata

Microsystem Technologies - Quantum dot cellular automata (QCA) is an upcoming nano-technology for its high speed and low power operation in the field of nano-science and nano-electronics. As QCA...     

Optimal demultiplexer unit design and energy estimation using quantum dot cellular automata

The Journal of Supercomputing - Quantum dot cellular automata (QCA)-based demultiplexer or DeMUX is a basic module of nanocommunication and nanocomputation, like a multiplexer. However, the design...     

Simulation of dynamic phenomena by cellular automata

This paper is aimed at showing how cellular automata can be conveniently employed to simulate dynamic phenomena, typically involving transportation, diffusion, or propagation problems. A cellular automaton can be viewed as made of two parts: a computational engine based on a proper discretization of the domain and charged with correctness and consistency controls, and a dynamic model constituted by transition functions that express cell behaviour. The adoption of cellular automata introduces a new means of spatial data modelling, in addition to those traditionally provided by GIS packages, resulting in the possibility of storing elements of dynamic knowledge in cellular maps: each cell is provided with the attributes that constitute its state, and groups of cells with the functions that describe their mutual interaction. The basic characteristics of cellular automata are discussed with reference to a significant application case, the study of tide propagation over a lagoon.     

Massively parallel quantum computer simulator

We describe portable software to simulate universal quantum computers on massive parallel computers. We illustrate the use of the simulation software by running various quantum algorithms on different computer architectures, such as a IBM BlueGene/L, a IBM Regatta p690+, a Hitachi SR11000/J1, a Cray X1E, a SGI Altix 3700 and clusters of PCs running Windows XP. We study the performance of the software by simulating quantum computers containing up to 36 qubits, using up to 4096 processors and up to 1 TB of memory. Our results demonstrate that the simulator exhibits nearly ideal scaling as a function of the number of processors and suggest that the simulation software described in this paper may also serve as benchmark for testing high-end parallel computers.     

Pyroclastic flows modelling using cellular automata

Cellular automata (CA) and derived computational paradigms represent an alternative approach to differential equations to model and simulating complex fluid dynamical systems, whose evolution depends on the local interactions of their constituent parts. A new notion of CA was developed according to an empirical method for modelling macroscopic phenomena; its application to PYR, a CA model for simulating pyroclastic flows, generated PYR2, which permitted an improvement of the model and a more efficient implementation. PYR2 was utilised for the 1991 eruption of Mt. Pinatubo in the Philippines islands and for the 1996 eruption of the Soufriere Hills in the Montserrat Island. Results of the simulations are satisfactory if the comparison between real and simulated event is performed, considering the area involved by the event and the variations of thickness of the deposit, as generated by collapsing volcanic columns.     

Text compression using two-dimensional cellular automata

This paper presents an elegant mathematical model using simple matrix algebra for characterising the behaviour of two-dimensional nearest neighbourhood linear cellular automata with periodic boundary conditions. Based on this mathematical model, the VLSI architecture of a Cellular Automata Machine (CAM) has been proposed for text compression. Experimental results of comparisons with adaptive Huffman coding scheme also presented.     

Simulation of one-way cellular automata by boolean circuits

We present a relationship between two major models of parallel computation: the one-way cellular automata and the boolean circuits. The starting point is the boolean circuit of small depth designed by Ladner and Fischer to simulate any rational transducer. We extend this construction to simulate one-way cellular automata by boolean circuits.