Search results for "Computer Science::Databases"

Grover’s Algorithm with Errors

2013

Grover’s algorithm is a quantum search algorithm solving the unstructured search problem of size n in \(O(\sqrt{n})\) queries, while any classical algorithm needs O(n) queries [3].

Understanding Quantum Algorithms via Query Complexity

2017

Query complexity is a model of computation in which we have to compute a function $f(x_1, \ldots, x_N)$ of variables $x_i$ which can be accessed via queries. The complexity of an algorithm is measured by the number of queries that it makes. Query complexity is widely used for studying quantum algorithms, for two reasons. First, it includes many of the known quantum algorithms (including Grover's quantum search and a key subroutine of Shor's factoring algorithm). Second, one can prove lower bounds on the query complexity, bounding the possible quantum advantage. In the last few years, there have been major advances on several longstanding problems in the query complexity. In this talk, we su…

Embedding finite linear spaces in projective planes, II

1987

Abstract It is shown that a finite linear space with maximal point degree n + 1 can be embedded in a projective plane of order n, provided that the line sizes are big enough.

Error-Free Affine, Unitary, and Probabilistic OBDDs

2018

We introduce the affine OBDD model and show that zero-error affine OBDDs can be exponentially narrower than bounded-error unitary and probabilistic OBDDs on certain problems. Moreover, we show that Las Vegas unitary and probabilistic OBDDs can be quadratically narrower than deterministic OBDDs. We also obtain the same results for the automata versions of these models.

2014

Is there a general theorem that tells us when we can hope for exponential speedups from quantum algorithms, and when we cannot? In this paper, we make two advances toward such a theorem, in the black-box model where most quantum algorithms operate. First, we show that for any problem that is invariant under permuting inputs and outputs (like the collision or the element distinctness problems), the quantum query complexity is at least the 9 th root of the classical randomized query complexity. This resolves a conjecture of Watrous from 2002. Second, inspired by recent work of O’Donnell et al. and Dinur et al., we conjecture that every bounded low-degree polynomial has a “highly influential” …

Locality of order-invariant first-order formulas

1998

A query is local if the decision of whether a tuple in a structure satisfies this query only depends on a small neighborhood of the tuple. We prove that all queries expressible by order-invariant first-order formulas are local.

Elementary (-1)-curves of P-3

2006

In this note we deal with rational curves in P^3 which are images of a line by means of a finite sequence of cubo-cubic Cremona transformations. We prove that these curves can always be obtained applying to the line a sequence of such transformations increasing at each step the degree of the curve. As a corollary we get a result about curves that can give speciality for linear systems of P^3.

Error-Free Affine, Unitary, and Probabilistic OBDDs

2021

We introduce the affine OBDD model and show that zero-error affine OBDDs can be exponentially narrower than bounded-error unitary and probabilistic OBDDs on certain problems. Moreover, we show that Las-Vegas unitary and probabilistic OBDDs can be quadratically narrower than deterministic OBDDs. We also obtain the same results for the automata counterparts of these models.

Trading off accuracy for efficiency by randomized greedy warping

2016

Dynamic Time Warping (DTW) is a widely used distance measure for time series data mining. Its quadratic complexity requires the application of various techniques (e.g. warping constraints, lower-bounds) for deployment in real-time scenarios. In this paper we propose a randomized greedy warping algorithm for finding similarity between time series instances. We show that the proposed algorithm outperforms the simple greedy approach and also provides very good time series similarity approximation consistently, as compared to DTW. We show that the Randomized Time Warping (RTW) can be used in place of DTW as a fast similarity approximation technique by trading some classification accuracy for ve…

Exact solution of generalized Tavis - Cummings models in quantum optics

1996

Quantum inverse methods are developed for the exact solution of models which describe N two-level atoms interacting with one mode of the quantized electromagnetic field containing an arbitrary number of excitations M. Either a Kerr-type nonlinearity or a Stark-shift term can be included in the model, and it is shown that these two cases can be mapped from one to the other. The method of solution provides a general framework within which many related problems can similarly be solved. Explicit formulae are given for the Rabi splitting of the models for some N and M, on- and off-resonance. It is also shown that the solution of the pure Tavis - Cummings model can be reduced to solving a homogen…