3 Search Results for "Brand�o, Fernando G. S. L."

Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2019.27
Quantum SDP Solvers: Large Speed-Ups, Optimality, and Applications to Quantum Learning

Authors: Fernando G. S. L. Brandão, Amir Kalev, Tongyang Li, Cedric Yen-Yu Lin, Krysta M. Svore, and Xiaodi Wu

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

Abstract
We give two new quantum algorithms for solving semidefinite programs (SDPs) providing quantum speed-ups. We consider SDP instances with m constraint matrices, each of dimension n, rank at most r, and sparsity s. The first algorithm assumes an input model where one is given access to an oracle to the entries of the matrices at unit cost. We show that it has run time O~(s^2 (sqrt{m} epsilon^{-10} + sqrt{n} epsilon^{-12})), with epsilon the error of the solution. This gives an optimal dependence in terms of m, n and quadratic improvement over previous quantum algorithms (when m ~~ n). The second algorithm assumes a fully quantum input model in which the input matrices are given as quantum states. We show that its run time is O~(sqrt{m}+poly(r))*poly(log m,log n,B,epsilon^{-1}), with B an upper bound on the trace-norm of all input matrices. In particular the complexity depends only polylogarithmically in n and polynomially in r. We apply the second SDP solver to learn a good description of a quantum state with respect to a set of measurements: Given m measurements and a supply of copies of an unknown state rho with rank at most r, we show we can find in time sqrt{m}*poly(log m,log n,r,epsilon^{-1}) a description of the state as a quantum circuit preparing a density matrix which has the same expectation values as rho on the m measurements, up to error epsilon. The density matrix obtained is an approximation to the maximum entropy state consistent with the measurement data considered in Jaynes' principle from statistical mechanics. As in previous work, we obtain our algorithm by "quantizing" classical SDP solvers based on the matrix multiplicative weight update method. One of our main technical contributions is a quantum Gibbs state sampler for low-rank Hamiltonians, given quantum states encoding these Hamiltonians, with a poly-logarithmic dependence on its dimension, which is based on ideas developed in quantum principal component analysis. We also develop a "fast" quantum OR lemma with a quadratic improvement in gate complexity over the construction of Harrow et al. [Harrow et al., 2017]. We believe both techniques might be of independent interest.
Cite as

Fernando G. S. L. Brandão, Amir Kalev, Tongyang Li, Cedric Yen-Yu Lin, Krysta M. Svore, and Xiaodi Wu. Quantum SDP Solvers: Large Speed-Ups, Optimality, and Applications to Quantum Learning. In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 132, pp. 27:1-27:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{brandao_et_al:LIPIcs.ICALP.2019.27,
  author =	{Brand\~{a}o, Fernando G. S. L. and Kalev, Amir and Li, Tongyang and Lin, Cedric Yen-Yu and Svore, Krysta M. and Wu, Xiaodi},
  title =	{{Quantum SDP Solvers: Large Speed-Ups, Optimality, and Applications to Quantum Learning}},
  booktitle =	{46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)},
  pages =	{27:1--27:14},
  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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2019.27},
  URN =		{urn:nbn:de:0030-drops-106036},
  doi =		{10.4230/LIPIcs.ICALP.2019.27},
  annote =	{Keywords: quantum algorithms, semidefinite program, convex optimization}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2019.99
Improvements in Quantum SDP-Solving with Applications

Authors: Joran van Apeldoorn and András Gilyén

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

Abstract
Following the first paper on quantum algorithms for SDP-solving by Brandão and Svore [Brandão and Svore, 2017] in 2016, rapid developments have been made on quantum optimization algorithms. In this paper we improve and generalize all prior quantum algorithms for SDP-solving and give a simpler and unified framework. We take a new perspective on quantum SDP-solvers and introduce several new techniques. One of these is the quantum operator input model, which generalizes the different input models used in previous work, and essentially any other reasonable input model. This new model assumes that the input matrices are embedded in a block of a unitary operator. In this model we give a O~((sqrt{m}+sqrt{n}gamma)alpha gamma^4) algorithm, where n is the size of the matrices, m is the number of constraints, gamma is the reciprocal of the scale-invariant relative precision parameter, and alpha is a normalization factor of the input matrices. In particular for the standard sparse-matrix access, the above result gives a quantum algorithm where alpha=s. We also improve on recent results of Brandão et al. [Fernando G. S. L. Brandão et al., 2018], who consider the special case when the input matrices are proportional to mixed quantum states that one can query. For this model Brandão et al. [Fernando G. S. L. Brandão et al., 2018] showed that the dependence on n can be replaced by a polynomial dependence on both the rank and the trace of the input matrices. We remove the dependence on the rank and hence require only a dependence on the trace of the input matrices. After we obtain these results we apply them to a few different problems. The most notable of which is the problem of shadow tomography, recently introduced by Aaronson [Aaronson, 2018]. Here we simultaneously improve both the sample and computational complexity of the previous best results. Finally we prove a new Omega~(sqrt{m}alpha gamma) lower bound for solving LPs and SDPs in the quantum operator model, which also implies a lower bound for the model of Brandão et al. [Fernando G. S. L. Brandão et al., 2018].
Cite as

