Search on a hypercubic lattice using a quantum random walk. I. d > 2

Random walks describe diffusion processes, where movement at every time step is restricted to only the neighboring locations. We construct a quantum random walk algorithm, based on discretization of the Dirac evolution operator inspired by staggered lattice fermions. We use it to investigate the spatial search problem, that is, to find a marked vertex on a d-dimensional hypercubic lattice. The restriction on movement hardly matters for d > 2, and scaling behavior close to Grover's optimal algorithm (which has no restriction on movement) can be achieved. Using numerical simulations, we optimize the proportionality constants of the scaling behavior, and demonstrate the approach to that for Grover's algorithm (equivalent to the mean-field theory or the d -> infinity limit). In particular, the scaling behavior for d = 3 is only about 25% higher than the optimal d -> infinity value.

Search on a hypercubic lattice using a quantum random walk. II. d = 2

We investigate the spatial search problem on the two-dimensional square lattice, using the Dirac evolution operator discretized according to the staggered lattice fermion formalism. d = 2 is the critical dimension for the spatial search problem, where infrared divergence of the evolution operator leads to logarithmic factors in the scaling behavior. As a result, the construction used in our accompanying article A. Patel and M. A. Rahaman, Phys. Rev. A 82, 032330 (2010)] provides an O(root N ln N) algorithm, which is not optimal. The scaling behavior can be improved to O(root N ln N) by cleverly controlling the massless Dirac evolution operator by an ancilla qubit, as proposed by Tulsi Phys. Rev. A 78, 012310 (2008)]. We reinterpret the ancilla control as introduction of an effective mass at the marked vertex, and optimize the proportionality constants of the scaling behavior of the algorithm by numerically tuning the parameters.

Estimating Frequencies of Minority Nevirapine-Resistant Strains in Chronically HIV-1-Infected Individuals Naive to Nevirapine by Using Stochastic Simulations and a Mathematical Model

Nevirapine forms the mainstay of our efforts to curtail the pediatric AIDS epidemic through prevention of mother-to-child transmission of HIV-1. A key limitation, however, is the rapid selection of HIV-1 strains resistant to nevirapine following the administration of a single dose. This rapid selection of resistance suggests that nevirapine-resistant strains preexist in HIV-1 patients and may adversely affect outcomes of treatment. The frequencies of nevirapine-resistant strains in vivo, however, remain poorly estimated, possibly because they exist as a minority below current assay detection limits. Here, we employ stochastic simulations and a mathematical model to estimate the frequencies of strains carrying different combinations of the common nevirapine resistance mutations K103N, V106A, Y181C, Y188C, and G190A in chronically infected HIV-1 patients naive to nevirapine. We estimate the relative fitness of mutant strains from an independent analysis of previous competitive growth assays. We predict that single mutants are likely to preexist in patients at frequencies (similar to 0.01% to 0.001%) near or below current assay detection limits (>0.01%), emphasizing the need for more-sensitive assays. The existence of double mutants is subject to large stochastic variations. Triple and higher mutants are predicted not to exist. Our estimates are robust to variations in the recombination rate, cellular superinfection frequency, and the effective population size. Thus, with 10(7) to 10(8) infected cells in HIV-1 patients, even when undetected, nevirapine-resistant genomes may exist in substantial numbers and compromise efforts to prevent mother-to-child transmission of HIV-1, accelerate the failure of subsequent antiretroviral treatments, and facilitate the transmission of drug resistance.

Free vibration of a stochastic beam-column using stochastic fem

The free vibrational characteristics of a beam-column, which is having randomly varying Young's modulus and mass density and subjected to randomly distributed axial loading is analysed. The material property fluctuations and axial loadings are considered to constitute independent one-dimensional, uni-variate, homogeneous real, spatially distributed stochastic fields. Hamilton's principle is used to formulate the problem using stochastic FEM. Vibration frequencies and mode shapes are analysed for their statistical descriptions. A numerical example is shown.

Energy efficient asymmetric binary search switching technique for SAR ADC

An asymmetric binary search switching technique for a successive approximation register (SAR) ADC is presented, and trade-off between switching energy and conversion cycles is discussed. Without using any additional switches, the proposed technique consumes 46% less switching energy, for a small input swing (0.5 V-ref (P-P)), as compared to the last reported efficient switching technique in literature for an 8-bit SAR ADC. For a full input swing (2 V-ref (P-P)), the proposed technique consumes 16.5% less switching energy.

Random-Restart Reactive Tabu Search Algorithm for Detection in Large-MIMO Systems

We present a low-complexity algorithm based on reactive tabu search (RTS) for near maximum likelihood (ML) detection in large-MIMO systems. The conventional RTS algorithm achieves near-ML performance for 4-QAM in large-MIMO systems. But its performance for higher-order QAM is far from ML performance. Here, we propose a random-restart RTS (R3TS) algorithm which achieves significantly better bit error rate (BER) performance compared to that of the conventional RTS algorithm in higher-order QAM. The key idea is to run multiple tabu searches, each search starting with a random initial vector and choosing the best among the resulting solution vectors. A criterion to limit the number of searches is also proposed. Computer simulations show that the R3TS algorithm achieves almost the ML performance in 16 x 16 V-BLAST MIMO system with 16-QAM and 64-QAM at significantly less complexities than the sphere decoder. Also, in a 32 x 32 V-BLAST MIMO system, the R3TS performs close to ML lower bound within 1.6 dB for 16-QAM (128 bps/Hz), and within 2.4 dB for 64-QAM (192 bps/Hz) at 10(-3) BER.

