A note on alternating one-pebble Turing machines with sublogarithmic space

Inoue et al. [A. Inoue, A. Ito, K. Inoue, T. Okazaki, Some properties of one-pebble Turing machines with sublogarithmic space, Theoret. Comput. Sci. 341 (2005) 138-149] conjectured that the language {ww|w∈⁺{a,b}} is not accepted by any alternating one-pebble Turing machine with sublogarithmic space. In this paper we disprove the conjecture by showing that there exists an alternating one-pebble Turing machine accepting the language in loglogn space.     

Mathematical models of quantum computation

In this paper, we introduce two mathematical models of realistic quantum computation. First, we develop a theory of bulk quantum computation such as NMR (Nuclear Magnetic Resonance) quantum computation. For this purpose, we define bulk quantum Turing machine (BQTM for short) as a model of bulk quantum computation. Then, we define complexity classes EBQP, BBQP and ZBQP as counterparts of the quantum complexity classes EQP, BQP and ZQP, respectively, and show that EBQP=EQP, BBQP=BQP and ZBQP=ZQP. This implies that BQTMs are polynomially related to ordinary QTMs as long as they are used to solve decision problems. We also show that these two types of QTMs are also polynomially related when they solve a function problem which has a unique solution. Furthermore, we show that BQTMs can solve certain instances of NP-complete problems efficiently. On the other hand, in the theory of quantum computation, only feed-forward quantum circuits are investigated, because a quantum circuit represents a sequence of applications of time evolution operators. But, if a quantum computer is a physical device where the gates are interactions controlled by a current computer such as laser pulses on trapped ions, NMR and most implementation proposals, it is natural to describe quantum circuits as ones that have feedback loops if we want to visualize the total amount of the necessary hardware. For this purpose, we introduce a quantum recurrent circuit model, which is a quantum circuit with feedback loops. LetC be a quantum recurrent circuit which solves the satisfiability problem for a blackbox Boolean function includingn variables with probability at least 1/2. And lets be the size ofC (i.e. the number of the gates inC) andt be the number of iterations that is needed forC to solve the satisfiability problem. Then, we show that, for those quantum recurrent circuits, the minimum value ofmax(s, t) isO(n ²2 ^n/3). Tetsuro Nishino, D.Sc.: He is presently an Associate Professor in the Department of Information and Communication Engineering, The University of Electro-Communications. He received the B.S., M.S. and D.Sc degrees in mathematics from Waseda University, in 1982, 1984 and 1991 respectively. From 1984 to 1987, he joined Tokyo Research Laboratory, IBM Japan. From 1987 to 1992, he was a Research Associate of Tokyo Denki University, and from 1992 to 1994, he was an Associate Professor of Japan Advanced Institute of Science and Technology, Hokuriku. His main interests are circuit complexity theory, computational learning theory and quantum complexity theory.     

Optimal computation with non-unitary quantum walks

Quantum versions of random walks on the line and the cycle show a quadratic improvement over classical random walks in their spreading rates and mixing times, respectively. Non-unitary quantum walks can provide a useful optimisation of these properties, producing a more uniform distribution on the line, and faster mixing times on the cycle. We investigate the interplay between quantum and random dynamics by comparing the resources required, and examining numerically how the level of quantum correlations varies during the walk. We show numerically that the optimal non-unitary quantum walk proceeds such that the quantum correlations are nearly all removed at the point of the final measurement. This requires only O(logT)$O(logT)$ random bits for a quantum walk of T$T$ steps.     

The alternation hierarchy for sublogarithmic space is infinite

The alternation hierarchy for Turing machines with a space bound between loglog and log is infinite. That applies to all common concepts, especially a) to two-way machines with weak space-bounds, b) to two-way machines with strong space-bounds, and c) to one-way machines with weak space-bounds. In all of these cases the _k -and II _k -classes are not comparable fork>-2. Furthermore the _k -classes are not closed under intersection and the II _k -classes are not closed under union. Thus these classes are not closed under complementation. The hierarchy results also apply to classes determined by an alternation depth which is a function depending on the input rather than on a constant.     

Polynomial time quantum computation with advice

Advice is supplementary information that enhances the computational power of an underlying computation. This paper focuses on advice that is given in the form of a pure quantum state and examines the influence of such advice on the behaviors of an underlying polynomial-time quantum computation with bounded-error probability.     

Perfect computational equivalence between quantum Turing machines and finitely generated uniform quantum circuit families

