8 Search Results for "Gilyén, András"


Document
Quantum Probability Oracles & Multidimensional Amplitude Estimation

Authors: Joran van Apeldoorn

Published in: LIPIcs, Volume 197, 16th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2021)


Abstract
We give a multidimensional version of amplitude estimation. Let p be an n-dimensional probability distribution which can be sampled from using a quantum circuit U_p. We show that all coordinates of p can be estimated up to error ε per coordinate using Õ(1/(ε)) applications of U_p and its inverse. This generalizes the normal amplitude estimation algorithm, which solves the problem for n = 2. Our results also imply a Õ(n/ε) query algorithm for 𝓁₁-norm (the total variation distance) estimation and a Õ(√n/ε) query algorithm for 𝓁₂-norm. We also show that these results are optimal up to logarithmic factors.

Cite as

Joran van Apeldoorn. Quantum Probability Oracles & Multidimensional Amplitude Estimation. In 16th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 197, pp. 9:1-9:11, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)


Copy BibTex To Clipboard

@InProceedings{vanapeldoorn:LIPIcs.TQC.2021.9,
  author =	{van Apeldoorn, Joran},
  title =	{{Quantum Probability Oracles \& Multidimensional Amplitude Estimation}},
  booktitle =	{16th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2021)},
  pages =	{9:1--9:11},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-198-6},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{197},
  editor =	{Hsieh, Min-Hsiu},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.TQC.2021.9},
  URN =		{urn:nbn:de:0030-drops-140046},
  doi =		{10.4230/LIPIcs.TQC.2021.9},
  annote =	{Keywords: quantum algorithms, amplitude estimation, monte carlo}
}
Document
A Unified Framework of Quantum Walk Search

Authors: Simon Apers, András Gilyén, and Stacey Jeffery

Published in: LIPIcs, Volume 187, 38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021)


Abstract
Many quantum algorithms critically rely on quantum walk search, or the use of quantum walks to speed up search problems on graphs. However, the main results on quantum walk search are scattered over different, incomparable frameworks, such as the hitting time framework, the MNRS framework, and the electric network framework. As a consequence, a number of pieces are currently missing. For example, recent work by Ambainis et al. (STOC'20) shows how quantum walks starting from the stationary distribution can always find elements quadratically faster. In contrast, the electric network framework allows quantum walks to start from an arbitrary initial state, but it only detects marked elements. We present a new quantum walk search framework that unifies and strengthens these frameworks, leading to a number of new results. For example, the new framework effectively finds marked elements in the electric network setting. The new framework also allows to interpolate between the hitting time framework, minimizing the number of walk steps, and the MNRS framework, minimizing the number of times elements are checked for being marked. This allows for a more natural tradeoff between resources. In addition to quantum walks and phase estimation, our new algorithm makes use of quantum fast-forwarding, similar to the recent results by Ambainis et al. This perspective also enables us to derive more general complexity bounds on the quantum walk algorithms, e.g., based on Monte Carlo type bounds of the corresponding classical walk. As a final result, we show how in certain cases we can avoid the use of phase estimation and quantum fast-forwarding, answering an open question of Ambainis et al.

Cite as

Simon Apers, András Gilyén, and Stacey Jeffery. A Unified Framework of Quantum Walk Search. In 38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 187, pp. 6:1-6:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)


Copy BibTex To Clipboard

@InProceedings{apers_et_al:LIPIcs.STACS.2021.6,
  author =	{Apers, Simon and Gily\'{e}n, Andr\'{a}s and Jeffery, Stacey},
  title =	{{A Unified Framework of Quantum Walk Search}},
  booktitle =	{38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021)},
  pages =	{6:1--6:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-180-1},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{187},
  editor =	{Bl\"{a}ser, Markus and Monmege, Benjamin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2021.6},
  URN =		{urn:nbn:de:0030-drops-136511},
  doi =		{10.4230/LIPIcs.STACS.2021.6},
  annote =	{Keywords: Quantum Algorithms, Quantum Walks, Graph Theory}
}
Document
No Quantum Speedup over Gradient Descent for Non-Smooth Convex Optimization

Authors: Ankit Garg, Robin Kothari, Praneeth Netrapalli, and Suhail Sherif

Published in: LIPIcs, Volume 185, 12th Innovations in Theoretical Computer Science Conference (ITCS 2021)


Abstract
We study the first-order convex optimization problem, where we have black-box access to a (not necessarily smooth) function f:ℝⁿ → ℝ and its (sub)gradient. Our goal is to find an ε-approximate minimum of f starting from a point that is distance at most R from the true minimum. If f is G-Lipschitz, then the classic gradient descent algorithm solves this problem with O((GR/ε)²) queries. Importantly, the number of queries is independent of the dimension n and gradient descent is optimal in this regard: No deterministic or randomized algorithm can achieve better complexity that is still independent of the dimension n. In this paper we reprove the randomized lower bound of Ω((GR/ε)²) using a simpler argument than previous lower bounds. We then show that although the function family used in the lower bound is hard for randomized algorithms, it can be solved using O(GR/ε) quantum queries. We then show an improved lower bound against quantum algorithms using a different set of instances and establish our main result that in general even quantum algorithms need Ω((GR/ε)²) queries to solve the problem. Hence there is no quantum speedup over gradient descent for black-box first-order convex optimization without further assumptions on the function family.

Cite as

Ankit Garg, Robin Kothari, Praneeth Netrapalli, and Suhail Sherif. No Quantum Speedup over Gradient Descent for Non-Smooth Convex Optimization. In 12th Innovations in Theoretical Computer Science Conference (ITCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 185, pp. 53:1-53:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)


Copy BibTex To Clipboard

@InProceedings{garg_et_al:LIPIcs.ITCS.2021.53,
  author =	{Garg, Ankit and Kothari, Robin and Netrapalli, Praneeth and Sherif, Suhail},
  title =	{{No Quantum Speedup over Gradient Descent for Non-Smooth Convex Optimization}},
  booktitle =	{12th Innovations in Theoretical Computer Science Conference (ITCS 2021)},
  pages =	{53:1--53:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-177-1},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{185},
  editor =	{Lee, James R.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2021.53},
  URN =		{urn:nbn:de:0030-drops-135921},
  doi =		{10.4230/LIPIcs.ITCS.2021.53},
  annote =	{Keywords: Quantum algorithms, Gradient descent, Convex optimization}
}
Document
Quantum-Inspired Algorithms for Solving Low-Rank Linear Equation Systems with Logarithmic Dependence on the Dimension

Authors: Nai-Hui Chia, András Gilyén, Han-Hsuan Lin, Seth Lloyd, Ewin Tang, and Chunhao Wang

Published in: LIPIcs, Volume 181, 31st International Symposium on Algorithms and Computation (ISAAC 2020)


Abstract
We present two efficient classical analogues of the quantum matrix inversion algorithm [Harrow et al., 2009] for low-rank matrices. Inspired by recent work of Tang [Tang, 2019], assuming length-square sampling access to input data, we implement the pseudoinverse of a low-rank matrix allowing us to sample from the solution to the problem Ax = b using fast sampling techniques. We construct implicit descriptions of the pseudo-inverse by finding approximate singular value decomposition of A via subsampling, then inverting the singular values. In principle, our approaches can also be used to apply any desired "smooth" function to the singular values. Since many quantum algorithms can be expressed as a singular value transformation problem [András Gilyén et al., 2019], our results indicate that more low-rank quantum algorithms can be effectively "dequantised" into classical length-square sampling algorithms.

Cite as

Nai-Hui Chia, András Gilyén, Han-Hsuan Lin, Seth Lloyd, Ewin Tang, and Chunhao Wang. Quantum-Inspired Algorithms for Solving Low-Rank Linear Equation Systems with Logarithmic Dependence on the Dimension. In 31st International Symposium on Algorithms and Computation (ISAAC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 181, pp. 47:1-47:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)


Copy BibTex To Clipboard

@InProceedings{chia_et_al:LIPIcs.ISAAC.2020.47,
  author =	{Chia, Nai-Hui and Gily\'{e}n, Andr\'{a}s and Lin, Han-Hsuan and Lloyd, Seth and Tang, Ewin and Wang, Chunhao},
  title =	{{Quantum-Inspired Algorithms for Solving Low-Rank Linear Equation Systems with Logarithmic Dependence on the Dimension}},
  booktitle =	{31st International Symposium on Algorithms and Computation (ISAAC 2020)},
  pages =	{47:1--47:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-173-3},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{181},
  editor =	{Cao, Yixin and Cheng, Siu-Wing and Li, Minming},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2020.47},
  URN =		{urn:nbn:de:0030-drops-133916},
  doi =		{10.4230/LIPIcs.ISAAC.2020.47},
  annote =	{Keywords: sublinear algorithms, quantum-inspired, regression, importance sampling, quantum machine learning}
}
Document
Quantum-Inspired Classical Algorithms for Singular Value Transformation

Authors: Dhawal Jethwani, François Le Gall, and Sanjay K. Singh

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


Abstract
A recent breakthrough by Tang (STOC 2019) showed how to "dequantize" the quantum algorithm for recommendation systems by Kerenidis and Prakash (ITCS 2017). The resulting algorithm, classical but "quantum-inspired", efficiently computes a low-rank approximation of the users' preference matrix. Subsequent works have shown how to construct efficient quantum-inspired algorithms for approximating the pseudo-inverse of a low-rank matrix as well, which can be used to (approximately) solve low-rank linear systems of equations. In the present paper, we pursue this line of research and develop quantum-inspired algorithms for a large class of matrix transformations that are defined via the singular value decomposition of the matrix. In particular, we obtain classical algorithms with complexity polynomially related (in most parameters) to the complexity of the best quantum algorithms for singular value transformation recently developed by Chakraborty, Gilyén and Jeffery (ICALP 2019) and Gilyén, Su, Low and Wiebe (STOC 2019).

Cite as

Dhawal Jethwani, François Le Gall, and Sanjay K. Singh. Quantum-Inspired Classical Algorithms for Singular Value Transformation. In 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 170, pp. 53:1-53:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)


