194 citations · 1.9k across the 115 of their papers we have counts for
5 papers · 1 filter
Symmetry-assisted adversaries for quantum state generation
Andris Ambainis, Loïck Magnin, Martin Roetteler +1
We introduce a new quantum adversary method to prove lower bounds on the query complexity of the quantum state generation problem. This problem encompasses both, the computation of…
Quantum property testing for bounded-degree graphs
Andris Ambainis, Andrew M. Childs, Yi-Kai Liu
We study quantum algorithms for testing bipartiteness and expansion of bounded-degree graphs. We give quantum algorithms that solve these problems in time O(N^(1/3)), beating the O…
Variable time amplitude amplification and a faster quantum algorithm for solving systems of linear equations
Andris Ambainis
We present two new quantum algorithms. Our first algorithm is a generalization of amplitude amplification to the case when parts of the quantum algorithm that is being amplified st…
New Developments in Quantum Algorithms
Andris Ambainis
In this survey, we describe two recent developments in quantum algorithms. The first new development is a quantum algorithm for evaluating a Boolean formula consisting of AND and O…
Quantum algorithms for formula evaluation
Andris Ambainis
We survey the recent sequence of algorithms for evaluating Boolean formulas consisting of NAND gates.