544 citations · 1.1k across the 11 of their papers we have counts for
14 papers
Tight bounds for hybrid quantum-classical query algorithms
Andris Ambainis, András Gilyén, Martins Kokainis
We study hybrid quantum-classical algorithms in the query model. The computation consists of quantum subroutines that make at most oracle queries; between subroutines, all qubi…
Finding Angles for Quantum Signal Processing with Machine Precision
Rui Chao, Dawei Ding, Andras Gilyen +2
We describe an algorithm for finding angle sequences in quantum signal processing, with a novel component we call halving based on a new algebraic uniqueness theorem, and another w…
Sampling-based sublinear low-rank matrix arithmetic framework for dequantizing quantum machine learning
Nai-Hui Chia, András Gilyén, Tongyang Li +3
We present an algorithmic framework for quantum-inspired classical algorithms on close-to-low-rank matrices, generalizing the series of results started by Tang's breakthrough quant…
Quadratic speedup for finding marked vertices by quantum walks
Andris Ambainis, András Gilyén, Stacey Jeffery +1
A quantum walk algorithm can detect the presence of a marked vertex on a graph quadratically faster than the corresponding random walk algorithm (Szegedy, FOCS 2004). However, quan…
Distributional property testing in a quantum world
András Gilyén, Tongyang Li
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. I…
Quantum-inspired low-rank stochastic regression with logarithmic dependence on the dimension
András Gilyén, Seth Lloyd, Ewin Tang
We construct an efficient classical analogue of the quantum matrix inversion algorithm (HHL) for low-rank matrices. Inspired by recent work of Tang, assuming length-square sampling…
Convex optimization using quantum oracles
Joran van Apeldoorn, András Gilyén, Sander Gribling +1
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 oracle…
Quantum singular value transformation and beyond: exponential improvements for quantum matrix arithmetics
András Gilyén, Yuan Su, Guang Hao Low +1
Quantum computing is powerful because unitary operators describing the time-evolution of a quantum system have exponential size in terms of the number of qubits present in the syst…
Improvements in Quantum SDP-Solving with Applications
Joran van Apeldoorn, András Gilyén
Following the first paper on quantum algorithms for SDP-solving by Brandão and Svore in 2016, rapid developments has been made on quantum optimization algorithms. Recently Brandão…
The power of block-encoded matrix powers: improved regression techniques via faster Hamiltonian simulation
Shantanav Chakraborty, András Gilyén, 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 resul…
Optimizing quantum optimization algorithms via faster quantum gradient computation
András Gilyén, Srinivasan Arunachalam, Nathan Wiebe
We consider a generic framework of optimization algorithms based on gradient descent. We develop a quantum algorithm that computes the gradient of a multi-variate real-valued funct…
Quantum SDP-Solvers: Better upper and lower bounds
Joran van Apeldoorn, András Gilyén, Sander Gribling +1
Brandão and Svore very recently gave quantum algorithms for approximately solving semidefinite programs, which in some regimes are faster than the best-possible classical algorithm…
On preparing ground states of gapped Hamiltonians: An efficient Quantum Lovász Local Lemma
András Gilyén, Or Sattath
A frustration-free local Hamiltonian has the property that its ground state minimises the energy of all local terms simultaneously. In general, even deciding whether a Hamiltonian…
Exponential Sensitivity and its Cost in Quantum Physics
András Gilyén, Tamás Kiss, Igor Jex
State selective protocols, like entanglement purification, lead to an essentially non-linear quantum evolution, unusual in naturally occurring quantum processes. Sensitivity to ini…