1.1k citations · 4.7k across the 73 of their papers we have counts for
Showing 2009Show all
3 papers · 1 filter
cs.CC2009
On the communication complexity of XOR functions
Ashley Montanaro, Tobias Osborne
An XOR function is a function of the form g(x,y) = f(x + y), for some boolean function f on n bits. We study the quantum and classical communication complexity of XOR functions. In…
quant-ph2009★ 2 cited
Quantum search with advice
Ashley Montanaro
We consider the problem of search of an unstructured list for a marked element, when one is given advice as to where this element might be located, in the form of a probability dis…
quant-ph2009★ 3 cited
Symmetric functions of qubits in an unknown basis
Ashley Montanaro
Consider an n qubit computational basis state corresponding to a bit string x, which has had an unknown local unitary applied to each qubit, and whose qubits have been reordered by…