0000000000824752
AUTHOR
Raitis Ozols
showing 7 related works from this author
Boolean Functions with a Low Polynomial Degree and Quantum Query Algorithms
2005
The complexity of quantum query algorithms computing Boolean functions is strongly related to the degree of the algebraic polynomial representing this Boolean function. There are two related difficult open problems. First, Boolean functions are sought for which the complexity of exact quantum query algorithms is essentially less than the complexity of deterministic query algorithms for the same function. Second, Boolean functions are sought for which the degree of the representing polynomial is essentially less than the complexity of deterministic query algorithms. We present in this paper new techniques to solve the second problem.
Quantum Strategies Are Better Than Classical in Almost Any XOR Game
2012
We initiate a study of random instances of nonlocal games. We show that quantum strategies are better than classical for almost any 2-player XOR game. More precisely, for large n, the entangled value of a random 2-player XOR game with n questions to every player is at least 1.21... times the classical value, for 1−o(1) fraction of all 2-player XOR games.
Search by Quantum Walks on Two-Dimensional Grid without Amplitude Amplification
2013
We study search by quantum walk on a finite two dimensional grid. The algorithm of Ambainis, Kempe, Rivosh [AKR05] uses \(O(\sqrt{N \log{N}})\) steps and finds a marked location with probability O(1 / logN) for grid of size \(\sqrt{N} \times \sqrt{N}\). This probability is small, thus [AKR05] needs amplitude amplification to get Θ(1) probability. The amplitude amplification adds an additional \(O(\sqrt{\log{N}})\) factor to the number of steps, making it \(O(\sqrt{N} \log{N})\).
Galīgi automāti, kas atpazīst valodas viena burta alfabētā
2013
Darbā tiks apskatīti galīgi determinēti un nedeterminēti automāti viena burta valodām un situācijām, kad visi ievadītie vārdi ir no kādas speciālas kopas (solījuma problēmas). Katrai apskatītajai valodai vai problēmai tiks meklēti atbilstošie automāti, kas tās atpazīst un kam ir iespējami mazs stāvokļu skaits. Papildus tiks izmantoti rezultāti no automātu teorijas un skaitļu teorijas. Darbā tiks parādīts, ka apskatītās problēmas nav triviālas – attiecīgo nedeterminēto automātu stāvokļu skaits ir saistīts ar vairākām speciālām funkcijām, piemēram, Landausa funkciju, kā arī ar Rīmaņa hipotēzi. Atslēgvārdi: Automāti, stāvokļu skaits, novērtējums, vārda garums.
Search by quantum walks on two-dimensional grid without amplitude amplification
2011
We study search by quantum walk on a finite two dimensional grid. The algorithm of Ambainis, Kempe, Rivosh (quant-ph/0402107) takes O(\sqrt{N log N}) steps and finds a marked location with probability O(1/log N) for grid of size \sqrt{N} * \sqrt{N}. This probability is small, thus amplitude amplification is needed to achieve \Theta(1) success probability. The amplitude amplification adds an additional O(\sqrt{log N}) factor to the number of steps, making it O(\sqrt{N} log N). In this paper, we show that despite a small probability to find a marked location, the probability to be within an O(\sqrt{N}) neighbourhood (at an O(\sqrt[4]{N}) distance) of the marked location is \Theta(1). This all…
Parameterized Quantum Query Complexity of Graph Collision
2013
We present three new quantum algorithms in the quantum query model for \textsc{graph-collision} problem: \begin{itemize} \item an algorithm based on tree decomposition that uses $O\left(\sqrt{n}t^{\sfrac{1}{6}}\right)$ queries where $t$ is the treewidth of the graph; \item an algorithm constructed on a span program that improves a result by Gavinsky and Ito. The algorithm uses $O(\sqrt{n}+\sqrt{\alpha^{**}})$ queries, where $\alpha^{**}(G)$ is a graph parameter defined by \[\alpha^{**}(G):=\min_{VC\text{-- vertex cover of}G}{\max_{\substack{I\subseteq VC\\I\text{-- independent set}}}{\sum_{v\in I}{\deg{v}}}};\] \item an algorithm for a subclass of circulant graphs that uses $O(\sqrt{n})$ qu…
Quantum strategies are better than classical in almost any XOR game
2011
We initiate a study of random instances of nonlocal games. We show that quantum strategies are better than classical for almost any 2-player XOR game. More precisely, for large n, the entangled value of a random 2-player XOR game with n questions to every player is at least 1.21... times the classical value, for 1-o(1) fraction of all 2-player XOR games.