Unbounded-error quantum computation with small space bounds

We prove the following facts about the language recognition power of quantum Turing machines (QTMs) in the unbounded error setting: QTMs are strictly more powerful than probabilistic Turing machines for any common space bound s satisfying s(n)=o(loglogn). For “one-way” Turing machines, where the input tape head is not allowed to move left, the above result holds for s(n)=o(logn). We also give a characterization for the class of languages recognized with unbounded error by real-time quantum finite automata (QFAs) with restricted measurements. It turns out that these automata are equal in power to their probabilistic counterparts, and this fact does not change when the QFA model is augmented to allow general measurements and mixed states. Unlike the case with classical finite automata, when the QFA tape head is allowed to remain stationary in some steps, more languages become recognizable. We define and use a QTM model that generalizes the other variants introduced earlier in the study of quantum space complexity.     

Quantum Algorithms for Learning and Testing Juntas

In this article we develop quantum algorithms for learning and testing juntas, i.e. Boolean functions which depend only on an unknown set of k out of n input variables. Our aim is to develop efficient algorithms: (1) whose sample complexity has no dependence on n, the dimension of the domain the Boolean functions are defined over; (2) with no access to any classical or quantum membership (“black-box”) queries. Instead, our algorithms use only classical examples generated uniformly at random and fixed quantum superpositions of such classical examples; (3) which require only a few quantum examples but possibly many classical random examples (which are considered quite “cheap” relative to quantum examples). Our quantum algorithms are based on a subroutine FS which enables sampling according to the Fourier spectrum of f; the FS subroutine was used in earlier work of Bshouty and Jackson on quantum learning. Our results are as follows: (1) We give an algorithm for testing k-juntas to accuracy ε that uses O(k/ϵ) quantum examples. This improves on the number of examples used by the best known classical algorithm. (2) We establish the following lower bound: any FS-based k-junta testing algorithm requires queries. (3) We give an algorithm for learning k-juntas to accuracy ϵ that uses O(ϵ⁻¹ k log k) quantum examples and O(2 ^k log(1/ϵ)) random examples. We show that this learning algorithm is close to optimal by giving a related lower bound. Supported in part by NSF award CCF-0347282, by NSF award CCF-0523664, and by a Sloan Foundation Fellowship.     

Bridging across the log(n) Space Frontier

This paper establishes the importance of even the lowest possible level of space bounded computations. We show that DLOG does not coincide with NLOG if and only if there exists a tally set in NSPACE(log log n)\DSPACE(log log n). This result stands in perfect analogy to the related results concerning linear space or exponential time. Moreover, the above problem is equivalent to the existence of a functions(n), with arbitrarily slow or rapid growth rate, that is nondeterministically fully space constructible but cannot be constructed deterministically. We also present a “hardest” fully space constructibles(n)∈O(log log n), a functional counterpart of log-space complete languages. These nonrelativized results are obtained by the use of oracle machines consuming much larger amount of space, in range betweennand 2^d·n.     

Parallel Biomolecular Computation: Models and Simulations

