8 papers
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…
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…