7 Search Results for "Vihrovs, Jevgēnijs"


Document
Improved Algorithm and Lower Bound for Variable Time Quantum Search

Authors: Andris Ambainis, Martins Kokainis, and Jevgēnijs Vihrovs

Published in: LIPIcs, Volume 266, 18th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2023)


Abstract
We study variable time search, a form of quantum search where queries to different items take different time. Our first result is a new quantum algorithm that performs variable time search with complexity O(√Tlog n) where T = ∑_{i = 1}ⁿ t_i² with t_i denoting the time to check the i^th item. Our second result is a quantum lower bound of Ω(√{Tlog T}). Both the algorithm and the lower bound improve over previously known results by a factor of √{log T} but the algorithm is also substantially simpler than the previously known quantum algorithms.

Cite as

Andris Ambainis, Martins Kokainis, and Jevgēnijs Vihrovs. Improved Algorithm and Lower Bound for Variable Time Quantum Search. In 18th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 266, pp. 7:1-7:18, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)


Copy BibTex To Clipboard

@InProceedings{ambainis_et_al:LIPIcs.TQC.2023.7,
  author =	{Ambainis, Andris and Kokainis, Martins and Vihrovs, Jevg\={e}nijs},
  title =	{{Improved Algorithm and Lower Bound for Variable Time Quantum Search}},
  booktitle =	{18th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2023)},
  pages =	{7:1--7:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-283-9},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{266},
  editor =	{Fawzi, Omar and Walter, Michael},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.TQC.2023.7},
  URN =		{urn:nbn:de:0030-drops-183177},
  doi =		{10.4230/LIPIcs.TQC.2023.7},
  annote =	{Keywords: quantum search, amplitude amplification}
}
Document
Quantum Speedups for Treewidth

Authors: Vladislavs Kļevickis, Krišjānis Prūsis, and Jevgēnijs Vihrovs

Published in: LIPIcs, Volume 232, 17th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2022)


Abstract
In this paper, we study quantum algorithms for computing the exact value of the treewidth of a graph. Our algorithms are based on the classical algorithm by Fomin and Villanger (Combinatorica 32, 2012) that uses O(2.616ⁿ) time and polynomial space. We show three quantum algorithms with the following complexity, using QRAM in both exponential space algorithms: - O(1.618ⁿ) time and polynomial space; - O(1.554ⁿ) time and O(1.452ⁿ) space; - O(1.538ⁿ) time and space. In contrast, the fastest known classical algorithm for treewidth uses O(1.755ⁿ) time and space. The first two speed-ups are obtained in a fairly straightforward way. The first version uses additionally only Grover’s search and provides a quadratic speedup. The second speedup is more time-efficient and uses both Grover’s search and the quantum exponential dynamic programming by Ambainis et al. (SODA '19). The third version uses the specific properties of the classical algorithm and treewidth, with a modified version of the quantum dynamic programming on the hypercube. As a small side result, we give a new classical time-space tradeoff for computing treewidth in O^*(2ⁿ) time and O^*(√{2ⁿ}) space.

Cite as

Vladislavs Kļevickis, Krišjānis Prūsis, and Jevgēnijs Vihrovs. Quantum Speedups for Treewidth. In 17th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 232, pp. 11:1-11:18, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022)


Copy BibTex To Clipboard

@InProceedings{klevickis_et_al:LIPIcs.TQC.2022.11,
  author =	{K\c{l}evickis, Vladislavs and Pr\={u}sis, Kri\v{s}j\={a}nis and Vihrovs, Jevg\={e}nijs},
  title =	{{Quantum Speedups for Treewidth}},
  booktitle =	{17th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2022)},
  pages =	{11:1--11:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-237-2},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{232},
  editor =	{Le Gall, Fran\c{c}ois and Morimae, Tomoyuki},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.TQC.2022.11},
  URN =		{urn:nbn:de:0030-drops-165186},
  doi =		{10.4230/LIPIcs.TQC.2022.11},
  annote =	{Keywords: Quantum computation, Treewidth, Exact algorithms, Dynamic programming}
}
Document
Quantum Speedups for Dynamic Programming on n-Dimensional Lattice Graphs