This paper is concerned with the development of techniques for massively parallel computation at the molecular scale, which we refer to as molecular parallelism. While this may at first appear to be purely science fiction, Adleman [Ad1] has already employed molecular parallelism in the solution of the Hamiltonian path problem, and successfully tested his techniques in a lab experiment on DNA for a small graph. Lipton [L] showed that finding the satisfying inputs to a Boolean expression of size n can be done in O(n) lab steps using DNA of length O(n log n) base pairs. This recent work by Adleman and Lipton in molecular parallelism considered only the solution of NP search problems, and provided no way of quickly executing lengthy computations by purely molecular means; the number of lab steps depended linearly on the size of the simulated expression. See [Re3] for further recent work on molecular parallelism and see [Re4] for an extensive survey of molecular parallelism. Our goal is to execute lengthy computations quickly by the use of molecular parallelism. We wish to execute these biomolecular computations using short DNA strands by more or less conventional biotechnology engineering techniques within a small number of lab steps. This paper describes techniques for achieving this goal, in the context of well defined abstract models of biomolecular computation. Although our results are of theoretical consequence only, due to the large amount of molecular parallelism (i.e., large test tube volume) required , we believe that our theoretical models and results may be a basis for more practical later work, just as was done in the area of parallel computing. We propose two abstract models of biomolecular computation. The first, the Parallel Associative Memory (PAM) model, is a very high-level model which includes a Parallel Associative Matching (PA-Match) operation, that appears to improve the power of molecular parallelism beyond the operations previously considered by Lipton [L]. We give some simulations of conventional sequential and parallel computational models by our PAM model. Each of the simulations use strings of length O(s) over an alphabet of size O(s) (which correspond to DNA of length O(s log s) base pairs). Using O(s log s) PAM operations that are not PA-Match (or O(s) operations assuming a ligation operation) and t PA-Match operations, we can: 1. simulate a nondeterministic Turing Machine computation with space bound s and time bound 2 ^O(s) , with t = O(s) , 2. simulate a CREW PRAM with time bound D, with M memory cells, and processor bound P, where here s = O( log (PM)) and t = O(D+s), 3. find the satisfying inputs to a Boolean circuit constructible in s space with n inputs, unbounded fan-out, and depth D, where here t = O(D+s). We also propose a Recombinant DNA (RDNA) model which is a low-level model that allows operations that are abstractions of very well understood recombinant DNA operations and provides a representation, which we call the complex , for the relevant structural properties of DNA. The PA-Match operation for lengthy strings of length s cannot be feasibly implemented by recombinant DNA techniques directly by a single step of complementary pairing in DNA; nevertheless we show this Matching operation can be simulated in the RDNA model with O(s) slowdown by multiple steps of complementary pairing of substrings of length 2 (corresponding to logarithmic length DNA subsequences). Each of the other operations of the PAM model can be executed in our RDNA model, without slowdown. We further show that, with a further O(s)/ log (1/ε) slowdown, the simulations can be done correctly with probability 1/2 even if certain recombinant DNA operations (e.g., Separation) can error with a probability ε. We also observe efficient simulations can be done by PRAMs and thus Turing Machines of our molecular models. Received December 30, 1995; revised December 30, 1996, and January 22, 1998.     

Geometric Approach to Digital Quantum Information

We present geometric methods for uniformly discretizing the continuous N-qubit Hilbert space H_N. When considered as the vertices of a geometrical figure, the resulting states form the equivalent of a Platonic solid. The discretization technique inherently describes a class of /2 rotations that connect neighboring states in the set, i.e., that leave the geometrical figures invariant. These rotations are shown to generate the Clifford group, a general group of discrete transformations on N qubits. Discretizing H_N allows us to define its digital quantum information content, and we show that this information content grows as N². While we believe the discrete sets are interesting because they allow extra-classical behavior—such as quantum entanglement and quantum parallelism—to be explored while circumventing the continuity of Hilbert space, we also show how they may be a useful tool for problems in traditional quantum computation. We describe in detail the discrete sets for one and two qubits.PACS: 03.67.Lx; 03.67.pp; 03.67.-a; 03.67.Mn.PACS: 03.67.Lx; 03.67.pp; 03.67.-a; 03.67.Mn.     

Space Complexity Vs. Query Complexity

Combinatorial property testing deals with the following relaxation of decision problems: Given a fixed property and an input x, one wants to decide whether x satisfies the property or is “far” from satisfying it. The main focus of property testing is in identifying large families of properties that can be tested with a certain number of queries to the input. In this paper we study the relation between the space complexity of a language and its query complexity. Our main result is that for any space complexity s(n) ≤ log n there is a language with space complexity O(s(n)) and query complexity 2^Ω(s(n)). Our result has implications with respect to testing languages accepted by certain restricted machines. Alon et al. [FOCS 1999] have shown that any regular language is testable with a constant number of queries. It is well known that any language in space o(log log n) is regular, thus implying that such languages can be so tested. It was previously known that there are languages in space O(log n) that are not testable with a constant number of queries and Newman [FOCS 2000] raised the question of closing the exponential gap between these two results. A special case of our main result resolves this problem as it implies that there is a language in space O(log log n) that is not testable with a constant number of queries. It was also previously known that the class of testable properties cannot be extended to all context-free languages. We further show that one cannot even extend the family of testable languages to the class of languages accepted by single counter machines.      

Optimal parallel detection of squares in strings

