Source author record

Jānis Iraids

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

quant-ph Computational Complexity Data Structures and Algorithms math.NT

Catalog footprint

Research overview

8works

4topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2020arXiv

Quantum Lower and Upper Bounds for 2D-Grid and Dyck Language

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 lower bound of $Ω(c^k \sqrt{n})$ , showing that the complexity of this problem increases exponentially in $k$ . Here $n$ is the length of the word. When $k$ is a constant, this is interesting as a representative example of star-free languages for which a surprising $\tilde{O}(\sqrt{n})$ query quantum algorithm was recently constructed by Aaronson et al. Their proof does not give rise to a general algorithm. When $k$ is not a constant, $Dyck_{k,n}$ is not context-free. We give an algorithm with $O\left(\sqrt{n}(\log{n})^{0.5k}\right)$ quantum queries for $Dyck_{k,n}$ for all $k$ . This is better than the trival upper bound $n$ for $k=o\left(\frac{\log(n)}{\log\log n}\right)$ . Second, we consider connectivity problems on grid graphs in 2 dimensions, if some of the edges of the grid may be missing. By embedding the "balanced parentheses" problem into the grid, we show a lower bound of $Ω(n^{1.5-ε})$ for the directed 2D grid and $Ω(n^{2-ε})$ for the undirected 2D grid. The directed problem is interesting as a black-box model for a class of classical dynamic programming strategies including the one that is usually used for the well-known edit distance problem. We also show a generalization of this result to more than 2 dimensions.

preprint2016arXiv

Polynomials, Quantum Query Complexity, and Grothendieck's Inequality

We show an equivalence between 1-query quantum algorithms and representations by degree-2 polynomials. Namely, a partial Boolean function $f$ is computable by a 1-query quantum algorithm with error bounded by $ε<1/2$ iff $f$ can be approximated by a degree-2 polynomial with error bounded by $ε'<1/2$ . This result holds for two different notions of approximation by a polynomial: the standard definition of Nisan and Szegedy and the approximation by block-multilinear polynomials recently introduced by Aaronson and Ambainis (STOC'2015, arxiv:1411.5729). We also show two results for polynomials of higher degree. First, there is a total Boolean function which requires $\tildeΩ(n)$ quantum queries but can be represented by a block-multilinear polynomial of degree $\tilde{O}(\sqrt{n})$ . Thus, in the general case (for an arbitrary number of queries), block-multilinear polynomials are not equivalent to quantum algorithms. Second, for any constant degree $k$ , the two notions of approximation by a polynomial (the standard and the block-multilinear) are equivalent. As a consequence, we solve an open problem of Aaronson and Ambainis, showing that one can estimate the value of any bounded degree- $k$ polynomial $p:\{0, 1\}^n \rightarrow [-1, 1]$ with $O(n^{1-\frac{1}{2k}})$ queries.

preprint2015arXiv

Quantum Lower Bound for Graph Collision Implies Lower Bound for Triangle Detection

We show that an improvement to the best known quantum lower bound for GRAPH-COLLISION problem implies an improvement to the best known lower bound for TRIANGLE problem in the quantum query complexity model. In GRAPH-COLLISION we are given free access to a graph $(V,E)$ and access to a function $f:V\rightarrow \{0,1\}$ as a black box. We are asked to determine if there exist $(u,v) \in E$ , such that $f(u)=f(v)=1$ . In TRIANGLE we have a black box access to an adjacency matrix of a graph and we have to determine if the graph contains a triangle. For both of these problems the known lower bounds are trivial ( $Ω(\sqrt{n})$ and $Ω(n)$ , respectively) and there is no known matching upper bound.

preprint2014arXiv

Integer Complexity: Experimental and Analytical Results II