Authors: Adam Glos, Martins Kokainis, Ryuhei Mori, and Jevgēnijs Vihrovs

Published in: LIPIcs, Volume 202, 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021)


Abstract
Motivated by the quantum speedup for dynamic programming on the Boolean hypercube by Ambainis et al. (2019), we investigate which graphs admit a similar quantum advantage. In this paper, we examine a generalization of the Boolean hypercube graph, the n-dimensional lattice graph Q(D,n) with vertices in {0,1,…,D}ⁿ. We study the complexity of the following problem: given a subgraph G of Q(D,n) via query access to the edges, determine whether there is a path from 0ⁿ to Dⁿ. While the classical query complexity is Θ̃((D+1)ⁿ), we show a quantum algorithm with complexity Õ(T_Dⁿ), where T_D < D+1. The first few values of T_D are T₁ ≈ 1.817, T₂ ≈ 2.660, T₃ ≈ 3.529, T₄ ≈ 4.421, T₅ ≈ 5.332. We also prove that T_D ≥ (D+1)/e (here, e ≈ 2.718 is the Euler’s number), thus for general D, this algorithm does not provide, for example, a speedup, polynomial in the size of the lattice. While the presented quantum algorithm is a natural generalization of the known quantum algorithm for D = 1 by Ambainis et al., the analysis of complexity is rather complicated. For the precise analysis, we use the saddle-point method, which is a common tool in analytic combinatorics, but has not been widely used in this field. We then show an implementation of this algorithm with time and space complexity poly(n)^{log n} T_Dⁿ in the QRAM model, and apply it to the Set Multicover problem. In this problem, m subsets of [n] are given, and the task is to find the smallest number of these subsets that cover each element of [n] at least D times. While the time complexity of the best known classical algorithm is O(m(D+1)ⁿ), the time complexity of our quantum algorithm is poly(m,n)^{log n} T_Dⁿ.

Cite as

Adam Glos, Martins Kokainis, Ryuhei Mori, and Jevgēnijs Vihrovs. Quantum Speedups for Dynamic Programming on n-Dimensional Lattice Graphs. In 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 202, pp. 50:1-50:23, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2021)


Copy BibTex To Clipboard

@InProceedings{glos_et_al:LIPIcs.MFCS.2021.50,
  author =	{Glos, Adam and Kokainis, Martins and Mori, Ryuhei and Vihrovs, Jevg\={e}nijs},
  title =	{{Quantum Speedups for Dynamic Programming on n-Dimensional Lattice Graphs}},
  booktitle =	{46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021)},
  pages =	{50:1--50:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-201-3},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{202},
  editor =	{Bonchi, Filippo and Puglisi, Simon J.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2021.50},
  URN =		{urn:nbn:de:0030-drops-144901},
  doi =		{10.4230/LIPIcs.MFCS.2021.50},
  annote =	{Keywords: Quantum query complexity, Dynamic programming, Lattice graphs}
}
Document
Quantum Lower and Upper Bounds for 2D-Grid and Dyck Language

Authors: Andris Ambainis, Kaspars Balodis, Jānis Iraids, Kamil Khadiev, Vladislavs Kļevickis, Krišjānis Prūsis, Yixin Shen, Juris Smotrovs, and Jevgēnijs Vihrovs

Published in: LIPIcs, Volume 170, 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020)


Abstract
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 √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 Õ(√n) query quantum algorithm was recently constructed by Aaronson et al. [Scott Aaronson et al., 2018]. 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(√n(log n)^{0.5k}) quantum queries for Dyck_{k,n} for all k. This is better than the trival upper bound n for k = o({log(n)}/{log log n}). 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.

Cite as

Andris Ambainis, Kaspars Balodis, Jānis Iraids, Kamil Khadiev, Vladislavs Kļevickis, Krišjānis Prūsis, Yixin Shen, Juris Smotrovs, and Jevgēnijs Vihrovs. Quantum Lower and Upper Bounds for 2D-Grid and Dyck Language. In 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 170, pp. 8:1-8:14, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2020)


Copy BibTex To Clipboard

