Zobrazeno 1 - 10
of 56
pro vyhledávání: '"Vihrovs, Jevgēnijs"'
In this work we study quantum algorithms for Hopcroft's problem which is a fundamental problem in computational geometry. Given $n$ points and $n$ lines in the plane, the task is to determine whether there is a point-line incidence. The classical com
Externí odkaz:
http://arxiv.org/abs/2405.01160
Publikováno v:
18th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2023)
We study variable time search, a form of quantum search where queries to different items take different time. Our first result is a new quantum algorithm that performs variable time search with complexity $O(\sqrt{T}\log n)$ where $T=\sum_{i=1}^n t_i
Externí odkaz:
http://arxiv.org/abs/2302.06749
In this paper, we study quantum algorithms for computing the exact value of the treewidth of a graph. Our algorithms are based on the classical algorithm by Fomin and Villanger (Combinatorica 32, 2012) that uses $O(2.616^n)$ time and polynomial space
Externí odkaz:
http://arxiv.org/abs/2202.08186
Autor:
Kokainis, Martins, Prūsis, Krišjānis, Vihrovs, Jevgēnijs, Kashcheyevs, Vyacheslavs, Ambainis, Andris
Publikováno v:
J. Phys. A: Math. Theor. 55 495301 (2022)
We show that the discrete time quantum walk on the Boolean hypercube of dimension $n$ has a strong dispersion property: if the walk is started in one vertex, then the probability of the walker being at any particular vertex after $O(n)$ steps is of a
Externí odkaz:
http://arxiv.org/abs/2201.11735
Motivated by the quantum speedup for dynamic programming on the Boolean hypercube by Ambainis et al. (2019), we investigate which graphs admit a similar quantum advantage. In this paper, we examine a generalization of the Boolean hypercube graph, the
Externí odkaz:
http://arxiv.org/abs/2104.14384
Autor:
Ambainis, Andris, Balodis, Kaspars, Iraids, Jānis, Khadiev, Kamil, Kļevickis, Vladislavs, Prūsis, Krišjānis, Shen, Yixin, Smotrovs, Juris, Vihrovs, Jevgēnijs
We study the quantum query complexity of two problems. First, we consider the problem of determining if a sequence of parentheses is a properly balanced one (a Dyck word), with a depth of at most $k$. We call this the $Dyck_{k,n}$ problem. We prove a
Externí odkaz:
http://arxiv.org/abs/2007.03402
We investigate the relation between the block sensitivity $\text{bs}(f)$ and fractional block sensitivity $\text{fbs}(f)$ complexity measures of Boolean functions. While it is known that $\text{fbs}(f) = O(\text{bs}(f)^2)$, the best known separation
Externí odkaz:
http://arxiv.org/abs/1810.02393
Motivated by cryptographic applications such as predicate encryption, we consider the problem of representing an arbitrary predicate as the inner product predicate on two vectors. Concretely, fix a Boolean function $P$ and some modulus $q$. We are in
Externí odkaz:
http://arxiv.org/abs/1810.02396
Autor:
Ambainis, Andris, Balodis, Kaspars, Iraids, Jānis, Kokainis, Martins, Prūsis, Krišjānis, Vihrovs, Jevgēnijs
In this paper we study quantum algorithms for NP-complete problems whose best classical algorithm is an exponential time application of dynamic programming. We introduce the path in the hypercube problem that models many of these dynamic programming
Externí odkaz:
http://arxiv.org/abs/1807.05209
Autor:
Ambainis, Andris, Kokainis, Martins, Prūsis, Krišjānis, Vihrovs, Jevgēnijs, Zajakins, Aleksejs
We show that all known classical adversary lower bounds on randomized query complexity are equivalent for total functions, and are equal to the fractional block sensitivity $\text{fbs}(f)$. That includes the Kolmogorov complexity bound of Laplante an
Externí odkaz:
http://arxiv.org/abs/1709.08985