194 citations · 1.9k across the 115 of their papers we have counts for
Showing 2012 · quant-phShow all
3 papers · 2 filters
quant-ph2012★ 2 cited
Superlinear advantage for exact quantum algorithms
Andris Ambainis
A quantum algorithm is exact if, on any input data, it outputs the correct answer with certainty (probability 1). A key question is: how big is the advantage of exact quantum algor…
quant-ph2012★ 1 cited
Quantum algorithms for search with wildcards and combinatorial group testing
Andris Ambainis, Ashley Montanaro
We consider two combinatorial problems. The first we call "search with wildcards": given an unknown n-bit string x, and the ability to check whether any subset of the bits of x is…
quant-ph2012
How Low Can Approximate Degree and Quantum Query Complexity be for Total Boolean Functions?
Andris Ambainis, Ronald de Wolf
It has long been known that any Boolean function that depends on n input variables has both degree and exact quantum query complexity of Omega(log n), and that this bound is achiev…