The k'th frequency moment of a sequence of integers is defined as Fk = Σj njk, where nj is the number of times that j occurs in the sequence. Here we study the quantum complexity of approximately c...
The k’th frequency moment of a sequence of integers is defined as F_k = Sum_ j n^k _j , where n_j is the number of times that j occurs in the sequence. Here we study the quantum complexity of approximately computing the frequency moments in two settings. In the query complexity setting, we wish to minimise the number of queries to the input used to approximate F_k up to relative error epsilon. We give quantum algorithms which outperform the best possible classical algorithms up to quadratically. In the multiple-pass streaming setting, we see the elements of the input one at a time, and seek to minimise the amount of storage space, or passes over the data, used to approximate F_k. We describe quantum algorithms for F_0, F_2 and F_∞ in this model which substantially outperform the best possible classical algorithms in certain parameter regimes.
Let X = (z,, , z,-,) be a sequence of n numbers.For 6 > 0, we say that 5; is an e-approximate median if the number of elements strictly less than zi and the number of elements strictly greater than zi are each less than (1 + 6):.We consider the quantum query complexity of computing an c-approximate median, given the sequence X as an oracle.We prove a lower bound of n(min{t,n}) queries for any quantum algorithm that computes an r-approximate median with any constant probability greater than l/2.We also show how an c-approximate median may be computed with 0( $ log(t) log log( $)) oracle queries, which rep resents an improvement over an earlier algorithm due to Grover [ll, 121.Thus, the lower bound we obtain is essentially optimal.The upper and the lower bound both hold in the comparison tree model as well.Our lower bound result is an application of the polynomial paradigm recently introduced to quantum complexity theory by Be& et ol.[l].The main ingredient in the proof is a polynomial degree lower bound far real multilinear polynomials that "approximate" symmetric partial boolean functions.The degree bound extends a result of Patti[15] and also immediately yields lower bounds for the problems of approximating the kth-smallest element, approximating the mean of a sequence of numbers, and approximately counting the number of ones of a boolean function.All bounds obtained come within a polylogarithmic factor of the optimal (as we show by presenting algorithms where no such optimal or near optimal algorithms were known), thus demonstrating the power of the polynomial method.
Two-mode squeezed states have potential applications in quantum teleportation, quantum computation, and quantum information. Spontaneous parametric down conversion (SPDC) is one of the processes that can be used to generate two-mode squeezed optical states, both in bulk and integrated systems. In this work, we theoretically model SPDC in a vertically-pumped, lossy, coupled-resonator optical waveguide (CROW), shown in Fig. 1(a), to generate counterpropagating continuous variable (CV) entangled states. For a CROW in which the cavities are identical, using the nearest neighbour TB approximation, the CROW mode dispersion is given by ω̃Fk≈ ω̃F[1+ β̃1cos(kD)] ≡ ωFk-iγFk,, where ω̃Fis the individual-cavity complex mode frequency, β̃1is the complex coupling parameter, D is the periodicity of the CROW, and k is the Bloch vector. We consider the case of a pump that is Gaussian in time and space, with spatial and temporal full width at half maxima of ΔrFMHM= 2 √{l n2}/σ+and ΔtFMHM= 2 √{l n2}/τ/(σ_D), respectively, where σ+and σ_ are the k-space width parameters (see below), and τ = Re {1 / (ω̃Fβ̃1)} is the minimum time for the light to propagate one period.
The nonnegativity of the determinant of the partial transpose of a two-qubit (4 x 4) density matrix is both a necessary and sufficient condition for its separability. While the determinant is restricted to the interval [0,1/256], the determinant of the partial transpose can range over [-1/16,1/256], with negative values corresponding to entangled states. We report here the exact values of the first nine moments of the probability distribution of the partial transpose over this interval, with respect to the Hilbert-Schmidt (metric volume element) measure on the nine-dimensional convex set of real two-qubit density matrices. Rational functions C_{2 j}(m), yielding the coefficients of the 2j-th power of even polynomials occurring at intermediate steps in our derivation of the m-th moment, emerge. These functions possess poles at finite series of consecutive half-integers (m=-3/2,-1/2,...,(2j-1)/2), and certain (trivial) roots at finite series of consecutive natural numbers (m=0, 1,...). Additionally, the (nontrivial) dominant roots of C_{2 j}(m) approach the same half-integer values (m = (2 j-1)/2, (2 j-3)/2,...), as j increases. The first two moments (mean and variance) found--when employed in the one-sided Chebyshev inequality--give an upper bound of 30397/34749 = 0.874759 on the separability probability of real two-qubit density matrices. We are able to report general formulas for the m-th moment of the Hilbert-Schmidt probability distribution of the density matrix determinant over [0,1/256], in the real, complex and quaternionic two-qubit cases.