A stringw isprimitive if it is not a power of another string (i.e., writingw =v ^k impliesk = 1. Conversely,w is asquare ifw =vv, withv a primitive string. A stringx issquare-free if it has no nonempty substring of the formww. It is shown that the square-freedom of a string ofn symbols over an arbitrary alphabet can be tested by a CRCW PRAM withn processors inO(logn) time and linear auxiliary space. If the cardinality of the input alphabet is bounded by a constant independent of the input size, then the number of processors can be reduced ton/logn without affecting the time complexity of this strategy. The fastest sequential algorithms solve this problemO(n logn) orO(n) time, depending on whether the cardinality of the input alphabet is unbounded or bounded, and either performance is known to be optimal within its class. More elaborate constructions lead to a CRCW PRAM algorithm for detecting, within the samen-processors bounds, all positioned squares inx in timeO(logn) and using linear auxiliary space. The fastest sequential algorithms solve this problem inO(n logn) time, and such a performance is known to be optimal.This research was supported, through the Leonardo Fibonacci Institute, by the Istituto Trentino di Cultura, Trento, Italy. Additional support was provided by the French and Italian Ministries of Education, by the National Research Council of Italy, by the British Research Council Grant SERC-E76797, by NSF Grant CCR-89-00305, by NIH Library of Medicine Grant ROI LM05118, by AFOSR Grant 90-0107, and by NATO Grant CRG900293.     

Quantum models of cognition and decision

Abstract

The purpose of this article is to discuss principle ideas of quantum cognition research program, which comprise elements of the formalism of quantum mechanics (mainly Hilbert space theory and quantum probability theory) for modeling human cognition and decision processes. In the opinion of authors of this program, paradox empirical findings in psychological literature may be explained based on concepts of quantum mechanics. Formally, there is described a discrete-time random chain χ which is defined on a finite interval [0, T] and χ(t) can assume only finite number of values. The space H of such processes will be finite-dimensioned. Then some properties and applications of the quantum probability space on H are studied.     

Low-randomness constant-round private XOR computations

In this paper we study the randomness complexity needed to distributively perform k XOR computations in a t-private way using constant-round protocols in the case in which the players are honest but curious. We show that the existence of a particular family of subsets allows the recycling of random bits for constant-round private protocols. More precisely, we show that after a 1-round initialization phase during which random bits are distributed among n players, it is possible to perform each of the k XOR computations using two rounds of communication. For , for any c < 1/2, we design a protocol that uses O(kt ²log n) random bits.     

On the computational power of probabilistic and quantum branching program

In this paper, we show that one-qubit polynomial time computations are as powerful as NC¹ circuits. More generally, we define syntactic models for quantum and stochastic branching programs of bounded width and prove upper and lower bounds on their power. We show that any NC¹ language can be accepted exactly by a width-2 quantum branching program of polynomial length, in contrast to the classical case where width 5 is necessary unless NC¹ = ACC. This separates width-2 quantum programs from width-2 doubly stochastic programs as we show the latter cannot compute the middle bit of multiplication. Finally, we show that bounded-width quantum and stochastic programs can be simulated by classical programs of larger but bounded width, and thus are in NC¹. For read-once quantum branching programs (QBPs), we give a symmetric Boolean function which is computable by a read-once QBP with O (log n) width, but not by a deterministic read-once BP with o (n) width, or by a classical randomized read-once BP with o (n) width which is “stable” in the sense that its transitions depend on the value of the queried variable but do not vary from step to step. Finally, we present a general lower bound on the width of read-once QBPs, showing that our O (log n) upper bound for this symmetric function is almost tight.     

Space Hierarchy Results for Randomized and other Semantic Models

We prove space hierarchy and separation results for randomized and other semantic models of computation with advice where a machine is only required to behave appropriately when given the correct advice sequence. Previous works on hierarchy and separation theorems for such models focused on time as the resource. We obtain tighter results with space as the resource. Our main theorems deal with space-bounded randomized machines that always halt. Let s(n) be any space-constructible monotone function that is Ω(log n) and let s′(n) be any function such that s′(n) = ω(s(n + as(n))) for all constants a.

Robust H∞ controller design for a class of linear quantum systems with time delay

Time delay is frequently encountered in practical quantum feedback control systems with long transmission lines and measurement process. This paper is concerned with measurement‐based feedback H^∞ control for quantum systems with time delays appearing in the feedback loops. A physical model is presented for the quantum time‐delay system described by complex quantum stochastic differential equations. Quantum versions of some fundamental properties, such as dissipativity and stability, are discussed for this model. A numerical procedure is proposed for H^∞ controller synthesis, which can deal with a non‐convex optimization problem arising in the design processes. Copyright © 2016 John Wiley & Sons, Ltd.     

Efficient adaptive collect algorithms

Deterministic collect algorithms are presented that are adaptive to total contention and are efficient with respect to both the number of registers used and the step complexity. One of them has optimal O(k) step and O(n) space complexities, but assumes that processes’ identifiers are in O(n), where n is the total number of processes in the system and k is the total contention. The step complexity of an unrestricted name space variant of this algorithm remains O(k), but its space complexity increases to O(n ²).     

Parallel algorithms for minimal spanning trees of directed graphs

The main results of this paper are efficient parallel algorithms, MSP and LOCATE, for computing minimal spanning trees and locating minimal paths in directed graphs, respectively. Algorithm MSP has time complexityO(log³ n) usingO(n ³/logn) processors, while LOCATE has time complexityO(logn) usingO(n ²) processors. Algorithm MSP is derived from sequential algorithms, when the unbounded parallelism model is used.     

NP对PP

主要目的是研究NP与PP的关系。引入了一个NP的等价的随机定义。基于此等价定义,定义了另一个随机复杂性类：SUPER－NP。虽然SUPER－NP与NP非常接近,但令人吃惊的是发现了PP包含于SUPER－NP,从而NP包含于PP包含于SUPER－NP。考虑到NP＝PCP（log,O(1))以及NP和SUPER－NP的相似性,也希望能通过证明SUPER－NP包含于PCP（log^2,O(1))来解决PP包含于PCP（log^2,O(1))的猜想。     