In order to establish the computational equivalence between quantum Turing machines (QTMs) and quantum circuit families (QCFs) using Yao’s quantum circuit simulation of QTMs, we previously introduced the class of uniform QCFs based on an infinite set of elementary gates, which has been shown to be computationally equivalent to the polynomial-time QTMs (with appropriate restriction of amplitudes) up to bounded error simulation. This result implies that the complexity class BQP introduced by Bernstein and Vazirani for QTMs equals its counterpart for uniform QCFs. However, the complexity classes ZQP and EQP for QTMs do not appear to equal their counterparts for uniform QCFs. In this paper, we introduce a subclass of uniform QCFs, the finitely generated uniform QCFs, based on finite number of elementary gates and show that the class of finitely generated uniform QCFs is perfectly equivalent to the class of polynomial-time QTMs; they can exactly simulate each other. This naturally implies that BQP as well as ZQP and EQP equal the corresponding complexity classes of the finitely generated uniform QCFs.     

Computational procedure to determine quantum state evolution in Fock space

A new algorithm to solve the quantum state evolution of a system described by a general quadratic Hamiltonian form in creation and the annihilation operators of Fock space is presented. The nonlinear equation for the dynamic operators are obtained in the matrix representation, and by a recursive relation the time evolution operator in the Fock basis is constructed. The method permits to obtain the evolution of entangled quantum states of interacting subsystems when the Hamiltonian of the whole system is in the above mentioned form. Numerical solution with the method is sufficiently accurate to safely analyze the important question of quantum state transfer between the interacting subsystems. A qubits transfer is discussed as an illustrative example when the method is applied to a system described by a particular quadratic Hamiltonian form.     

Some algebraic properties of measure-once two-way quantum finite automata

Quantum finite automata (QFA) can be divided into four kinds depend upon the head-directions and the measure times. They are measure-once one way QFA (MO-1QFA) introduced by Moore and Crutchfield (Theor Comput Sci 237: 275–306, 2000); measure-many one way QFA (MM-1QFA) and measure-many two-way QFA (MM-2QFA) introduced by Kondacs and Watrous (Proceedings of the 38th IEEE annual symposium on 433 foundations of computer science, 66–75, 1997); and measure-once two-way QFA (MO-2QFA) which were not given until now. The purpose of this work is mainly to discuss one kind of QFA, which is called MO-2QFA for brief. First of all, the definition of MO-2QFA is given and the conditions for preserving unitary properties are shown. Then, we analysis the basic algebraic properties of the class of languages which can be recognized by MO-2QFA, such as the union, intersection, complement and reversal operations. As well, we consider the catenation operation on the class of quantum languages recognized by MO-2QFA is closed in the generalized conditions.      

Computing with random quantum dot repulsion

Quantum dot cellular automata (QCA) show great promise for fast computation with larger integration density and lower power consumption. Unfortunately, previous research has shown that QCA are likely to be extremely sensitive to placement error. During an investigation into placement sensitivity, it was discovered that completely random quantum dot structures have the ability to compute simple binary functions. In this paper, we further explore the random structures in an idealized way, looking for higher-order functions; an example of one-bit full adder is shown in the paper. Moreover, a new structure, the semi-random structure, is introduced to alleviate some, but not all, difficulties in connecting disparate random structures; the difficulties arise from the fact that inputs and outputs to and from a purely random structure may not reside at the edges of the structure. In the semi-random structure, the inputs and outputs are localized to the edges. It is demonstrated that semi-random structures, like random structures, can almost assuredly compute simple Boolean functions.     

computation,among other things,is beneath us

What's computation? The received answer is that computation is a computer at work, and a computer at work is that which can be modelled as a Turing machine at work. Unfortunately, as John Searle has recently argued, and as others have agreed, the received answer appears to imply that AI and Cog Sci are a royal waste of time. The argument here is alarmingly simple: AI and Cog Sci (of the “Strong” sort, anyway) are committed to the view that cognition is computation (or brains are computers); butall processes are computations (orall physical things are computers); so AI and Cog Sci are positively silly. I refute this argument herein, in part by defining the locutions ‘x is a computer’ and ‘c is a computation’ in a way that blocks Searle's argument but exploits the hard-to-deny link between What's Computation? and the theory of computation. However, I also provide, at the end of this essay, an argument which, it seems to me, implies not that AI and Cog Sci are silly, but that they're based on a form of computation that is well “beneath” human persons.     

Efficient algorithms for NMR quantum computers with small qubits

