On estimation of the probability of absence of collisions of some random mappings

Let X and Y be finite sets and φ: (X,Y) →Y be a mapping. Consider a random mapping i → φ(x_i,y_i), where x_i are arbitrarily chosen from the set X, whereas (y_i) is a random sample from Y without replacement. A two-sided bound is derived for the probability of absence of collisions of this mapping. A case of mapping, defined as φ(x, y)=x+ y modulo n, is considered in particular. The results may be used in the selection of identification codes. Translated from Kibernetika i Sistemnyi Analiz, No. 1, pp. 132–137, January–February, 2000.     

Quantum Search with Variable Times

Since Grover’s seminal work, quantum search has been studied in great detail. In the usual search problem, we have a collection of n items x ₁,…,x _n and we would like to find i:x _i =1. We consider a new variant of this problem in which evaluating x _i for different i may take a different number of time steps.     

Continuous-time quantum walks on semi-regular spidernet graphs via quantum probability theory

We analyze continuous-time quantum and classical random walk on spidernet lattices. In the framework of Stieltjes transform, we obtain density of states, which is an efficiency measure for the performance of classical and quantum mechanical transport processes on graphs, and calculate the spacetime transition probabilities between two vertices of the lattice. Then we analytically show that there are two power law decays ∼ t ⁻³ and ∼ t ^−1.5 at the beginning of the transport for transition probability in the continuous-time quantum and classical random walk, respectively. This results illustrate the decay of quantum mechanical transport processes is quicker than that of the classical one. Due to the result, the characteristic time t _c , which is the time when the first maximum of the probabilities occur on an infinite graph, for the quantum walk is shorter than that of the classical walk. Therefore, we can interpret that the quantum transport speed on spidernet is faster than that of the classical one. In the end, we investigate the results by numerical analysis for two examples.     

Scope Dominance with Upward Monotone Quantifiers

We give a complete characterization of the class of upward monotone generalized quantifiers Q₁ and Q₂ over countable domains that satisfy the scheme Q₁ x Q₂ y φ → Q₂ y Q₁ x φ. This generalizes the characterization of such quantifiers over finite domains, according to which the scheme holds iff Q₁ is ∃ or Q₂ is ∀ (excluding trivial cases). Our result shows that in infinite domains, there are more general types of quantifiers that support these entailments.     

Quantum Information and the PCP Theorem

Our main result is that the membership x∈SAT (for x of length n) can be proved by a logarithmic-size quantum state |Ψ〉, together with a polynomial-size classical proof consisting of blocks of length polylog(n) bits each, such that after measuring the state |Ψ〉 the verifier only needs to read one block of the classical proof. This shows that if a short quantum witness is available then a (classical) PCP with only one query is possible. Our second result is that the class QIP/qpoly contains all languages. That is, for any language L (even non-recursive), the membership x∈L (for x of length n) can be proved by a polynomial-size quantum interactive proof, where the verifier is a polynomial-size quantum circuit with working space initiated with some quantum state |Ψ _L,n 〉 (depending only on L and n). Moreover, the interactive proof that we give is of only one round, and the messages communicated are classical. The advice |Ψ _L,n 〉 given to the verifier can also be replaced by a classical probabilistic advice, as long as this advice is kept as a secret from the prover. Our result can hence be interpreted as: the class IP/rpoly contains all languages. For the proof of the second result, we introduce the quantum low-degree-extension of a string of bits. The main result requires an additional machinery of quantum low-degree-test. R. Raz’s research was supported by Israel Science Foundation (ISF) grant.     

Electrical properties and crystallization behavior of Sb<Subscript><Emphasis Type="Italic">x</Emphasis></Subscript>Se<Subscript>100−<Emphasis Type="Italic">x</Emphasis></Subscript> thin films

