Quantum Lower Bounds for Fanout

We prove several new lower bounds for constant depth quantum circuits. The main result is that parity (and hence fanout) requires log depth circuits, when the circuits are composed of single qubit and arbitrary size Toffoli gates, and when they use only constantly many ancillae. Under this constraint, this bound is close to optimal. In the case of a non-constant number of ancillae, we give a tradeoff between the number of ancillae and the required depth.

Upper and lower bounds of 180 degrees unit element of a ridge waveguide: Calculations and measurements

The upper and lower bounds on the actual solution of any microwave structure is of general interest. The purpose of this letter is to compare some calculations using the mode-matching and finite-element methods, with some measurements on a 180 degrees ridge waveguide insert between standard WR62 rectangular waveguides. The work suggests that the MMM produces an upper bound, while the FEM places a lower bound on the measurement. (C) 2001 John Wiley & Sons, Inc.

Lower Bounds for Nonforgetting Restarting Automata and CD-Systems of Restarting Automata

The nonforgetting restarting automaton is a generalization of the restarting automaton that, when executing a restart operation, changes its internal state based on the current state and the actual contents of its read/write window instead of resetting it to the initial state. Another generalization of the restarting automaton is the cooperating distributed system (CD-system) of restarting automata. Here a finite system of restarting automata works together in analyzing a given sentence, where they interact based on a given mode of operation. As it turned out, CD-systems of restarting automata of some type X working in mode =1 are just as expressive as nonforgetting restarting automata of the same type X. Further, various types of determinism have been introduced for CD-systems of restarting automata called strict determinism, global determinism, and local determinism, and it has been shown that globally deterministic CD-systems working in mode =1 correspond to deterministic nonforgetting restarting automata. Here we derive some lower bound results for some types of nonforgetting restarting automata and for some types of CD-systems of restarting automata. In this way we establish separations between the corresponding language classes, thus providing detailed technical proofs for some of the separation results announced in the literature.

Lower Bounds for Achieving Synchronous Early Stopping Consensus with Orderly Crash Failures

In this paper, we discuss the consensus problem for synchronous distributed systems with orderly crash failures. For a synchronous distributed system of n processes with up to t crash failures and f failures actually occur, first, we present a bivalency argument proof to solve the open problem of proving the lower bound, min (t + 1, f + 2) rounds, for early-stopping synchronous consensus with orderly crash failures, where t < n - 1. Then, we extend the system model with orderly crash failures to a new model in which a process is allowed to send multiple messages to the same destination process in a round and the failing processes still respect the order specified by the protocol in sending messages. For this new model, we present a uniform consensus protocol, in which all non-faulty processes always decide and stop immediately by the end of f + 1 rounds. We prove that the lower bound of early stopping protocols for both consensus and uniform consensus are f + 1 rounds under the new model, and our proposed protocol is optimal.

Ω-results for Beurling's zeta function and lower bounds for the generalised Dirichlet divisor problem

In this paper we study generalised prime systems for which the integer counting function NP(x) is asymptotically well behaved, in the sense that NP(x)=ρx+O(xβ), where ρ is a positive constant and . For such systems, the associated zeta function ζP(s) is holomorphic for . We prove that for , for any ε>0, and also for ε=0 for all such σ except possibly one value. The Dirichlet divisor problem for generalised integers concerns the size of the error term in NkP(x)−Ress=1(ζPk(s)xs/s), which is O(xθ) for some θ<1. Letting αk denote the infimum of such θ, we show that .

Lower bounds on blow up solutions of the three-dimensional Navier-Stokes equations in homogeneous Sobolev spaces

