Quantum Algorithms with Fixed Points: The Case of Database Search

The standard quantum search algorithm lacks a feature, enjoyed by many classical algorithms, of having a fixed-point, i.e. a monotonic convergence towards the solution. Here we present two variations of the quantum search algorithm, which get around this limitation. The first replaces selective inversions in the algorithm by selective phase shifts of $\frac{\pi}{3}$. The second controls the selective inversion operations using two ancilla qubits, and irreversible measurement operations on the ancilla qubits drive the starting state towards the target state. Using $q$ oracle queries, these variations reduce the probability of finding a non-target state from $\epsilon$ to $\epsilon^{2q+1}$, which is asymptotically optimal. Similar ideas can lead to robust quantum algorithms, and provide conceptually new schemes for error correction.

Design space exploration of systolic realization of QR factorization on a runtime reconfigurable platform

In the world of high performance computing huge efforts have been put to accelerate Numerical Linear Algebra (NLA) kernels like QR Decomposition (QRD) with the added advantage of reconfigurability and scalability. While popular custom hardware solution in form of systolic arrays can deliver high performance, they are not scalable, and hence not commercially viable. In this paper, we show how systolic solutions of QRD can be realized efficiently on REDEFINE, a scalable runtime reconfigurable hardware platform. We propose various enhancements to REDEFINE to meet the custom need of accelerating NLA kernels. We further do the design space exploration of the proposed solution for any arbitrary application of size n × n. We determine the right size of the sub-array in accordance with the optimal pipeline depth of the core execution units and the number of such units to be used per sub-array.

An operator-splitting finite element method for the efficient parallel solution of multidimensional population balance systems

A finite element method for solving multidimensional population balance systems is proposed where the balance of fluid velocity, temperature and solute partial density is considered as a two-dimensional system and the balance of particle size distribution as a three-dimensional one. The method is based on a dimensional splitting into physical space and internal property variables. In addition, the operator splitting allows to decouple the equations for temperature, solute partial density and particle size distribution. Further, a nodal point based parallel finite element algorithm for multi-dimensional population balance systems is presented. The method is applied to study a crystallization process assuming, for simplicity, a size independent growth rate and neglecting agglomeration and breakage of particles. Simulations for different wall temperatures are performed to show the effect of cooling on the crystal growth. Although the method is described in detail only for the case of d=2 space and s=1 internal property variables it has the potential to be extendable to d+s variables, d=2, 3 and s >= 1. (C) 2011 Elsevier Ltd. All rights reserved.

Intra-molecular hydrogen bonding with organic fluorine in the solution state: Deriving evidence by a two dimensional NMR experiment

The direct evidence for the existence of intra-molecular C-F center dot center dot center dot H-N hydrogen bond in organofluorine molecules, in the liquid state, is derived using NMR spectroscopy by the detection of long range interactions among fluorine, nitrogen and hydrogen atoms. The present study reports the determination of the relative signs and magnitudes of through space and through bond couplings to draw unambiguous evidence on the existence of weak molecular interactions involving organic fluorine. It is a simple, easy to implement, N-15 natural abundant two dimensional heteronuclear N-15-H-1 double quantum-single quantum correlation experiment. The existence of intra-molecular hydrogen bond is conclusively established in the investigated molecules. (C) 2011 Elsevier B.V. All rights reserved.

Performance of a class of multi-robot deploy and search strategies based on centroidal voronoi configurations

This article considers a class of deploy and search strategies for multi-robot systems and evaluates their performance. The application framework used is deployment of a system of autonomous mobile robots equipped with required sensors in a search space to gather information. The lack of information about the search space is modelled as an uncertainty density distribution. The agents are deployed to maximise single-step search effectiveness. The centroidal Voronoi configuration, which achieves a locally optimal deployment, forms the basis for sequential deploy and search (SDS) and combined deploy and search (CDS) strategies. Completeness results are provided for both search strategies. The deployment strategy is analysed in the presence of constraints on robot speed and limit on sensor range for the convergence of trajectories with corresponding control laws responsible for the motion of robots. SDS and CDS strategies are compared with standard greedy and random search strategies on the basis of time taken to achieve reduction in the uncertainty density below a desired level. The simulation experiments reveal several important issues related to the dependence of the relative performances of the search strategies on parameters such as the number of robots, speed of robots and their sensor range limits.

Engagement of CF3 Group in N-H center dot center dot center dot F-C Hydrogen Bond in the Solution State: NMR Spectroscopy and MD Simulation Studies

Unambiguous evidence for the engagement of CF3 group in N-H center dot center dot center dot F-C hydrogen bond in a low polarity solvent, the first observation of its kind, is reported. The presence of such weak molecular interactions in the solution state is convincingly established by one and two-dimensional H-1, F-19, and natural abundant N-15 NMR spectroscopic studies. The strong and direct evidence is derived by the observation of through-space couplings, such as, (1h)J(FH), (1h)J(FN), and (2h)J(FF), where the spin polarization is transmitted through hydrogen bond. In an interesting example of a molecule containing two CF3 groups getting simultaneously involved in hydrogen bond, where hydrogen bond mediated couplings are not reflected in the NMR spectrum, F-19-F-19 NOESY experiment yielded confirmatory evidence. Significant deviations in the strengths of (1)J(NH), variable temperature, and the solvent induced perturbations yielded additional support. The NMR results are corroborated by both DFT calculations and MD simulations, where the quantitative information on different ways of involvement of fluorine in two and three centered hydrogen bonds, their percentage of occurrences, and geometries have been obtained. The hydrogen bond interaction energies have also been calculated.