The structural transformation and transformation kinetics of Sb _x Se_100−x films (60 ≤ x ≤ 70) were studied to investigate the feasibility of applying Sb _x Se_100−x alloys in phase-change nonvolatile memories. The temperature-dependent van der Pauw measurements, Hall measurements, X-ray diffraction and a static tester were used to investigate the electrical properties and crystallization behavior of the Sb _x Se_100−x films. The sheet resistance difference between amorphous and crystalline state was higher than 10⁴ Ω per square According to Hall measurement, Sb _x Se_100−x films have p-type conduction and the Hall mobility and carrier concentration increases with the increase in Sb content. The crystalline structure of the metastable phase of Sb _x Se_100−x alloys, which plays a major roll in fast crystallization, is similar to that of Sb₂Te (rhombohedral structure). The transition temperature, sheet resistance and activation energy for transformation decrease as the amount of Sb increases in the Sb _x Se_100−x film. Applying the Kissinger method, the activation energies for crystallization were in the range from 1.90 ± 0.15 to 4.16 ± 0.28 eV. The desired crystallization speed can be obtained by a systematic change of the composition owing to the variation of the activation barrier with stoichiometry.     

On the bottom summation

We consider summation of consecutive values (φ(v), φ(v + 1), ..., φ(w) of a meromorphic function φ(z), where v, w ∈ ℤ. We assume that φ(z) satisfies a linear difference equation L(y) = 0 with polynomial coefficients, and that a summing operator for L exists (such an operator can be found—if it exists—by the Accurate Summation algorithm, or, alternatively, by Gosper’s algorithm when ordL = 1). The notion of bottom summation which covers the case where φ(z) has poles in ℤ is introduced. The text was submitted by the authors in English.     

Complexities of Homomorphism and Isomorphism for Definite Logic Programs

A homomorphism (?) of logic programs from P to P' is a function mapping Atoms(P) to Atoms(P') and it preserves complements and program clauses. For each definite program clause a←a1,...,an∈P it implies that (?)(a)←(?)(a1),...,(?)(an) is a program clause of P'. A homomorphism (?) is an isomorphism if (?) is a bijection. In this paper, the complexity of the decision problems on homomorphism and isomorphism for definite logic programs is studied. It is shown that the homomorphism problem (HOM-LP) for definite logic programs is NP-complete, and the isomorphism problem (ISO-LP) is equivalent to the graph isomorphism problem (GI).     

On the rate of convergence of 2-term recursions in ℝ d

LetG be a compact set in ℝ ^d d≥1,M=G×G andϕ:M →G a map inC ₃(M). Suppose thatϕ has a fixed pointξ, i.e.ϕ(ξ, ξ)=ξ. We investigate the rate of convergence of the iterationx ⁿ⁺²=φ(x ⁿ⁺¹,x ⁿ) withx ⁰,x ¹∈G andx ⁿ→ξ. Iff _n=Q‖x ⁿ−ξ‖ with a suitable norm and a constantQ depending onξ, an exact representation forf _n is derived. The error terms satisfyf _2m+1≍(ƒ_2m)^γ,f _2m+2≍(ƒ_2m+1)^2γ,m≥0, with 1<gg<2, andγ=γ(x ¹,x ⁰). According to our main result we have lim_n→∞{‖x ⁿ⁺²‖/(‖x ⁿ‖)²}=Q, 0<Q<∞. This paper constitutes an extension of a part of the author’s doctoral thesis realized under the direction of Prof. E. Wirsing and Prof. A. Peyerimhoff, University of Ulm (Germany).     

Accurate evaluation of divided differences for polynomial interpolation of exponential propagators

In this paper, we propose an approach to the computation of more accurate divided differences for the interpolation in the Newton form of the matrix exponential propagator φ(hA)v, φ (z) = (e ^z − 1)/z. In this way, it is possible to approximate φ (hA)v with larger time step size h than with traditionally computed divided differences, as confirmed by numerical examples. The technique can be also extended to “higher” order φ _k functions, k≥0.     

Superpositions of continuous functions defined on a Baire space

We consider uniformly continuous functions on a Baire space and introduce the notion of a continuity modulus of a function. We formulate a condition on the growth of the continuity modulus φ guaranteeing that superpositions of n-ary functions with continuity modulus φ do not exhaust all (n + 1)-ary functions with continuity modulus φ for any n. Moreover, negating this property leads to the inverse effect.     

Asymmetric quantum Reed-Solomon and generalized Reed-Solomon codes

