2 Search Results for "Mori, Ryuhei"

Document
DOI: 10.4230/LIPIcs.MFCS.2021.50
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-dev.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
DOI: 10.4230/LIPIcs.APPROX-RANDOM.2016.41
Lower Bounds for CSP Refutation by SDP Hierarchies

Authors: Ryuhei Mori and David Witmer

Published in: LIPIcs, Volume 60, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2016)

Abstract
For a k-ary predicate P, a random instance of CSP(P) with n variables and m constraints is unsatisfiable with high probability when m >= O(n). The natural algorithmic task in this regime is refutation: finding a proof that a given random instance is unsatisfiable. Recent work of Allen et al. suggests that the difficulty of refuting CSP(P) using an SDP is determined by a parameter cmplx(P), the smallest t for which there does not exist a t-wise uniform distribution over satisfying assignments to P. In particular they show that random instances of CSP(P) with m >> n^{cmplx(P)/2} can be refuted efficiently using an SDP. In this work, we give evidence that n^{cmplx(P)/2} constraints are also necessary for refutation using SDPs. Specifically, we show that if P supports a (t-1)-wise uniform distribution over satisfying assignments, then the Sherali-Adams_+ and Lovasz-Schrijver_+ SDP hierarchies cannot refute a random instance of CSP(P) in polynomial time for any m <= n^{t/2-epsilon}.
Cite as

Ryuhei Mori and David Witmer. Lower Bounds for CSP Refutation by SDP Hierarchies. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 60, pp. 41:1-41:30, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{mori_et_al:LIPIcs.APPROX-RANDOM.2016.41,
  author =	{Mori, Ryuhei and Witmer, David},
  title =	{{Lower Bounds for CSP Refutation by SDP Hierarchies}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2016)},
  pages =	{41:1--41:30},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-018-7},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{60},
  editor =	{Jansen, Klaus and Mathieu, Claire and Rolim, Jos\'{e} D. P. and Umans, Chris},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2016.41},
  URN =		{urn:nbn:de:0030-drops-66645},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2016.41},
  annote =	{Keywords: constraint satisfaction problems, LP and SDP relaxations, average-case complexity}
}
  • Refine by Author
  • 2 Mori, Ryuhei
  • 1 Glos, Adam
  • 1 Kokainis, Martins
  • 1 Vihrovs, Jevgēnijs
  • 1 Witmer, David

  • Refine by Classification
  • 1 Theory of computation → Dynamic programming
  • 1 Theory of computation → Quantum query complexity

  • Refine by Keyword
  • 1 Dynamic programming
  • 1 LP and SDP relaxations
  • 1 Lattice graphs
  • 1 Quantum query complexity
  • 1 average-case complexity
  • Show More...

  • Refine by Type
  • 2 document

  • Refine by Publication Year
  • 1 2016
  • 1 2021

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
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact