5 papers · 1 filter
Weak coin flipping with small bias
Iordanis Kerenidis, Ashwin Nayak
This note presents a quantum protocol that demonstrates that_weak_ coin flipping with bias approximately 0.239, less than 1/4, is possible. A bias of 1/4 was the smallest known, an…
Quantum Walk on the Line
Ashwin Nayak, Ashvin Vishwanath
Motivated by the immense success of random walk and Markov chain methods in the design of classical algorithms, we consider_quantum_ walks on graphs. We analyse in detail the behav…
Interaction in Quantum Communication Complexity
Ashwin Nayak, Amnon Ta-Shma, David Zuckerman
One of the most intriguing facts about communication using quantum states is that these states cannot be used to transmit more classical bits than the number of qubits used, yet th…
Optimal lower bounds for quantum automata and random access codes
Ashwin Nayak
Consider the finite regular language L_n = {w0 : w \in {0,1}^*, |w| \le n}. It was shown by Ambainis, Nayak, Ta-Shma and Vazirani that while this language is accepted by a determin…
The quantum query complexity of approximating the median and related statistics
Ashwin Nayak, Felix Wu
Let X = (x_0,...,x_{n-1})$ be a sequence of n numbers. For ε> 0, we say that x_i is an ε-approximate median if the number of elements strictly less than x_i, and the number of elem…