Two new families of asymmetric quantum codes are constructed in this paper. The first one is derived from the Calderbank-Shor-Steane (CSS) construction applied to classical Reed-Solomon (RS) codes, providing quantum codes with parameters [[N = l(q ^l −1), K = l(q ^l −2d + c + 1), d _z ≥ d/d _x ≥ (d−c)]] _q , where q is a prime power and d > c + 1, c ≥ 1, l ≥ 1 are integers. The second family is derived from the CSS construction applied to classical generalized RS codes, generating quantum codes with parameters [[N = mn, K = m(2k−n + c), d _z ≥ d/d _x ≥ (d−c)]] _q , where q is a prime power, 1 < k < n < 2k + c ≤ q ^m , k = n − d + 1, and n, d > c + 1, c ≥ 1, m ≥ 1 are integers. Although the second proposed construction generalizes the first one, the techniques developed in both constructions are slightly different. These new codes have parameters better than or comparable to the ones available in the literature. Additionally, the proposed codes can be utilized in quantum channels having great asymmetry, that is, quantum channels in which the probability of occurrence of phase-shift errors is large when compared to the probability of occurrence of qudit-flip errors.     

Unimodality,Independence Lead to NP-Hardness of Interval Probability Problems

In many real-life situations, we only have partial information about probabilities. This information is usually described by bounds on moments, on probabilities of certain events, etc. –i.e., by characteristics c(p) which are linear in terms of the unknown probabilities p _j. If we know interval bounds on some such characteristics , and we are interested in a characteristic c(p), then we can find the bounds on c(p) by solving a linear programming problem. In some situations, we also have additional conditions on the probability distribution –e.g., we may know that the two variables x ₁ and x ₂ are independent, or that the joint distribution of x ₁ and x ₂ is unimodal. We show that adding each of these conditions makes the corresponding interval probability problem NP-hard.     

Decoherence control for high-temperature reservoirs

We investigate the decoherence control coupled to a rather general environment, i.e., without using the Markov approximation. Markovian errors generally require high-energy excitations (of the reservoir) and tend to destroy the scalability of the adiabatic quantum computation. Especially, we find that deriving optimal control using the Pontryagin maximum principle, the decoherence can be suppressed even in high-temperature reservoirs. The influences of Ohmic reservoir with Lorentz-Drude regularization are numerically studied in a two-level system under ω _c ≪ ω ₀ condition, here ω ₀ is the characteristic frequency of the quantum system of interest, and ω _c the cut-off frequency of Ohmic reservoir. It implies that designing some engineered reservoirs with the controlled coupling and state of the environment can slow down the decoherence rate and delay the decoherence time. Moreover, we compared the non-Markovian optimal decoherence control with the Markovian one and find that with non-Markovian the engineered artificial reservoirs are better than the Markovian approximate in controlling the decoherence of open, dissipative quantum systems.     

On a cosmological invariant as an observational probe in the early universe

k-essence scalar field models are usually taken to have Lagrangians of the form L = −V (φ)F(X) with F some general function of X = ▿ _μ φ▿ ^μ ϕ. Under certain conditions, this Lagrangian can take the form of that of an oscillator with time-dependent frequency. The Ermakov invariant for a time-dependent oscillator in a cosmological scenario then leads to an invariant quadratic form involving the Hubble parameter and a logarithm of the scale factor. In principle, this invariant can lead to further observational probes for the early Universe. Moreover, if such an invariant can be observationally verified, then the presence of dark energy will also be indirectly confirmed.     

Computational research of the dynamics of bubble cavities and supercavity in a pipe filled with degassed liquid under hydroblows

Further substantiation of the reliability of the method for calculation of an unsteady flow of liquid in a pipeline with coordinate and time variant velocity of sound, developed by the author and previously published in the journal “Matematicheskoye modelirovanie,” is presented. The dependences for variations with x and t in total volume (W _Σ) of bubble cavities, the volume of the supercavity (W _φ2), steam quality (α), the velocity of sound (a), true pressure (P′), and the mass flow rate (G) of a liquid or steam-and-liquid mixture during the course of two cycles, calculated according to the proposed method, for the characteristic cross sections of a simple pipeline filled with cavitating degassed liquid (near the feeding reservoir (x = 0), in the middle of the pipe (x = 0.5L), and near the completely closed throttle (x = L), where x is a longitudinal coordinate and L is the length of the pipe) and for the characteristic times (t) of the development of cavitation processes (for the maximum length of the region of cavitation (t _km ), for the maximum total volume of bubble cavities (t _W ), and for the complete closure of all cavities (t _c )), are presented. An analysis of these dependences is given, which reveals the dynamics of cavitation processes in a pipe filled with degassed cavitating liquid under hydroblows.     