The security of the RSA cryptosystems is based on the difficulty of factoring a large composite integer. In 1994, Shor showed that factoring a large composite is executable in polynomial time if we use a quantum Turing machine. Since this algorithm is complicated, straightforward implementations seem impractical judging from current technologies. In this paper, we propose simple and efficient algorithms for factoring and discrete logarithm problem based on NMR quantum computers. Our algorithms are easier to implement if we consider NMR quantum computers with small qubits. A part of this work was done while both authors were with NTT Communication Science Laboratories. Noboru Kunihiro, Ph.D.: He is Assistant Professor of the University of Electro-Communications. He received his B.E., M.E. and Ph.D. in mathematical engineering and information physics from the University of Tokyo in 1994, 1996 and 2001, respectively. He had been engaged in the research on cryptography and information security at NTT Communication Science Laboratories from 1996 to 2002. Since 2002, he has been working for Department of Information and Communication Engineering of the University of Elector-Communications. His research interest includes cryptography, information security and quantum computations. He was awarded the SCIS’97 paper prize. Shigeru Yamashita, Ph.D.: Associate Professor of Graduate School of Information Science, Nara Institute of Science and Technology, Nara 630-0192, Japan. He received his B.E., M.E. and Ph.D. degrees in information science from Kyoto University, Kyoto, Japan, in 1993, 1995 and 2001, respectively. His research interests include new type of computer architectures and quantum computation. He received the 2000 IEEE Circuits and Systems Society Transactions on Computer-Aided Design of Integrated Circuits and Systems Best Paper Award.     

Experiments with probabilistic quantum auctions

We describe human-subject laboratory experiments on probabilistic auctions based on previously proposed auction protocols involving the simulated manipulation and communication of quantum states. These auctions are probabilistic in determining which bidder wins, or having no winner, rather than always having the highest bidder win. Comparing two quantum protocols in the context of first-price sealed bid auctions, we find the one predicted to be superior by game theory also performs better experimentally. We also compare with a conventional first-price auction, which gives higher performance. Thus to provide benefits, the quantum protocol requires more complex economic scenarios such as maintaining privacy of bids over a series of related auctions or involving allocative externalities.      

Sufficient conditions of deterministic implementation of finite-state automata with retention of the numbers of their states

The following three conditions for nondeterministic finite-state automata are defined: input embeddability, output embeddability, and input decomposability. Automata satisfying these conditions are called nondeterministic automata with embeddability. A method for deterministic implementation of such automata with retention of the numbers of their states is proposed. These automata correspond to block-procedural high-level programming languages. Translated from Kibernetika i Sistemnyi Analiz, No. 3, pp. 55–62, May–June, 2000.     

Probabilistic reasoning in an augmented fact-proposition space and its applications

A simple and versatile probabilistic reasoning scheme is presented. Based on an augmentation of a multi-dimensional inference space indexed by a Cartesian product of the fact and proposition sets, the scheme simplifies the processes involved in the representation and computation of a probabilistic reasoning system. In the augmented space, a set of auxiliary fields is utilized in addition to the fact-proposition relations to manipulate the uncertainty and incompleteness of the information presented. The scheme enhances the functionality of a probabilistic reasoning and facilitates the building of practical reasoning systems. The utilization of the augmented space in reasoning is illustrated by two problems in computer-vision applications.     

A novel reduced-basis method with upper and lower bounds for real-time computation of linear elasticity problems

This paper presents a novel reduced-basis method for analyzing problems of linear elasticity in a systematical, rapid and reliable fashion for solutions with both upper and lower bounds to the exact solution in the form of energy norm or compliance output. The lower bound of the solution output is obtained form the well-known reduced-basis method based on the Galerkin projection used in the finite element method, which is termed as GP_RBM. For the upper bound, a new reduced-basis approach is developed by the combination of the reduced-basis method and a smoothed Galerkin projection used in the linearly conforming point interpolation method, and it is thus termed as SGP_RBM. To examine the present SGP_RBM, we first conduct a theoretical study on the very important upper bound property. Reduced-basis models for both GP_RBM and SGP_RBM are constructed with the aid of an asymptotic error estimation and greedy adaptive procedure. The GP_RBM and the newly proposed SGP_RBM are applied to analyze a cantilever beam with an oblique crack to verify the proposed RBM technique in terms of accuracy, convergence, bound properties and computational savings. Both theoretical analysis and numerical results have demonstrated that the present method is a very efficient method for real-time solutions providing exact output bounds.