Copy BibTex To Clipboard

@InProceedings{jethwani_et_al:LIPIcs.MFCS.2020.53,
  author =	{Jethwani, Dhawal and Le Gall, Fran\c{c}ois and Singh, Sanjay K.},
  title =	{{Quantum-Inspired Classical Algorithms for Singular Value Transformation}},
  booktitle =	{45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020)},
  pages =	{53:1--53: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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2020.53},
  URN =		{urn:nbn:de:0030-drops-127193},
  doi =		{10.4230/LIPIcs.MFCS.2020.53},
  annote =	{Keywords: Sampling algorithms, quantum-inspired algorithms, linear algebra}
}
Document
Distributional Property Testing in a Quantum World

Authors: András Gilyén and Tongyang Li

Published in: LIPIcs, Volume 151, 11th Innovations in Theoretical Computer Science Conference (ITCS 2020)


Abstract
A fundamental problem in statistics and learning theory is to test properties of distributions. We show that quantum computers can solve such problems with significant speed-ups. We also introduce a novel access model for quantum distributions, enabling the coherent preparation of quantum samples, and propose a general framework that can naturally handle both classical and quantum distributions in a unified manner. Our framework generalizes and improves previous quantum algorithms for testing closeness between unknown distributions, testing independence between two distributions, and estimating the Shannon / von Neumann entropy of distributions. For classical distributions our algorithms significantly improve the precision dependence of some earlier results. We also show that in our framework procedures for classical distributions can be directly lifted to the more general case of quantum distributions, and thus obtain the first speed-ups for testing properties of density operators that can be accessed coherently rather than only via sampling.

Cite as

András Gilyén and Tongyang Li. Distributional Property Testing in a Quantum World. In 11th Innovations in Theoretical Computer Science Conference (ITCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 151, pp. 25:1-25:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)


Copy BibTex To Clipboard

