Jānis Iraids
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Previous Organizations / Institutes
The organizations / institutes from the scholar's other articles in the past ten years
Research Subjects
Research Interests
Jānis Iraids has a total of 22 co-authors. Here are the top co-authors by number of shared publications:
- Agris Šostaks
University of Latvia
3 shared publications - Andris Ambainis
Faculty of Computing University of Latvia
3 shared publications - Audris Kalnins
Institute of Mathematics and Computer Science, University of Latvia
3 shared publications - Elina Kalnina
Institute of Mathematics and Computer Science, University of Latvia, LV-1459 Riga, Latvia
3 shared publications Andris Ambainis
University of Latvia
2 shared publications- Daniel Nagaj
Institute of Physics RCQI Slovak Academy of Sciences Bratislava Slovakia
2 shared publications
Latest Publications
- Open AccessExact quantum query complexity of $\rm{EXACT}_{k,l}^n$In the exact quantum query model a successful algorithm must always output the correct function value. We investigate the function that is true if exactly $k$ or $l$ of the $n$ input bits given by an oracle are 1. We find an optimal algorithm (for some cases), and a nontrivial general lower and upper bound on the minimum number of queries to the black box.Open AccessExact quantum query complexity of $\rm{EXACT}_{k,l}^n$In the exact quantum query model a successful algorithm must always output the correct function value. We investigate the function that is true if exactly $k$ or $l$ of the $n$ input bits given by an oracle are 1. We find an optimal algorithm (for some cases), and a nontrivial general lower and upper bound on the minimum number of queries to the black box.
- Open Access
Optimal one-shot quantum algorithm for EQUALITY and AND
We study the computation complexity of Boolean functions in the quantum black box model. In this model our task is to compute a function $f:\{0,1\}\to\{0,1\}$ on an input $x\in\{0,1\}^n$ that can be accessed by querying the black box. Quantum algorithms are inherently probabilistic; we are interested in the lowest possible probability that the algorithm outputs incorrect answer (the error probability) for a fixed number of queries. We show that the lowest possible error probability for $AND_n$ and $EQUALITY_{n+1}$ is $1/2-n/(n^2+1)$.Open AccessOptimal one-shot quantum algorithm for EQUALITY and AND
We study the computation complexity of Boolean functions in the quantum black box model. In this model our task is to compute a function $f:\{0,1\}\to\{0,1\}$ on an input $x\in\{0,1\}^n$ that can be accessed by querying the black box. Quantum algorithms are inherently probabilistic; we are interested in the lowest possible probability that the algorithm outputs incorrect answer (the error probability) for a fixed number of queries. We show that the lowest possible error probability for $AND_n$ and $EQUALITY_{n+1}$ is $1/2-n/(n^2+1)$. - 11 January 2017
- Published by Springer Nature
- p. 243-255
Exact Quantum Query Complexity of $\text {EXACT}_{k,l}^n$- 11 January 2017
- Published by Springer Nature
- p. 243-255
Exact Quantum Query Complexity of $\text {EXACT}_{k,l}^n$- Open Access
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 $\epsilon<1/2$ iff $f$ can be approximated by a degree-2 polynomial with error bounded by $\epsilon'<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{\Omega}(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.Open AccessPolynomials, 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 $\epsilon<1/2$ iff $f$ can be approximated by a degree-2 polynomial with error bounded by $\epsilon'<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{\Omega}(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. - 16 June 2015
- Published by Springer Nature
- p. 58-69
Integer Complexity: Experimental and Analytical Results II
- 16 June 2015
- Published by Springer Nature
- p. 58-69
Integer Complexity: Experimental and Analytical Results II
- 16 April 2015
- Published by Springer Nature
- p. 50-61
Structured Frequency Algorithms
- 1 January 2013
- Published by Springer Nature
- p. 57-68
Advantage of Quantum Strategies in Random Symmetric XOR Games
- 1 January 2013
- Published by Springer Nature
- p. 57-68
Advantage of Quantum Strategies in Random Symmetric XOR Games
- 1 January 2012
- Published by Springer Nature in Lecture Notes in Computer Science
- p. 492-504
Tree Based Domain-Specific Mapping Languages
- 1 January 2012
- Published by Springer Nature in Lecture Notes in Computer Science
- p. 492-504
Tree Based Domain-Specific Mapping Languages
- Open Access
- 16 November 2011
- Published by Open Publishing Association in Electronic Proceedings in Theoretical Computer Science
- Vol. 74, 237-252
Saying Hello World with MOLA - A Solution to the TTC 2011 Instructive Case
This paper describes the solution of Hello World transformations in MOLA transformation language. Transformations implementing the task are relatively straightforward and easily inferable from the task specification. The required additional steps related to model import and export are also described.Comment: In Proceedings TTC 2011, arXiv:1111.440
- 16 November 2011
- Published by Open Publishing Association in Electronic Proceedings in Theoretical Computer Science
- Vol. 74, 237-252
Open AccessSaying Hello World with MOLA - A Solution to the TTC 2011 Instructive Case
This paper describes the solution of Hello World transformations in MOLA transformation language. Transformations implementing the task are relatively straightforward and easily inferable from the task specification. The required additional steps related to model import and export are also described.Comment: In Proceedings TTC 2011, arXiv:1111.440
- Open Access
- 16 November 2011
- Published by Open Publishing Association in Electronic Proceedings in Theoretical Computer Science
- Vol. 74, 159-167
Solving the TTC 2011 Reengineering Case with MOLA and Higher-Order Transformations
The Reengineering Case of the Transformation Tool Contest 2011 deals with automatic extraction of state machine from Java source code. The transformation task involves complex, non-local matching of model elements. This paper contains the solution of the task using model transformation language MOLA. The MOLA solution uses higher-order transformations (HOT-s) to generate a part of the required MOLA program. The described HOT approach allows creating reusable, complex model transformation libraries for generic tasks without modifying an implementation of a model transformation language. Thus model transformation users who are not the developers of the language can achieve the desired functionality more easily.Comment: In Proceedings TTC 2011, arXiv:1111.440
- 16 November 2011
- Published by Open Publishing Association in Electronic Proceedings in Theoretical Computer Science
- Vol. 74, 159-167
Open AccessSolving the TTC 2011 Reengineering Case with MOLA and Higher-Order Transformations
The Reengineering Case of the Transformation Tool Contest 2011 deals with automatic extraction of state machine from Java source code. The transformation task involves complex, non-local matching of model elements. This paper contains the solution of the task using model transformation language MOLA. The MOLA solution uses higher-order transformations (HOT-s) to generate a part of the required MOLA program. The described HOT approach allows creating reusable, complex model transformation libraries for generic tasks without modifying an implementation of a model transformation language. Thus model transformation users who are not the developers of the language can achieve the desired functionality more easily.Comment: In Proceedings TTC 2011, arXiv:1111.440