Denumerable state stochastic games with limiting average payoff

We study stochastic games with countable state space, compact action spaces, and limiting average payoff. ForN-person games, the existence of an equilibrium in stationary strategies is established under a certain Liapunov stability condition. For two-person zero-sum games, the existence of a value and optimal strategies for both players are established under the same stability condition.

Non-conservatively loaded stochastic columns

A new finite element method is developed to analyse non-conservative structures with more than one parameter behaving in a stochastic manner. As a generalization, this paper treats the subsequent non-self-adjoint random eigenvalue problem that arises when the material property values of the non-conservative structural system have stochastic fluctuations resulting from manufacturing and measurement errors. The free vibration problems of stochastic Beck's column and stochastic Leipholz column whose Young's modulus and mass density are distributed stochastically are considered. The stochastic finite element method that is developed, is implemented to arrive at a random non-self-adjoint algebraic eigenvalue problem. The stochastic characteristics of eigensolutions are derived in terms of the stochastic material property variations. Numerical examples are given. It is demonstrated that, through this formulation, the finite element discretization need not be dependent on the characteristics of stochastic processes of the fluctuations in material property value.

On extremal solutions to stochastic control problems, II

The set of attainable laws of the joint state-control process of a controlled diffusion is analyzed from a convex analytic viewpoint. Various equivalence relations depending on one-dimensional marginals thereof are defined on this set and the corresponding equivalence classes are studied.

Parametric instability of stochastic columns

Columns which have stochastically distributed Young's modulus and mass density and are subjected to deterministic periodic axial loadings are considered. The general case of a column supported on a Winkler elastic foundation of random stiffness and also on discrete elastic supports which are also random is considered. Material property fluctuations are modeled as independent one-dimensional univariate homogeneous real random fields in space. In addition to autocorrelation functions or their equivalent power spectral density functions, the input random fields are characterized by scale of fluctuations or variance functions for their second order properties. The foundation stiffness coefficient and the stiffnesses of discrete elastic supports are treated to constitute independent random variables. The system equations of boundary frequencies are obtained using Bolotin's method for deterministic systems. Stochastic FEM is used to obtain the discrete system with random as well as periodic coefficients. Statistical properties of boundary frequencies are derived in terms of input parameter statistics. A complete covariance structure is obtained. The equations developed are illustrated using a numerical example employing a practical correlation structure.

Snapthrough instability of a stochastic a von Mises truss

A von Mises truss with stochastically varying material properties is investigated for snapthrough instability. The variability of the snap-through load is calculated analytically as a function of the material property variability represented as a stochastic process. The bounds are established which are independent of the knowledge of the complete description of correlation structure which is seldom possible using the experimental data. Two processes are considered to represent the material property variability and the results are presented graphically. Ein von Mises Fachwerk mit stochastisch verteilten Materialeigenschaften wird bezüglich der Durchschlagsinstabilität untersucht. Die Spannbreite der Durchschlagslast wird analytisch als Funktion der Spannbreite der Materialeigenschaften berechnet, die stochastisch verteilt angenommen werden. Eine explizite Gesamtbeschreibung der Struktur ist bei Benutzung experimenteller Daten selten möglich. Deshalb werden Grenzen für die Durchschlagskraft entwickelt, die von der Kenntnis dieser Gesamtbeschreibung unabhängig sind. Zwei Grenzfälle werden betrachtet, um die Spannbreite der Materialeigenschaften darzustellen. Die Ergebnisse werden grafisch dargestellt.

Search Strategies for Multiple UAV Search and Destroy Missions

Multiple UAVs are deployed to carry out a search and destroy mission in a bounded region. The UAVs have limited sensor range and can carry limited resources which reduce with use. The UAVs perform a search task to detect targets. When a target is detected which requires different type and quantities of resources to completely destroy, then a team of UAVs called as a coalition is formed to attack the target. The coalition members have to modify their route to attack the target, in the process, the search task is affected, as search and destroy tasks are coupled. The performance of the mission is a function of the search and the task allocation strategies. Therefore, for a given task allocation strategy, we need to devise search strategies that are efficient. In this paper, we propose three different search strategies namely; random search strategy, lanes based search strategy and grid based search strategy and analyze their performance through Monte-Carlo simulations. The results show that the grid based search strategy performs the best but with high information overhead.

Stochastic Approximation Algorithms for Constrained Optimization via Simulation

We develop four algorithms for simulation-based optimization under multiple inequality constraints. Both the cost and the constraint functions are considered to be long-run averages of certain state-dependent single-stage functions. We pose the problem in the simulation optimization framework by using the Lagrange multiplier method. Two of our algorithms estimate only the gradient of the Lagrangian, while the other two estimate both the gradient and the Hessian of it. In the process, we also develop various new estimators for the gradient and Hessian. All our algorithms use two simulations each. Two of these algorithms are based on the smoothed functional (SF) technique, while the other two are based on the simultaneous perturbation stochastic approximation (SPSA) method. We prove the convergence of our algorithms and show numerical experiments on a setting involving an open Jackson network. The Newton-based SF algorithm is seen to show the best overall performance.