We consider representing of natural numbers by expressions using 1's, addition, multiplication and parentheses. $\left\| n \right\|$ denotes the minimum number of 1's in the expressions representing $n$ . The logarithmic complexity $\left\| n \right\|_{\log}$ is defined as $\left\| n \right\|/{\log_3 n}$ . The values of $\left\| n \right\|_{\log}$ are located in the segment $[3, 4.755]$ , but almost nothing is known with certainty about the structure of this "spectrum" (are the values dense somewhere in the segment etc.). We establish a connection between this problem and another difficult problem: the seemingly "almost random" behaviour of digits in the base 3 representations of the numbers $2^n$ . We consider also representing of natural numbers by expressions that include subtraction, and the so-called $P$ -algorithms - a family of "deterministic" algorithms for building representations of numbers.

preprint2013arXiv

Exact quantum query complexity of EXACT and THRESHOLD

A quantum algorithm is exact if it always produces the correct answer, on any input. Coming up with exact quantum algorithms that substantially outperform the best classical algorithm has been a quite challenging task. In this paper, we present two new exact quantum algorithms for natural problems: 1) for the problem EXACT_k^n in which we have to determine whether the sequence of input bits x_1, ..., x_n contains exactly k values x_i=1; 2) for the problem THRESHOLD_k^n in which we have to determine if at least k of n input bits are equal to 1.

preprint2013arXiv

Parameterized Quantum Query Complexity of Graph Collision

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{α^{**}})$ queries, where $α^{**}(G)$ is a graph parameter defined by $α^{**}(G):=\min_{VC\text{-- vertex cover of}G}{\max_{\substack{I\subseteq VC\\I\text{-- independent set}}}{\sum_{v\in I}{°{v}}}};$ \item an algorithm for a subclass of circulant graphs that uses $O(\sqrt{n})$ queries. \end{itemize} We also present an example of a possibly difficult graph $G$ for which all the known graphs fail to solve graph collision in $O(\sqrt{n} \log^c n)$ queries.

preprint2013arXiv

Provable Advantage for Quantum Strategies in Random Symmetric XOR Games

Non-local games are widely studied as a model to investigate the properties of quantum mechanics as opposed to classical mechanics. In this paper, we consider a subset of non-local games: symmetric XOR games of $n$ players with 0-1 valued questions. For this class of games, each player receives an input bit and responds with an output bit without communicating to the other players. The winning condition only depends on XOR of output bits and is constant w.r.t. permutation of players. We prove that for almost any $n$ -player symmetric XOR game the entangled value of the game is $Θ(\frac{\sqrt{\ln{n}}}{n^{1/4}})$ adapting an old result by Salem and Zygmund on the asymptotics of random trigonometric polynomials. Consequently, we show that the classical-quantum gap is $Θ(\sqrt{\ln{n}})$ for almost any symmetric XOR game.

preprint2012arXiv

Integer Complexity: Experimental and Analytical Results

We consider representing of natural numbers by arithmetical expressions using ones, addition, multiplication and parentheses. The (integer) complexity of n -- denoted by ||n|| -- is defined as the number of ones in the shortest expressions representing n. We arrive here very soon at the problems that are easy to formulate, but (it seems) extremely hard to solve. In this paper we represent our attempts to explore the field by means of experimental mathematics. Having computed the values of ||n|| up to 10^12 we present our observations. One of them (if true) implies that there is an infinite number of Sophie Germain primes, and even that there is an infinite number of Cunningham chains of length 4 (at least). We prove also some analytical results about integer complexity.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Jānis Iraids

Research overview

Is this your work?

8 publications

Quantum Lower and Upper Bounds for 2D-Grid and Dyck Language

Polynomials, Quantum Query Complexity, and Grothendieck's Inequality

Quantum Lower Bound for Graph Collision Implies Lower Bound for Triangle Detection

Integer Complexity: Experimental and Analytical Results II

Exact quantum query complexity of EXACT and THRESHOLD

Parameterized Quantum Query Complexity of Graph Collision

Provable Advantage for Quantum Strategies in Random Symmetric XOR Games

Integer Complexity: Experimental and Analytical Results

See the researcher in context

Building this map preview