1.2k citations · 2.5k across the 41 of their papers we have counts for
Showing 2012 · quant-phShow all
3 papers · 2 filters
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…
quant-ph2012
New bounds on the classical and quantum communication complexity of some graph properties
Gabor Ivanyos, Hartmut Klauck, Troy Lee +2
We study the communication complexity of a number of graph properties where the edges of the graph are distributed between Alice and Bob (i.e., each receives some of the edges…
quant-ph2012★ 7 cited
Fooling One-Sided Quantum Protocols
Hartmut Klauck, Ronald de Wolf
We use the venerable "fooling set" method to prove new lower bounds on the quantum communication complexity of various functions. Let f:X x Y-->{0,1} be a Boolean function, fool^1(…