András Gilyén

András Gilyén

Auto-generated profile, based on publicly available information

András Gilyén

QuSoft, CWI, Amsterdam, The Netherlands

Research Focus & Metrics

Academic Career Length

11Years (2016-Present)

(Calculated once Scilit publication data is synced: current year − year of first publication + 1)

Representative Publications

View All Publications
14 February 2020 in Quantum
Verified
Journal Article
Open access
PDF file
JAJoran van Apeldoorn
Joran van Apeldoorn
AGAndrás Gilyén
András Gilyén
SGSander Gribling
Sander Gribling
RWRonald de Wolf
Ronald de Wolf
Brandão and Svore \cite{brandao2016QSDPSpeedup} recently gave quantum algorithms for approximately solving semidefinite programs, which in some regimes are faster than the best-possible classical algorithms in terms of the dimension n of the problem and the number m of constraints, but worse in terms of various other parameters. In this paper we improve their algorithms in several ways, getting better dependence on those other parameters. To this end we develop new techniques for quantum algorithms, for instance a general way to efficiently implement smooth functions of sparse Hamiltonians, and a generalized minimum-finding procedure.We also show limits on this approach to quantum SDP-solvers, for instance for combinatorial optimization problems that have a lot of symmetry. Finally, we prove some general lower bounds showing that in the worst case, the complexity of every quantum LP-solver (and hence also SDP-solver) has to scale linearly with mn when m≈n, which is the same as classical.

13 January 2020 in Quantum
Verified
Journal Article
Open access
PDF file
JAJoran van Apeldoorn
Joran van Apeldoorn
AGAndrás Gilyén
András Gilyén
SGSander Gribling
Sander Gribling
RWRonald de Wolf
Ronald de Wolf
We study to what extent quantum algorithms can speed up solving convex optimization problems. Following the classical literature we assume access to a convex set via various oracles, and we examine the efficiency of reductions between the different oracles. In particular, we show how a separation oracle can be implemented using O~(1) quantum queries to a membership oracle, which is an exponential quantum speed-up over the Ω(n) membership queries that are needed classically. We show that a quantum computer can very efficiently compute an approximate subgradient of a convex Lipschitz function. Combining this with a simplification of recent classical work of Lee, Sidford, and Vempala gives our efficient separation oracle. This in turn implies, via a known algorithm, that O~(n) quantum queries to a membership oracle suffice to implement an optimization oracle (the best known classical upper bound on the number of membership queries is quadratic). We also prove several lower bounds: Ω(n) quantum separation (or membership) queries are needed for optimization if the algorithm knows an interior point of the convex set, and Ω(n) quantum separation queries are needed if it does not.

29 July 2019 in Journal of Statistical Physics
Verified
Journal Article
Open access
PDF file
TBTom Bannink
Tom Bannink
HBHarry Buhrman
Harry Buhrman
AGAndrás Gilyén
András Gilyén
MSMario Szegedy
Mario Szegedy
We consider a class of random processes on graphs that include the discrete Bak–Sneppen process and several versions of the contact process, with a focus on the former. These processes are parametrized by a probability \(0\le p \le 1\) that controls a local update rule, and often exhibit a phase transition in this parameter. In general, analyzing properties of the phase transition is challenging, even for one-dimensional chains. In this article we consider a power-series approach based on representing certain quantities, such as the survival probability or the expected number of steps per site to reach the steady state, as a power series in p. We prove that the coefficients of those power series stabilize for various families of graphs, including the family of chain graphs. This phenomenon has been used in the physics community but was not yet proven. We also show that for local events A, B of which the support is a distance d apart we have \({\mathrm {cor}}(A,B) = O(p^d)\). The stabilization allows for the (exact) computation of coefficients for arbitrary large systems which can then be analyzed using the wide range of existing methods of power series analysis.

3 September 2018 in arXiv
Verified
Preprint
Open access
PDF file
SCShantanav Chakraborty
Shantanav Chakraborty
AGAndrás Gilyén
András Gilyén
SJStacey Jeffery
Stacey Jeffery
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.

12 February 2020 in arXiv
Verified
Preprint
Open access
PDF file
JAJoran van Apeldoorn
Joran van Apeldoorn
AGAndrás Gilyén
András Gilyén
SGSander Gribling
Sander Gribling
RWRonald de Wolf
Ronald de Wolf
Brand\~ao and Svore very recently gave quantum algorithms for approximately solving semidefinite programs, which in some regimes are faster than the best-possible classical algorithms in terms of the dimension $n$ of the problem and the number $m$ of constraints, but worse in terms of various other parameters. In this paper we improve their algorithms in several ways, getting better dependence on those other parameters. To this end we develop new techniques for quantum algorithms, for instance a general way to efficiently implement smooth functions of sparse Hamiltonians, and a generalized minimum-finding procedure. We also show limits on this approach to quantum SDP-solvers, for instance for combinatorial optimizations problems that have a lot of symmetry. Finally, we prove some general lower bounds showing that in the worst case, the complexity of every quantum LP-solver (and hence also SDP-solver) has to scale linearly with $mn$ when $m\approx n$, which is the same as classical.

13 April 2018 in arXiv
Verified
Preprint
Open access
PDF file
JAJoran van Apeldoorn
Joran van Apeldoorn
AGAndrás Gilyén
András Gilyén
Following the first paper on quantum algorithms for SDP-solving by Brand\~ao and Svore in 2016, rapid developments has been made on quantum optimization algorithms. Recently Brand\~ao et al. improved the quantum SDP-solver in the so-called quantum state input model, where the input matrices of the SDP are given as purified mixed states. They also gave the first non-trivial application of quantum SDP-solving by obtaining a more efficient algorithm for the problem of shadow tomography (proposed by Aaronson in 2017). In this paper we improve on all previous quantum SDP-solvers. Mainly we construct better Gibbs-samplers for both input models, which directly gives better bounds for SDP-solving. For an SDP with $m$ constraints involving $n\times n$ matrices, our improvements yield an $\widetilde{\mathcal O}\left( \left( \sqrt{m} + \sqrt{n}\gamma \right)s \gamma^4\right)$ upper bound on SDP-solving in the sparse matrix input model and an $\widetilde{\mathcal O}\left( \left(\sqrt{m}+B^{2.5}\gamma^{3.5} \right)B\gamma^4 \right)$ upper bound in the quantum state input model. We then apply these results to the problem of shadow tomography to simultaneously improve the best known upper bounds on sample complexity due to Aaronson and complexity due Brandao et al. Furthermore, we apply our quantum SDP-solvers to the problems of quantum state discrimination and E-optimal design. In both cases we beat the classical lower bound in terms of some parameters, at the expense of heavy dependence on some other parameters. Finally we prove two lowers bounds for solving SDPs using quantum algorithms: (1) $\tilde{\Omega}(\sqrt{m}B/\eps)$ in the quantum state input model, and (2) $\tilde{\Omega}(\sqrt{m}\alpha/\eps)$ in the quantum operator input model. These lower bounds show that the $\sqrt{m}$ factor and the polynomial dependence on the parameters $B,\alpha$, and $1/\eps$ are necessary.