@InProceedings{ambainis_et_al:LIPIcs.MFCS.2020.8,
  author =	{Ambainis, Andris and Balodis, Kaspars and Iraids, J\={a}nis and Khadiev, Kamil and K\c{l}evickis, Vladislavs and Pr\={u}sis, Kri\v{s}j\={a}nis and Shen, Yixin and Smotrovs, Juris and Vihrovs, Jevg\={e}nijs},
  title =	{{Quantum Lower and Upper Bounds for 2D-Grid and Dyck Language}},
  booktitle =	{45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020)},
  pages =	{8:1--8:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-159-7},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{170},
  editor =	{Esparza, Javier and Kr\'{a}l', Daniel},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2020.8},
  URN =		{urn:nbn:de:0030-drops-126774},
  doi =		{10.4230/LIPIcs.MFCS.2020.8},
  annote =	{Keywords: Quantum query complexity, Quantum algorithms, Dyck language, Grid path}
}
Document
Track A: Algorithms, Complexity and Games
A Composition Theorem for Randomized Query Complexity via Max-Conflict Complexity

Authors: Dmitry Gavinsky, Troy Lee, Miklos Santha, and Swagato Sanyal

Published in: LIPIcs, Volume 132, 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)


Abstract
For any relation f subseteq {0,1}^n x S and any partial Boolean function g:{0,1}^m -> {0,1,*}, we show that R_{1/3}(f o g^n) in Omega(R_{4/9}(f) * sqrt{R_{1/3}(g)}) , where R_epsilon(*) stands for the bounded-error randomized query complexity with error at most epsilon, and f o g^n subseteq ({0,1}^m)^n x S denotes the composition of f with n instances of g. The new composition theorem is optimal, at least, for the general case of relational problems: A relation f_0 and a partial Boolean function g_0 are constructed, such that R_{4/9}(f_0) in Theta(sqrt n), R_{1/3}(g_0)in Theta(n) and R_{1/3}(f_0 o g_0^n) in Theta(n). The theorem is proved via introducing a new complexity measure, max-conflict complexity, denoted by bar{chi}(*). Its investigation shows that bar{chi}(g) in Omega(sqrt{R_{1/3}(g)}) for any partial Boolean function g and R_{1/3}(f o g^n) in Omega(R_{4/9}(f) * bar{chi}(g)) for any relation f, which readily implies the composition statement. It is further shown that bar{chi}(g) is always at least as large as the sabotage complexity of g.

Cite as

Dmitry Gavinsky, Troy Lee, Miklos Santha, and Swagato Sanyal. A Composition Theorem for Randomized Query Complexity via Max-Conflict Complexity. In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 132, pp. 64:1-64:13, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2019)


Copy BibTex To Clipboard

@InProceedings{gavinsky_et_al:LIPIcs.ICALP.2019.64,
  author =	{Gavinsky, Dmitry and Lee, Troy and Santha, Miklos and Sanyal, Swagato},
  title =	{{A Composition Theorem for Randomized Query Complexity via Max-Conflict Complexity}},
  booktitle =	{46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)},
  pages =	{64:1--64:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-109-2},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{132},
  editor =	{Baier, Christel and Chatzigiannakis, Ioannis and Flocchini, Paola and Leonardi, Stefano},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2019.64},
  URN =		{urn:nbn:de:0030-drops-106407},
  doi =		{10.4230/LIPIcs.ICALP.2019.64},
  annote =	{Keywords: query complexity, lower bounds}
}
Document
On the Inner Product Predicate and a Generalization of Matching Vector Families

Authors: Balthazar Bauer, Jevgenijs Vihrovs, and Hoeteck Wee

Published in: LIPIcs, Volume 122, 38th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2018)


Abstract
Motivated by cryptographic applications such as predicate encryption, we consider the problem of representing an arbitrary predicate as the inner product predicate on two vectors. Concretely, fix a Boolean function P and some modulus q. We are interested in encoding x to x_vector and y to y_vector so that P(x,y) = 1 <=> <x_vector,y_vector> = 0 mod q, where the vectors should be as short as possible. This problem can also be viewed as a generalization of matching vector families, which corresponds to the equality predicate. Matching vector families have been used in the constructions of Ramsey graphs, private information retrieval (PIR) protocols, and more recently, secret sharing. Our main result is a simple lower bound that allows us to show that known encodings for many predicates considered in the cryptographic literature such as greater than and threshold are essentially optimal for prime modulus q. Using this approach, we also prove lower bounds on encodings for composite q, and then show tight upper bounds for such predicates as greater than, index and disjointness.