@InProceedings{gilyen_et_al:LIPIcs.ITCS.2020.25,
  author =	{Gily\'{e}n, Andr\'{a}s and Li, Tongyang},
  title =	{{Distributional Property Testing in a Quantum World}},
  booktitle =	{11th Innovations in Theoretical Computer Science Conference (ITCS 2020)},
  pages =	{25:1--25:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-134-4},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{151},
  editor =	{Vidick, Thomas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2020.25},
  URN =		{urn:nbn:de:0030-drops-117100},
  doi =		{10.4230/LIPIcs.ITCS.2020.25},
  annote =	{Keywords: distributional property testing, quantum algorithms, quantum query complexity}
}
Document
Track A: Algorithms, Complexity and Games
The Power of Block-Encoded Matrix Powers: Improved Regression Techniques via Faster Hamiltonian Simulation

Authors: Shantanav Chakraborty, András Gilyén, and Stacey Jeffery

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


Abstract
We apply the framework of block-encodings, introduced by Low and Chuang (under the name standard-form), to the study of quantum machine learning algorithms and derive general results that are applicable to a variety of input models, including sparse matrix oracles and matrices stored in a data structure. We develop several tools within the block-encoding framework, such as singular value estimation of a block-encoded matrix, and quantum linear system solvers using block-encodings. The presented results give new techniques for Hamiltonian simulation of non-sparse matrices, which could be relevant for certain quantum chemistry applications, and which in turn imply an exponential improvement in the dependence on precision in quantum linear systems solvers for non-sparse matrices. In addition, we develop a technique of variable-time amplitude estimation, based on Ambainis' variable-time amplitude amplification technique, which we are also able to apply within the framework. As applications, we design the following algorithms: (1) a quantum algorithm for the quantum weighted least squares problem, exhibiting a 6-th power improvement in the dependence on the condition number and an exponential improvement in the dependence on the precision over the previous best algorithm of Kerenidis and Prakash; (2) the first quantum algorithm for the quantum generalized least squares problem; and (3) quantum algorithms for estimating electrical-network quantities, including effective resistance and dissipated power, improving upon previous work.

Cite as

Shantanav Chakraborty, András Gilyén, and Stacey Jeffery. The Power of Block-Encoded Matrix Powers: Improved Regression Techniques via Faster Hamiltonian Simulation. In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 132, pp. 33:1-33:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)


Copy BibTex To Clipboard

@InProceedings{chakraborty_et_al:LIPIcs.ICALP.2019.33,
  author =	{Chakraborty, Shantanav and Gily\'{e}n, Andr\'{a}s and Jeffery, Stacey},
  title =	{{The Power of Block-Encoded Matrix Powers: Improved Regression Techniques via Faster Hamiltonian Simulation}},
  booktitle =	{46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)},
  pages =	{33:1--33: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.33},
  URN =		{urn:nbn:de:0030-drops-106092},
  doi =		{10.4230/LIPIcs.ICALP.2019.33},
  annote =	{Keywords: Quantum algorithms, Hamiltonian simulation, Quantum machine learning}
}
Document
Track A: Algorithms, Complexity and Games
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}
}
  • Refine by Author
  • 5 Gilyén, András
  • 2 Jeffery, Stacey
  • 2 van Apeldoorn, Joran
  • 1 Apers, Simon
  • 1 Chakraborty, Shantanav
  • Show More...

  • Refine by Classification
  • 4 Theory of computation → Quantum computation theory
  • 2 Theory of computation → Design and analysis of algorithms
  • 1 Mathematics of computing → Distribution functions
  • 1 Theory of computation → Algorithm design techniques
  • 1 Theory of computation → Convex optimization
  • Show More...

  • Refine by Keyword
  • 3 quantum algorithms
  • 2 Quantum algorithms
  • 1 Convex optimization
  • 1 Gradient descent
  • 1 Graph Theory
  • Show More...

  • Refine by Type
  • 8 document

  • Refine by Publication Year
  • 3 2020
  • 3 2021
  • 2 2019

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