Range mode and range median queries in constant time and sub-quadratic space

Given a list of n items and a function defined over sub-lists, we study the space required for computing the function for arbitrary sub-lists in constant time.For the function mode we improve the previously known space bound O(n²/logn) to O(n²loglogn/log²n) words.For median the space bound is improved to O(n²loglog²n/log²n) words from O(n²⋅log(k)n/logn), where k is an arbitrary constant and log(k) is the iterated logarithm.     

Sextic C 1-spline collocation methods for solving delay differential equations

In this paper, we propose a global collocation method for the numerical solution of the delay differential equations (DDEs). The method presented is based on sextic C ¹-splines s(x) as an approximation to the exact solution y(x) of the DDEs. Convergence results shows that the error bounds ‖ s ^j ?y ^j ‖=O(h ⁶), j=0, 1, in the uniform norm. Moreover, the stability analysis properties of these methods have been studied. Numerical experiments will also be considered.     

Computation in networks of passively mobile finite-state sensors

The computational power of networks of small resource-limited mobile agents is explored. Two new models of computation based on pairwise interactions of finite-state agents in populations of finite but unbounded size are defined. With a fairness condition on interactions, the concept of stable computation of a function or predicate is defined. Protocols are given that stably compute any predicate in the class definable by formulas of Presburger arithmetic, which includes Boolean combinations of threshold-k, majority, and equivalence modulo m. All stably computable predicates are shown to be in NL. Assuming uniform random sampling of interacting pairs yields the model of conjugating automata. Any counter machine with O(1) counters of capacity O(n) can be simulated with high probability by a conjugating automaton in a population of size n. All predicates computable with high probability in this model are shown to be in P; they can also be computed by a randomized logspace machine in exponential time. Several open problems and promising future directions are discussed. Supported in part by NSF grants CCR-9820888, CCR-0098078, and CNS-0305258 (Aspnes), by ONR grant N00014-01-1-0795 (Diamadi), and by NSF grant CSE-0081823 (Fischer and Peralta). A preliminary version of this paper appeared in the proceedings of the 23rd ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing, St. John’s, Newfoundland, Canada, July 2004.     

Computing Bounds for the Star Discrepancy

We observe that the time required to compute the star discrepancy of a sequence of points in a multidimensional unit cube is prohibitive and that the best known upper bounds for the star discrepancy of (t,s)-sequences and (t,m,s)-nets are useful only for sample sizes that grow exponentially with the dimension s. Then, an algorithm to compute upper bounds for the star discrepancy of an arbitrary set of n points in the s-dimensional unit cube is proposed. For an integer k≥1, this algorithm computes in O(nslogk+2 ^s k ^s ) time and O(k ^s ) space a bound that is no better than a function depending on s and k. As an application, we give improved upper bounds for the star discrepancy of some Faure (0,m,s)-nets for s∈{7,…,20}. Received April 20, 1999; revised April 26, 2000