Cite as

Balthazar Bauer, Jevgenijs Vihrovs, and Hoeteck Wee. On the Inner Product Predicate and a Generalization of Matching Vector Families. In 38th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 122, pp. 41:1-41:13, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2018)


Copy BibTex To Clipboard

@InProceedings{bauer_et_al:LIPIcs.FSTTCS.2018.41,
  author =	{Bauer, Balthazar and Vihrovs, Jevgenijs and Wee, Hoeteck},
  title =	{{On the Inner Product Predicate and a Generalization of Matching Vector Families}},
  booktitle =	{38th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2018)},
  pages =	{41:1--41:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-093-4},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{122},
  editor =	{Ganguly, Sumit and Pandya, Paritosh},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2018.41},
  URN =		{urn:nbn:de:0030-drops-99400},
  doi =		{10.4230/LIPIcs.FSTTCS.2018.41},
  annote =	{Keywords: Predicate Encryption, Inner Product Encoding, Matching Vector Families}
}
Document
All Classical Adversary Methods are Equivalent for Total Functions

Authors: Andris Ambainis, Martins Kokainis, Krisjanis Prusis, and Jevgenijs Vihrovs

Published in: LIPIcs, Volume 96, 35th Symposium on Theoretical Aspects of Computer Science (STACS 2018)


Abstract
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. For partial functions, we show unbounded separations between fbs(f) and other adversary bounds, as well as between the relational and Kolmogorov complexity bounds. We also show that, for partial functions, fractional block sensitivity cannot give lower bounds larger than sqrt(n * bs(f)), where n is the number of variables and bs(f) is the block sensitivity. Then we exhibit a partial function f that matches this upper bound, fbs(f) = Omega(sqrt(n * bs(f))).

Cite as

Andris Ambainis, Martins Kokainis, Krisjanis Prusis, and Jevgenijs Vihrovs. All Classical Adversary Methods are Equivalent for Total Functions. In 35th Symposium on Theoretical Aspects of Computer Science (STACS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 96, pp. 8:1-8:14, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2018)


Copy BibTex To Clipboard

@InProceedings{ambainis_et_al:LIPIcs.STACS.2018.8,
  author =	{Ambainis, Andris and Kokainis, Martins and Prusis, Krisjanis and Vihrovs, Jevgenijs},
  title =	{{All Classical Adversary Methods are Equivalent for Total Functions}},
  booktitle =	{35th Symposium on Theoretical Aspects of Computer Science (STACS 2018)},
  pages =	{8:1--8:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-062-0},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{96},
  editor =	{Niedermeier, Rolf and Vall\'{e}e, Brigitte},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2018.8},
  URN =		{urn:nbn:de:0030-drops-84953},
  doi =		{10.4230/LIPIcs.STACS.2018.8},
  annote =	{Keywords: Randomized Query Complexity, Lower Bounds, Adversary Bounds, Fractional Block Sensitivity}
}
  • Refine by Author
  • 4 Vihrovs, Jevgēnijs
  • 3 Ambainis, Andris
  • 3 Kokainis, Martins
  • 2 Kļevickis, Vladislavs
  • 2 Prūsis, Krišjānis
  • Show More...

  • Refine by Classification
  • 3 Theory of computation → Quantum query complexity
  • 1 Security and privacy → Public key encryption
  • 1 Theory of computation → Dynamic programming
  • 1 Theory of computation → Oracles and decision trees
  • 1 Theory of computation → Parameterized complexity and exact algorithms
  • Show More...

  • Refine by Keyword
  • 2 Dynamic programming
  • 2 Quantum query complexity
  • 1 Adversary Bounds
  • 1 Dyck language
  • 1 Exact algorithms
  • Show More...

  • Refine by Type
  • 7 document

  • Refine by Publication Year
  • 2 2018
  • 1 2019
  • 1 2020
  • 1 2021
  • 1 2022
  • Show More...

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail