0000000000049771
AUTHOR
Martins Kokainis
showing 9 related works from this author
Approximation properties of higher degree F-transforms based on B-splines
2015
The paper deals with the F-transform with polynomial components with respect to a generalized fuzzy partition given by B-splines. We investigate approximation properties of the inverse F-transform in this case and prove that using B-splines allows us to improve the quality of approximation of smooth functions.
Quantum algorithm for tree size estimation, with applications to backtracking and 2-player games
2017
We study quantum algorithms on search trees of unknown structure, in a model where the tree can be discovered by local exploration. That is, we are given the root of the tree and access to a black box which, given a vertex $v$, outputs the children of $v$. We construct a quantum algorithm which, given such access to a search tree of depth at most $n$, estimates the size of the tree $T$ within a factor of $1\pm \delta$ in $\tilde{O}(\sqrt{nT})$ steps. More generally, the same algorithm can be used to estimate size of directed acyclic graphs (DAGs) in a similar model. We then show two applications of this result: a) We show how to transform a classical backtracking search algorithm which exam…
Quadratic speedup for finding marked vertices by quantum walks
2020
A quantum walk algorithm can detect the presence of a marked vertex on a graph quadratically faster than the corresponding random walk algorithm (Szegedy, FOCS 2004). However, quantum algorithms that actually find a marked element quadratically faster than a classical random walk were only known for the special case when the marked set consists of just a single vertex, or in the case of some specific graphs. We present a new quantum algorithm for finding a marked vertex in any graph, with any set of marked vertices, that is (up to a log factor) quadratically faster than the corresponding classical random walk.
A random-walk benchmark for single-electron circuits
2021
Mesoscopic integrated circuits aim for precise control over elementary quantum systems. However, as fidelities improve, the increasingly rare errors and component crosstalk pose a challenge for validating error models and quantifying accuracy of circuit performance. Here we propose and implement a circuit-level benchmark that models fidelity as a random walk of an error syndrome, detected by an accumulating probe. Additionally, contributions of correlated noise, induced environmentally or by memory, are revealed as limits of achievable fidelity by statistical consistency analysis of the full distribution of error counts. Applying this methodology to a high-fidelity implementation of on-dema…
Collocation Method for Linear BVPs via B-spline Based Fuzzy Transform
2018
The paper is devoted to an application of a modified F-transform technique based on B-splines in solving linear boundary value problems via the collocation method. An approximate solution is sought as a composite F-transform of a discrete function (which allows the solution to be compactly stored as the values of this discrete function). We demonstrate the effectiveness of the described technique with numerical examples, compare it with other methods and propose theoretical results on the order of approximation when the fuzzy partition is based on cubic B-splines.
All Classical Adversary Methods Are Equivalent for Total Functions
2017
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 fbs( f ). That includes the Kolmogorov complexity bound of Laplante and Magniez and the earlier relational adversary bound of Aaronson. This equivalence also implies that for total functions, the relational adversary is equivalent to a simpler lower bound, which we call rank-1 relational adversary. For partial functions, we show unbounded separations between fbs( f ) and other adversary bounds, as well as between the adversary bounds themselves. We also show that, for partial functions, fractional block sensitivity canno…
Modified F-transform Based on B-splines
2018
The aim of this paper is to improve the F-transform technique based on B-splines. A modification of the F-transform of higher degree with respect to fuzzy partitions based on B-splines is done to extend the good approximation properties from the interval where the Ruspini condition is fulfilled to the whole interval under consideration. The effect of the proposed modification is characterized theoretically and illustrated numerically.
Higher Degree F-transforms Based on B-splines of Two Variables
2016
The paper deals with the higher degree fuzzy transforms (F-transforms with polynomial components) for functions of two variables in the case when two-dimensional generalized fuzzy partition is given by B-splines of two variables. We investigate properties of the direct and inverse F-transform in this case and prove that using B-splines as basic functions of fuzzy partition allows us to improve the quality of approximation.
Quantum Speedups for Exponential-Time Dynamic Programming Algorithms
2018
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 algorithms. In this problem we are asked whether there is a path from $0^n$ to $1^n$ in a given subgraph of the Boolean hypercube, where the edges are all directed from smaller to larger Hamming weight. We give a quantum algorithm that solves path in the hypercube in time $O^*(1.817^n)$. The technique combines Grover's search with computing a partial dynamic programming table. We use this approach to solve a variety of vertex ordering problems o…