Electron transport through cubic InGaN/AlGaN resonant tunneling diodes

We theoretically study the electron transport through a resonant tunneling diode (RTD) based on strained Al_xGa_1−xN/In_0.1Ga_0.9N/Al_xGa_1−xN quantum wells embedded in relaxed n- Al_0.15Ga_0.85N/strained In_0.1Ga_0.9N emitter and collector. The aluminum composition in both injector and collector contacts is taken relatively weak; this does not preclude achieving a wide band offset at the border of the pre-confinement wells. The epilayers are assumed with a cubic crystal structure to reduce spontaneous and piezoelectric polarization effects. The resonant tunneling and the thermally activated transfer through the barriers are the two mechanisms of transport taken into account in the calculations based on the Schrödinger, Poisson and kinetic equations resolved self-consistently. Using the transfer matrix formalism, we have analyzed the influence of the double barrier height on the resonant current. With an Al composition in the barriers varying between 30% and 50%, we have found that resonant tunneling dominates over the transport mediated by the thermally activated charge transfer for low applied voltages. It is also found that the designed n-type InGaN/AlGaN RTD with 30% of Al composition in the barriers is a potential candidate for achieving a resonant tunneling diode.     

Probability densities for conditional statistics in the cubic sensor problem

This paper applies the techniques of Malliavin’s stochastic calculus of variations to Zakai’s equation for the one-dimensional cubic sensor problem in order to study the existence of densities of conditional statistics. Let {X _t} be a Brownian motion observed by a cubic sensor corrupted by white noise, and let denote the unnormalized conditional estimate of φ(X _i ). If φ₁,...,φ _n are linearly independent, and if , it is shown that the probability distribution of admits a density with respect to Lebesgue measure for anyn. This implies that, at any fixed time, the unnormalized conditional density cannot be characterized by a finite set of sufficient statistics. Research supported in part by NSF Grant No. MCS-8301880 and by the Institute for Mathematics and It Applications, Minneapolis, Minnesota.     

A new quantum claw-finding algorithm for three functions

Fork functionsf ₁, ...f _k, ak-tuple (x ₁, ...x _k) such thatf ₁(x ₁)=...=f _k(x _k) is called a claw off ₁, ...,f _k. In this paper, we construct a new quantum claw-finding algorithm for three functions that is efficient when the numberM of intermediate solutions is small. The known quantum claw-finding algorithm for three functions requiresO(N ^7/8 logN) queries to find a claw, but our algorithm requiresO(N ^3/4 logN) queries ifM ≤ √N andO(N ^7/12 M ^1/3 logN) queries otherwise. Thus, our algorithm is more efficient ifM≤N ^7/8. Kazuo Iwama, Ph.D.: Professor of Informatics, Kyoto University, Kyoto 606-8501, Japan. Received BE, ME, and Ph.D. degrees in Electrical Engineering from Kyoto University in 1978, 1980 and 1985, respectively. His research interests include algorithms, complexity theory and quantum computation. Editorial board of Information Processing Letters and Parallel Computing. Council Member of European Association for Theoretical Computer Science (EATCS). Akinori Kawachi: Received B.Eng. and M.Info. from Kyoto University in 2000 and 2002, respectively. His research interests are quantum computation and distributed computation.     

Large deviations for distributions of sums of random variables: Markov chain method

Let {ξ _k } _k=0^∞ be a sequence of i.i.d. real-valued random variables, and let g(x) be a continuous positive function. Under rather general conditions, we prove results on sharp asymptotics of the probabilities $ P\left\{ {\frac{1} {n}\sum\limits_{k = 0}^{n - 1} {g\left( {\xi _k } \right) < d} } \right\} $ P\left\{ {\frac{1} {n}\sum\limits_{k = 0}^{n - 1} {g\left( {\xi _k } \right) < d} } \right\} , n → ∞, and also of their conditional versions. The results are obtained using a new method developed in the paper, namely, the Laplace method for sojourn times of discrete-time Markov chains. We consider two examples: standard Gaussian random variables with g(x) = |x| ^p , p > 0, and exponential random variables with g(x) = x for x ≥ 0.