Joran van Apeldoorn and András Gilyén. Improvements in Quantum SDP-Solving with Applications. In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 132, pp. 99:1-99:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{vanapeldoorn_et_al:LIPIcs.ICALP.2019.99,
  author =	{van Apeldoorn, Joran and Gily\'{e}n, Andr\'{a}s},
  title =	{{Improvements in Quantum SDP-Solving with Applications}},
  booktitle =	{46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)},
  pages =	{99:1--99:15},
  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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2019.99},
  URN =		{urn:nbn:de:0030-drops-106750},
  doi =		{10.4230/LIPIcs.ICALP.2019.99},
  annote =	{Keywords: quantum algorithms, semidefinite programming, shadow tomography}
}
Document
DOI: 10.4230/LIPIcs.STACS.2016.31
Kernelization and Sparseness: the Case of Dominating Set

Authors: Pål Grønås Drange, Markus Dregi, Fedor V. Fomin, Stephan Kreutzer, Daniel Lokshtanov, Marcin Pilipczuk, Michal Pilipczuk, Felix Reidl, Fernando Sánchez Villaamil, Saket Saurabh, Sebastian Siebertz, and Somnath Sikdar

Published in: LIPIcs, Volume 47, 33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016)

Abstract
We prove that for every positive integer r and for every graph class G of bounded expansion, the r-DOMINATING SET problem admits a linear kernel on graphs from G. Moreover, in the more general case when G is only assumed to be nowhere dense, we give an almost linear kernel on G for the classic DOMINATING SET problem, i.e., for the case r=1. These results generalize a line of previous research on finding linear kernels for DOMINATING SET and r-DOMINATING SET (Alber et al., JACM 2004, Bodlaender et al., FOCS 2009, Fomin et al., SODA 2010, Fomin et al., SODA 2012, Fomin et al., STACS 2013). However, the approach taken in this work, which is based on the theory of sparse graphs, is radically different and conceptually much simpler than the previous approaches. We complement our findings by showing that for the closely related CONNECTED DOMINATING SET problem, the existence of such kernelization algorithms is unlikely, even though the problem is known to admit a linear kernel on H-topological-minor-free graphs (Fomin et al., STACS 2013). Also, we prove that for any somewhere dense class G, there is some r for which r-DOMINATING SET is W[2]-hard on G. Thus, our results fall short of proving a sharp dichotomy for the parameterized complexity of r-DOMINATING SET on subgraph-monotone graph classes: we conjecture that the border of tractability lies exactly between nowhere dense and somewhere dense graph classes.
Cite as

Pål Grønås Drange, Markus Dregi, Fedor V. Fomin, Stephan Kreutzer, Daniel Lokshtanov, Marcin Pilipczuk, Michal Pilipczuk, Felix Reidl, Fernando Sánchez Villaamil, Saket Saurabh, Sebastian Siebertz, and Somnath Sikdar. Kernelization and Sparseness: the Case of Dominating Set. In 33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 47, pp. 31:1-31:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{drange_et_al:LIPIcs.STACS.2016.31,
  author =	{Drange, P\r{a}l Gr{\o}n\r{a}s and Dregi, Markus and Fomin, Fedor V. and Kreutzer, Stephan and Lokshtanov, Daniel and Pilipczuk, Marcin and Pilipczuk, Michal and Reidl, Felix and S\'{a}nchez Villaamil, Fernando and Saurabh, Saket and Siebertz, Sebastian and Sikdar, Somnath},
  title =	{{Kernelization and Sparseness: the Case of Dominating Set}},
  booktitle =	{33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016)},
  pages =	{31:1--31:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-001-9},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{47},
  editor =	{Ollinger, Nicolas and Vollmer, Heribert},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2016.31},
  URN =		{urn:nbn:de:0030-drops-57327},
  doi =		{10.4230/LIPIcs.STACS.2016.31},
  annote =	{Keywords: kernelization, dominating set, bounded expansion, nowhere dense}
}
  • Refine by Author
  • 1 Brandão, Fernando G. S. L.
  • 1 Drange, Pål Grønås
  • 1 Dregi, Markus
  • 1 Fomin, Fedor V.
  • 1 Gilyén, András
  • Show More...

  • Refine by Classification
  • 1 Theory of computation → Convex optimization
  • 1 Theory of computation → Quantum computation theory
  • 1 Theory of computation → Quantum query complexity
  • 1 Theory of computation → Semidefinite programming

  • Refine by Keyword
  • 2 quantum algorithms
  • 1 bounded expansion
  • 1 convex optimization
  • 1 dominating set
  • 1 kernelization
  • Show More...

  • Refine by Type
  • 3 document

  • Refine by Publication Year
  • 2 2019
  • 1 2016

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