0000000000521292
AUTHOR
Jevgēnijs Vihrovs
showing 14 related works from this author
Limitations of Quantum Walks and Randomized Algorithms
2019
Šajā darbā tiek pētīta algoritmu sarežģītība dažādos skaitļošanas modeļos. Konkrētāk, tiek pētītas kvantu klejošanas algoritmu īpašības un ierobežojumi, kā arī varbūtisko vaicājumalgoritmu darbības laika novērtēšanas metodes. Pirmajā daļā tiek aplūkotas Grovera kvantu klejošana un meklēšana grafos. Darbā tiek sniegts vispārīgs matemātisks apraksts klejošanas lokalizācijai un meklēšanas stacionārajiem stāvokļiem. Otrajā daļā tiek aplūkotas apakšējo novērtējumu metodes varbūtisko vaicājumalgoritmu modelī. Darbā tiek pierādīta klasisko pretinieka metožu asimptotiskā ekvivalence visur definētām funkcijām, un aprakstītas to atšķirības daļēji definētām funkcijām. Tiek arī aplūkota saistība starp …
Quadratically Tight Relations for Randomized Query Complexity
2020
In this work we investigate the problem of quadratically tightly approximating the randomized query complexity of Boolean functions R(f). The certificate complexity C(f) is such a complexity measure for the zero-error randomized query complexity R0(f): C(f) ≤R0(f) ≤C(f)2. In the first part of the paper we introduce a new complexity measure, expectational certificate complexity EC(f), which is also a quadratically tight bound on R0(f): EC(f) ≤R0(f) = O(EC(f)2). For R(f), we prove that EC2/3 ≤R(f). We then prove that EC(f) ≤C(f) ≤EC(f)2 and show that there is a quadratic separation between the two, thus EC(f) gives a tighter upper bound for R0(f). The measure is also related to the fractional…
Doubling the success of quantum walk search using internal-state measurements
2015
In typical discrete-time quantum walk algorithms, one measures the position of the walker while ignoring its internal spin/coin state. Rather than neglecting the information in this internal state, we show that additionally measuring it doubles the success probability of many quantum spatial search algorithms. For example, this allows Grover's unstructured search problem to be solved with certainty, rather than with probability 1/2 if only the walker's position is measured, so the additional measurement yields a search algorithm that is twice as fast as without it, on average. Thus the internal state of discrete-time quantum walks holds valuable information that can be utilized to improve a…
Stationary states in quantum walk search
2016
When classically searching a database, having additional correct answers makes the search easier. For a discrete-time quantum walk searching a graph for a marked vertex, however, additional marked vertices can make the search harder by causing the system to approximately begin in a stationary state, so the system fails to evolve. In this paper, we completely characterize the stationary states, or 1-eigenvectors, of the quantum walk search operator for general graphs and configurations of marked vertices by decomposing their amplitudes into uniform and flip states. This infinitely expands the number of known stationary states and gives an optimization procedure to find the stationary state c…
On Block Sensitivity and Fractional Block Sensitivity
2018
We investigate the relation between the block sensitivity bs(f) and fractional block sensitivity fbs(f) complexity measures of Boolean functions. While it is known that fbs(f) = O(bs(f)2), the best known separation achieves $${\rm{fbs}}\left( f \right) = \left( {{{\left( {3\sqrt 2 } \right)}^{ - 1}} + o\left( 1 \right)} \right){\rm{bs}}{\left( f \right)^{3/2}}$$ . We improve the constant factor and show a family of functions that give fbs(f) = (6−1/2 − o(1)) bs(f)3/2.
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…
Exact affine counter automata
2017
We introduce an affine generalization of counter automata, and analyze their ability as well as affine finite automata. Our contributions are as follows. We show that there is a language that can be recognized by exact realtime affine counter automata but by neither 1-way deterministic pushdown automata nor realtime deterministic k-counter automata. We also show that a certain promise problem, which is conjectured not to be solved by two-way quantum finite automata in polynomial time, can be solved by Las Vegas affine finite automata. Lastly, we show that how a counter helps for affine finite automata by showing that the language MANYTWINS, which is conjectured not to be recognized by affin…
A Potential Field Function for Overlapping Point Set and Graph Cluster Visualization
2015
In this paper we address the problem of visualizing overlapping sets of points with a fixed positioning in a comprehensible way. A standard visualization technique is to enclose the point sets in isocontours generated by bounding a potential field function. The most commonly used functions are various approximations of the Gaussian distribution. Such an approach produces smooth and appealing shapes, however it may produce an incorrect point nesting in generated regions, e.g. some point is contained inside a foreign set region. We introduce a different potential field function that keeps the desired properties of Gaussian distribution, and in addition guarantees that every point belongs to a…
Size of Sets with Small Sensitivity: A Generalization of Simon’s Lemma
2015
We study the structure of sets \(S\subseteq \{0, 1\}^n\) with small sensitivity. The well-known Simon’s lemma says that any \(S\subseteq \{0, 1\}^n\) of sensitivity \(s\) must be of size at least \(2^{n-s}\). This result has been useful for proving lower bounds on the sensitivity of Boolean functions, with applications to the theory of parallel computing and the “sensitivity vs. block sensitivity” conjecture.
Oscillatory Localization of Quantum Walks Analyzed by Classical Electric Circuits
2016
We examine an unexplored quantum phenomenon we call oscillatory localization, where a discrete-time quantum walk with Grover's diffusion coin jumps back and forth between two vertices. We then connect it to the power dissipation of a related electric network. Namely, we show that there are only two kinds of oscillating states, called uniform states and flip states, and that the projection of an arbitrary state onto a flip state is bounded by the power dissipation of an electric circuit. By applying this framework to states along a single edge of a graph, we show that low effective resistance implies oscillatory localization of the quantum walk. This reveals that oscillatory localization occ…
Būla virkņu kopu jūtīgums
2013
Jūtīgums s(f) un bloku jūtīgums bs(f) ir divi plaši lietoti Būla funkciju sarežģītības mēri. Tie ir cieši saistīti ar daudziem citiem sarežģītības mēriem. Jautājums par asimptotisko attiecību starp šiem lielumiem jau ilgu laiku paliek neatrisināts, un vislabākais novērtējums sasniedz kvadrātisku atstarpi: bs(f) = Ω(s(f)^2). Darbā tiek risināts ar šo problēmu saistīts uzdevums: kāds ir mazākais iespējamais Būla virkņu kopas S ar jūtīgumu s izmērs pie nosacījuma, ka katra maska ar tieši k nofiksētiem bitiem satur vismaz vienu no S virsotnēm. Iepriekš tika atrisināts gadījums k = 0, un iegūtais rezultāts pielietots, lai uzlabotu asimptotiskās attiecības dažādiem funkciju sarežģītības mēriem. Š…
Fakultātes zinātnisko publikāciju uzskaites sistēma
2011
Darbā tiek aprakstīta zinātnisko publikāciju uzskaites sistēma, kas ļauj apskatīt un pārvaldīt publicētus akadēmiskos rakstus. Sistēma tiek izstrādāta kā tīmekļa vietne, kas ir brīvi pieejama jebkuram interneta lietotājam. Programmatūra tiek realizēta, izmantojot HTML, PHP, JavaScript, MySQL u.c. tīmekļa izstrādes tehnoloģijas. Sistēma galvenokārt ir paredzēta Latvijas Universitātes Datorikas fakultātes darbinieku zinātnisko publikāciju uzskaitei un pašlaik tiek ieviesta lietošanā.
Jaunas sakarības starp Būla funkciju jutīgumu un bloku jutīgumu
2015
Darbā tiek pētīta neatrisināta problēma skaitļošanas sarežģītības teorijā – Būla funkciju jutīguma s(f) saistība ar tādiem sarežģītības mēriem kā bloku jutīgums bs(f) un sertifikātu sarežģītība C(f). Populāra hipotēze apgalvo, ka jutīgums ir polinomiāli saistīts ar bloku jutīgumu un bs(f) = O(s(f)^c) kādai konstantei c. Līdz šim labākais zināmais novērtējums no augšas abiem mēriem ir eksponenciāls, bs(f) ≤ C(f) ≤ 2^(s(f)-1) s(f) - s(f) + 1, bet labākie atrastie piemēri sasniedz tikai kvadrātisku atstarpi, bs(f) = Ω(s(f)^2). Šajā darbā tiek pierādīts jauns novērtējums no augšas, bs(f) ≤ C(f) ≤ max(2^(s(f)-1) (s(f) - 1/3), s(f)).
Full Characterization of Oscillatory Localization of Quantum Walks
2016
Discrete-time quantum walks are well-known for exhibiting localization, a quantum phenomenon where the walker remains at its initial location with high probability. In companion with a joint Letter, we introduce oscillatory localization, where the walker alternates between two states. The walk is given by the flip-flop shift, which is easily defined on non-lattice graphs, and the Grover coin. Extremely simple examples of the localization exist, such as a walker jumping back and forth between two vertices of the complete graph. We show that only two kinds of states, called flip states and uniform states, exhibit exact oscillatory localization. So the projection of an arbitrary state onto the…