In ensemble (or bulk) quantum computation, all computations are performed on an ensemble of computers rather than on a single computer. Measurements of qubits in an individual computer cannot be performed; instead, only expectation values (over the complete ensemble of computers) can be measured. As a result of this limitation on the model of computation, many algorithms cannot be processed directly on such computers, and must be modified, as the common strategy of delaying the measurements usually does not resolve this ensemble-measurement problem. Here we present several new strategies for resolving this problem. Based on these strategies we provide new versions of some of the most important quantum algorithms, versions that are suitable for implementing on ensemble quantum computers, e.g., on liquid NMR quantum computers. These algorithms are Shor's factorization algorithm, Grover's search algorithm (with several marked items), and an algorithm for quantum fault-tolerant computation. The first two algorithms are simply modified using a randomizing and a sorting strategies. For the last algorithm, we develop a classical-quantum hybrid strategy for removing measurements. We use it to present a novel quantum fault-tolerant scheme. More explicitly, we present schemes for fault-tolerant measurement-free implementation of Toffoli and σ(z)(¼) as these operations cannot be implemented "bitwise", and their standard fault-tolerant implementations require measurement.

Embedded systems are becoming highly complex and increasingly being used in critical applications. Integrated system health management (ISHM) techniques have therefore been developed to ensure the proper operation of these systems. However, some ISHM systems are relatively complex and may consume a significant amount of resources. In some situations, activating the full ISHM system may cause resource contention and prevents the target system from timely completing critical tasks. Thus, it is imperative to introduce the notion of adaptivity into ISHM systems. This paper systematically discusses the issues that need to be addressed in an adaptive ISHM system with a focus on adaptation in terms of QoS aspects. A novel model, adaptive diagnosis quality-oriented system model (ADQSM), is proposed to model the QoS specification and fault diagnosis quality measurement issues as well as the abstraction of the adaptation problem. We then present the method to evaluate various diagnosability attributes based on a modified fault signature matrix. We further map the ADQSM model to the particle swarm optimization (PSO) problem model and use PSO for rapid configuration decision making

The G4-FET, a four-gate transistor compatible with standard silicon-on-insulator (SOI) CMOS technology, provides unique opportunities as a logic device. Combining both JFET- and MOSFET-like actions within one transistor body, the G4-FET offers two side (lateral) junction-based gates, a top MOS gate, and a MOS back gate that is activated by SOI substrate biasing. The G4-FET's conduction characteristics are controlled by the combined interaction of these four gates. In this paper, the G4-FET is demonstrated as a logic device, resulting in a universal and programmable logic gate that can lead to the design of more efficient logic circuits. As an example, we present a new full adder design based on the G4-FET that is significantly more efficient than conventional designs.

In ensemble (or bulk) quantum computation, all computations are performed on an ensemble of computers rather than on a single computer. Measurements of qubits in an individual computer cannot be performed; instead, only expectation values (over the complete ensemble of computers) can be measured. As a result of this limitation on the model of computation, many algorithms cannot be processed directly on such computers, and must be modified. We provide modification of the fault tolerant quantum computation protocols to enable processing on ensemble quantum computers.

Each probabilistic automaton M over an alphabet $\cal A$ defines a probability measure $\prob_M$ on the set of all finite and infinite words over $\cal A$. We can identify a k letter alphabet $\cal A$ with the set {0,1,…,k-1}, and, hence, we can consider every finite or infinite word w over $\cal A$ as a radix k expansion of a real number X(w) in the interval [0,1]. This makes X(w) a random variable and the distribution function of M is defined as usual: F(x):=\prob_M{w : X(w)

We show that Nechiporuk's method [I. Wegener, The Complexity of Boolean Functions, Teubner-Wiley, New York, 1987] for proving lower bounds for Boolean formulas can be extended to the quantum case. This leads to an $\Omega(n^2/\log^2 n)$ lower bound for quantum formulas computing an explicit function. The only known previous explicit lower bound for quantum formulas [A. Yao, Proceedings of 34th IEEE Symposium on Foundations of Computer Science, IEEE Computer Society Press, Los Alamitos, CA, 1993, pp. 352--361] states that the majority function does not have a linear-size quantum formula. We also show that quantum formulas can be simulated by Boolean circuits of almost the same size.

Upper bounds are given for the weight distribution of binary weakly self-dual codes. To get these new bounds, we introduce a novel method of utilizing unitary operations on Hilbert spaces. This method is motivated by recent progress on quantum computing. This new approach leads to much simpler proofs for such genre of bounds on the weight distributions of certain classes of codes. Moreover, in some cases, our bounds are improvements on the earlier bounds. These improvements are achieved either by extending the range of the weights over which the bounds apply or by extending the class of codes subjected to these bounds.

A novel universal and fault-tolerant basis (set of gates) for quantum computation is described. Such a set is necessary to perform quantum computation in a realistic noisy environment. The new basis consists of two single-qubit gates (Hadamard and /spl sigma//sub z//sup 1/4 /) and one double-qubit gate (Controlled-NOT). Since the set consisting of Controlled-NOT and Hadamard gates is not universal, the new basis achieves universality by including only one additional elementary (in the sense that it does not include angles that are irrational multiples of /spl pi/) single-qubit gate, and hence, is potentially the simplest universal basis that one can construct. We also provide an alternative proof of universality for the only other known class of universal and fault-tolerant basis proposed by P.W. Shor (1996) and A.Y. Kitaev (1997).

We explore the design of quantum error-correcting codes for cases where the decoherence events of qubits are correlated. In particular, we consider the case where only spatially contiguous qubits decohere, which is analogous to the case of burst errors in classical coding theory. We present several different efficient schemes for constructing families of such codes. For example, one can find one-dimensional quantum codes of length n=13 and 15 that correct burst errors of width b<3; as a comparison, a random-error correcting quantum code that corrects t=3 errors must have length n/spl ges/17. In general, we show that it is possible to build quantum burst-correcting codes that have near optimal dimension. For example, we show that for any constant b, there exist b-burst-correcting quantum codes with length n, and dimension k=n-log n-O(1); as a comparison, the Hamming bound for the case with t (constant) random errors yields k/spl les/n-tlog n+O(1).

We consider the complexity of computing Boolean functions by analog circuits of bounded fan-in, i.e. by circuits of gates computing real-valued functions, either exactly or as a sign-representation. Sharp upper bounds are obtained for the complexity of the most difficult n-variable function over certain bases (sign-representation by arithmetic circuits and exact computation by piecewise linear circuits). Bounds are given for the computational power gained by adding discontinuous gate functions and nondeterminism. We also prove explicit nonlinear lower bounds for the formula size of analog circuits over bases containing addition, subtraction, multiplication, the sign function and all real constants.>