Suppose that u(t) is a solution of the three-dimensional Navier-Stokes equations, either on the whole space or with periodic boundary conditions, that has a singularity at time T. In this paper we show that the norm of u(T - t) in the homogeneous Sobolev space (H)over dot(s) must be bounded below by c(s)t(-(2s-1)/4) for 1/2 < s < 5/2 (s not equal 3/2), where c(s) is an absolute constant depending only on s; and by c(s)parallel to u(0)parallel to((5-2s)/5)(L2)t(-2s/5) for s > 5/2. (The result for 1/2 < s < 3/2 follows from well-known lower bounds on blowup in Lp spaces.) We show in particular that the local existence time in (H)over dot(s)(R-3) depends only on the (H)over dot(s)-norm for 1/2 < s < 5/2, s not equal 3/2. (C) 2012 American Institute of Physics. [http://dx.doi.org/10.1063/1.4762841]

The trouble with quality filtering based on relative Cramér-Rao lower bounds.

Cramér Rao Lower Bounds (CRLB) have become the standard for expression of uncertainties in quantitative MR spectroscopy. If properly interpreted as a lower threshold of the error associated with model fitting, and if the limits of its estimation are respected, CRLB are certainly a very valuable tool to give an idea of minimal uncertainties in magnetic resonance spectroscopy (MRS), although other sources of error may be larger. Unfortunately, it has also become standard practice to use relative CRLB expressed as a percentage of the presently estimated area or concentration value as unsupervised exclusion criterion for bad quality spectra. It is shown that such quality filtering with widely used threshold levels of 20% to 50% CRLB readily causes bias in the estimated mean concentrations of cohort data, leading to wrong or missed statistical findings-and if applied rigorously-to the failure of using MRS as a clinical instrument to diagnose disease characterized by low levels of metabolites. Instead, absolute CRLB in comparison to those of the normal group or CRLB in relation to normal metabolite levels may be more useful as quality criteria. Magn Reson Med, 2015. © 2015 Wiley Periodicals, Inc.

New lower bounds for the topological complexity of aspherical spaces

Date of Acceptance: 5/04/2015 15 pages, 4 figures

Lower bounds on merging networks /

Bibliography: leaf 16.

Lower bounds on the complexity of simulating quantum gates

We give a simple proof of a formula for the minimal time required to simulate a two-qubit unitary operation using a fixed two-qubit Hamiltonian together with fast local unitaries. We also note that a related lower bound holds for arbitrary n-qubit gates.

A geometric approach to quantum circuit lower bounds

What is the minimal size quantum circuit required to exactly implement a specified n-qubit unitary operation, U, without the use of ancilla qubits? We show that a lower bound on the minimal size is provided by the length of the minimal geodesic between U and the identity, I, where length is defined by a suitable Finsler metric on the manifold SU(2(n)). The geodesic curves on these manifolds have the striking property that once an initial position and velocity are set, the remainder of the geodesic is completely determined by a second order differential equation known as the geodesic equation. This is in contrast with the usual case in circuit design, either classical or quantum, where being given part of an optimal circuit does not obviously assist in the design of the rest of the circuit. Geodesic analysis thus offers a potentially powerful approach to the problem of proving quantum circuit lower bounds. In this paper we construct several Finsler metrics whose minimal length geodesics provide lower bounds on quantum circuit size. For each Finsler metric we give a procedure to compute the corresponding geodesic equation. We also construct a large class of solutions to the geodesic equation, which we call Pauli geodesics, since they arise from isometries generated by the Pauli group. For any unitary U diagonal in the computational basis, we show that: (a) provided the minimal length geodesic is unique, it must be a Pauli geodesic; (b) finding the length of the minimal Pauli geodesic passing from I to U is equivalent to solving an exponential size instance of the closest vector in a lattice problem (CVP); and (c) all but a doubly exponentially small fraction of such unitaries have minimal Pauli geodesics of exponential length.

Upper and lower bounds on the learning curve for Gaussian processes

In this paper we introduce and illustrate non-trivial upper and lower bounds on the learning curves for one-dimensional Gaussian Processes. The analysis is carried out emphasising the effects induced on the bounds by the smoothness of the random process described by the Modified Bessel and the Squared Exponential covariance functions. We present an explanation of the early, linearly-decreasing behavior of the learning curves and the bounds as well as a study of the asymptotic behavior of the curves. The effects of the noise level and the lengthscale on the tightness of the bounds are also discussed.

Matricial Model for the Study of Lower Bounds

Let V be an array. The range query problem concerns the design of data structures for implementing the following operations. The operation update(j,x) has the effect vj ← vj + x, and the query operation retrieve(i,j) returns the partial sum vi + ... + vj. These tasks are to be performed on-line. We define an algebraic model – based on the use of matrices – for the study of the problem. In this paper we establish as well a lower bound for the sum of the average complexity of both kinds of operations, and demonstrate that this lower bound is near optimal – in terms of asymptotic complexity.

Upper and Lower Bounds in Relator Spaces

2000 Mathematics Subject Classification: 06A06, 54E15