Analysing modifica-tions in the synthesis of multiple state mechanical devices using configuration space and topology graphs

Automated synthesis of mechanical designs is an important step towards the development of an intelligent CAD system. Research into methods for supporting conceptual design using automated synthesis has attracted much attention in the past decades. In our research, ten experimental studies are conducted to find out how designers synthesize solution concepts for multi-state mechanical devices. The designers are asked to think aloud, while carrying out the synthesis. These design synthesis processes are video recorded. It has been found that modification of kinematic pairs and mechanisms is the major activity carried out by all the designers. This paper presents an analysis of these synthesis processes using configuration space and topology graph to identify and classify the types of modifications that take place. Understanding of these modification processes and the context in which they happened is crucial to develop a system for supporting design synthesis of multiple state mechanical devices that is capable of creating a comprehensive variety of solution alternatives.

A peer-peer particle swarm optimizer

Particle Swarm Optimization is a parallel algorithm that spawns particles across a search space searching for an optimized solution. Though inherently parallel, they have distinct synchronizations points which stumbles attempts to create completely distributed versions of it. In this paper, we attempt to create a completely distributed peer-peer particle swarm optimization in a cluster of heterogeneous nodes. Since, the original algorithm requires explicit synchronization points we modified the algorithm in multiple ways to support a peer-peer system of nodes. We also modify certain aspect of the basic PSO algorithm and show how certain numerical problems can take advantage of the same thereby yielding fast convergence.

Feature Search in the Grassmanian in Online Reinforcement Learning

We consider the problem of finding the best features for value function approximation in reinforcement learning and develop an online algorithm to optimize the mean square Bellman error objective. For any given feature value, our algorithm performs gradient search in the parameter space via a residual gradient scheme and, on a slower timescale, also performs gradient search in the Grassman manifold of features. We present a proof of convergence of our algorithm. We show empirical results using our algorithm as well as a similar algorithm that uses temporal difference learning in place of the residual gradient scheme for the faster timescale updates.

Does linear separability really matter? Complex visual search is explained by simple search

Visual search in real life involves complex displays with a target among multiple types of distracters, but in the laboratory, it is often tested using simple displays with identical distracters. Can complex search be understood in terms of simple searches? This link may not be straightforward if complex search has emergent properties. One such property is linear separability, whereby search is hard when a target cannot be separated from its distracters using a single linear boundary. However, evidence in favor of linear separability is based on testing stimulus configurations in an external parametric space that need not be related to their true perceptual representation. We therefore set out to assess whether linear separability influences complex search at all. Our null hypothesis was that complex search performance depends only on classical factors such as target-distracter similarity and distracter homogeneity, which we measured using simple searches. Across three experiments involving a variety of artificial and natural objects, differences between linearly separable and nonseparable searches were explained using target-distracter similarity and distracter heterogeneity. Further, simple searches accurately predicted complex search regardless of linear separability (r = 0.91). Our results show that complex search is explained by simple search, refuting the widely held belief that linear separability influences visual search.

Filling-in Void and Sparse Regions in Protein Sequence Space by Protein-Like Artificial Sequences Enables Remarkable Enhancement in Remote Homology Detection Capability

Protein functional annotation relies on the identification of accurate relationships, sequence divergence being a key factor. This is especially evident when distant protein relationships are demonstrated only with three-dimensional structures. To address this challenge, we describe a computational approach to purposefully bridge gaps between related protein families through directed design of protein-like ``linker'' sequences. For this, we represented SCOP domain families, integrated with sequence homologues, as multiple profiles and performed HMM-HMM alignments between related domain families. Where convincing alignments were achieved, we applied a roulette wheel-based method to design 3,611,010 protein-like sequences corresponding to 374 SCOP folds. To analyze their ability to link proteins in homology searches, we used 3024 queries to search two databases, one containing only natural sequences and another one additionally containing designed sequences. Our results showed that augmented database searches showed up to 30% improvement in fold coverage for over 74% of the folds, with 52 folds achieving all theoretically possible connections. Although sequences could not be designed between some families, the availability of designed sequences between other families within the fold established the sequence continuum to demonstrate 373 difficult relationships. Ultimately, as a practical and realistic extension, we demonstrate that such protein-like sequences can be ``plugged-into'' routine and generic sequence database searches to empower not only remote homology detection but also fold recognition. Our richly statistically supported findings show that complementary searches in both databases will increase the effectiveness of sequence-based searches in recognizing all homologues sharing a common fold. (C) 2013 Elsevier Ltd. All rights reserved.

Optimal trajectory planning for path convergence in three-dimensional space

