70 citations · 222 across the 11 of their papers we have counts for
13 papers
Quantum state preparation without coherent arithmetic
Sam McArdle, András Gilyén, Mario Berta
We introduce a versatile method for preparing a quantum state whose amplitudes are given by some known function. Unlike existing approaches, our method does not require handcrafted…
A streamlined quantum algorithm for topological data analysis with exponentially fewer qubits
Sam McArdle, András Gilyén, Mario Berta
Topological invariants of a dataset, such as the number of holes that survive from one length scale to another (persistent Betti numbers) can be used to analyze and classify data i…
Quantum tomography using state-preparation unitaries
Joran van Apeldoorn, Arjan Cornelissen, András Gilyén +1
We describe algorithms to obtain an approximate classical description of a -dimensional quantum state when given access to a unitary (and its inverse) that prepares it. For pure…
Improved Quantum Algorithms for Fidelity Estimation
András Gilyén, Alexander Poremba
Fidelity is a fundamental measure for the closeness of two quantum states, which is important both from a theoretical and a practical point of view. Yet, in general, it is difficul…
Limitations of the Macaulay matrix approach for using the HHL algorithm to solve multivariate polynomial systems
Jintai Ding, Vlad Gheorghiu, András Gilyén +2
Recently Chen and Gao~\cite{ChenGao2017} proposed a new quantum algorithm for Boolean polynomial system solving, motivated by the cryptanalysis of some post-quantum cryptosystems.…
Scalable Benchmarks for Gate-Based Quantum Computers
Arjan Cornelissen, Johannes Bausch, András Gilyén
In the near-term "NISQ"-era of noisy, intermediate-scale, quantum hardware and beyond, reliably determining the quality of quantum devices becomes increasingly important: users nee…
(Sub)Exponential advantage of adiabatic quantum computation with no sign problem
András Gilyén, Umesh Vazirani
We demonstrate the possibility of (sub)exponential quantum speedup via a quantum algorithm that follows an adiabatic path of a gapped Hamiltonian with no sign problem. This strengt…
An improved quantum-inspired algorithm for linear regression
András Gilyén, Zhao Song, Ewin Tang
We give a classical algorithm for linear regression analogous to the quantum matrix inversion algorithm [Harrow, Hassidim, and Lloyd, Physical Review Letters'09, arXiv:0811.3171] f…
Symmetries, graph properties, and quantum speedups
Shalev Ben-David, Andrew M. Childs, András Gilyén +3
Aaronson and Ambainis (2009) and Chailloux (2018) showed that fully symmetric (partial) functions do not admit exponential quantum query speedups. This raises a natural question: h…
Quantum algorithm for Petz recovery channels and pretty good measurements
András Gilyén, Seth Lloyd, Iman Marvian +2
The Petz recovery channel plays an important role in quantum information science as an operation that approximately reverses the effect of a quantum channel. The pretty good measur…
A Unified Framework of Quantum Walk Search
Simon Apers, András Gilyén, Stacey Jeffery
The main results on quantum walk search are scattered over different, incomparable frameworks, most notably the hitting time framework, originally by Szegedy, the electric network…
Quantum algorithms for zero-sum games
Joran van Apeldoorn, András Gilyén
We derive sublinear-time quantum algorithms for computing the Nash equilibrium of two-player zero-sum games, based on efficient Gibbs sampling methods. We are able to achieve speed…
The Power Light Cone of the Discrete Bak-Sneppen, Contact and other local processes
Tom Bannink, Harry Buhrman, András Gilyén +1
We consider a class of random processes on graphs that include the discrete Bak-Sneppen (DBS) process and the several versions of the contact process (CP), with a focus on the form…