31 citations · 199 across the 33 of their papers we have counts for
Showing 2013Show all
3 papers · 1 filter
quant-ph2013★ 3 cited
Quantum Algorithms for Learning Symmetric Juntas via the Adversary Bound
Aleksandrs Belovs
In this paper, we study the following variant of the junta learning problem. We are given oracle access to a Boolean function on variables that only depends on variable…
quant-ph2013
Adversary Lower Bounds for the Collision and the Set Equality Problems
Aleksandrs Belovs, Ansis Rosmanis
We prove tight lower bounds on the quantum query complexity of the Collision and the Set Equality problems, provided that the size of the alphabet is large enough. We…
quant-ph2013★ 25 cited
Quantum Walks and Electric Networks
Aleksandrs Belovs
We prove that a quantum walk can detect the presence of a marked element in a graph in steps for any initial probability distribution on vertices. Here, is the t…