This article addresses the problem of determining the shortest path that connects a given initial configuration (position, heading angle, and flight path angle) to a given rectilinear or a circular path in three-dimensional space for a constant speed and turn-rate constrained aerial vehicle. The final path is assumed to be located relatively far from the starting point. Due to its simplicity and low computational requirements the algorithm can be implemented on a fixed-wing type unmanned air vehicle in real time in missions where the final path may change dynamically. As wind has a very significant effect on the flight of small aerial vehicles, the method of optimal path planning is extended to meet the same objective in the presence of wind comparable to the speed of the aerial vehicles. But, if the path to be followed is closer to the initial point, an off-line method based on multiple shooting, in combination with a direct transcription technique, is used to obtain the optimal solution. Optimal paths are generated for a variety of cases to show the efficiency of the algorithm. Simulations are presented to demonstrate tracking results using a 6-degrees-of-freedom model of an unmanned air vehicle.

Successful data recovery from oscillation photographs containing strong polycrystalline diffraction rings from an unknown small-molecule contaminant: preliminary structure solution of Salmonella typhimurium pyridoxal kinase (PdxK)

Pyridoxal kinase (PdxK; EC 2.7.1.35) belongs to the phosphotransferase family of enzymes and catalyzes the conversion of the three active forms of vitamin B-6, pyridoxine, pyridoxal and pyridoxamine, to their phosphorylated forms and thereby plays a key role in pyridoxal 5 `-phosphate salvage. In the present study, pyridoxal kinase from Salmonella typhimurium was cloned and overexpressed in Escherichia coli, purified using Ni-NTA affinity chromatography and crystallized. X-ray diffraction data were collected to 2.6 angstrom resolution at 100 K. The crystal belonged to the primitive orthorhombic space group P2(1)2(1)2(1), with unitcell parameters a = 65.11, b = 72.89, c = 107.52 angstrom. The data quality obtained by routine processing was poor owing to the presence of strong diffraction rings caused by a polycrystalline material of an unknown small molecule in all oscillation images. Excluding the reflections close to powder/polycrystalline rings provided data of sufficient quality for structure determination. A preliminary structure solution has been obtained by molecular replacement with the Phaser program in the CCP4 suite using E. coli pyridoxal kinase (PDB entry 2ddm) as the phasing model. Further refinement and analysis of the structure are likely to provide valuable insights into catalysis by pyridoxal kinases.

Exact Solution of the PPP Model for Correlated Electronic States of Tetracene and Substituted Tetracene

Tetracene is an important conjugated molecule for device applications. We have used the diagrammatic valence bond method to obtain the desired states, in a Hilbert space of about 450 million singlets and 902 million triplets. We have also studied the donor/acceptor (D/A)-substituted tetracenes with D and A groups placed symmetrically about the long axis of the molecule. In these cases, by exploiting a new symmetry, which is a combination of C-2 symmetry and electron-hole symmetry, we are able to obtain their low-lying states. In the case of substituted tetracene, we find that optically allowed one-photon excitation gaps reduce with increasing D/A strength, while the lowest singlet triplet gap is only wealdy affected. In all the systems we have studied, the excited singlet state, S-i, is at more than twice the energy of the lowest triplet state and the second triplet is very close to the S-1 state. Thus, donor-acceptor-substituted tetracene could be a good candidate in photovoltaic device application as it satisfies energy criteria for singlet fission. We have also obtained the model exact second harmonic generation (SHG) coefficients using the correction vector method, and we find that the SHG responses increase with the increase in D/A strength.

Frequency Domain Based Solution for Certain Class of Wave Equations: An exhaustive study of Numerical Solutions

The paper discusses the frequency domain based solution for a certain class of wave equations such as: a second order partial differential equation in one variable with constant and varying coefficients (Cantilever beam) and a coupled second order partial differential equation in two variables with constant and varying coefficients (Timoshenko beam). The exact solution of the Cantilever beam with uniform and varying cross-section and the Timoshenko beam with uniform cross-section is available. However, the exact solution for Timoshenko beam with varying cross-section is not available. Laplace spectral methods are used to solve these problems exactly in frequency domain. The numerical solution in frequency domain is done by discretisation in space by approximating the unknown function using spectral functions like Chebyshev polynomials, Legendre polynomials and also Normal polynomials. Different numerical methods such as Galerkin Method, Petrov- Galerkin method, Method of moments and Collocation method or the Pseudo-spectral method in frequency domain are studied and compared with the available exact solution. An approximate solution is also obtained for the Timoshenko beam with varying cross-section using Laplace Spectral Element Method (LSEM). The group speeds are computed exactly for the Cantilever beam and Timoshenko beam with uniform cross-section and is compared with the group speeds obtained numerically. The shear mode and the bending modes of the Timoshenko beam with uniform cross-section are separated numerically by applying a modulated pulse as the shear force and the corresponding group speeds for varying taper parameter in are obtained numerically by varying the frequency of the input pulse. An approximate expression for calculating group speeds corresponding to the shear mode and the bending mode, and also the cut-off frequency is obtained. Finally, we show that the cut-off frequency disappears for large in, for epsilon > 0 and increases for large in, for epsilon < 0.