142 citations · 287 across the 18 of their papers we have counts for
11 papers · 1 filter
Reconstructing Strings from Substrings with Quantum Queries
Richard Cleve, Kazuo Iwama, François Le Gall +4
This paper investigates the number of quantum queries made to solve the problem of reconstructing an unknown string from its substrings in a certain query model. More concretely, t…
Quantum Counterfeit Coin Problems
Kazuo Iwama, Harumichi Nishimura, Rudy Raymond +1
The counterfeit coin problem requires us to find all false coins from a given bunch of coins using a balance scale. We assume that the balance scale gives us only ``balanced'' or `…
Average/Worst-Case Gap of Quantum Query Complexities by On-Set Size
Andris Ambainis, Kazuo Iwama, Masaki Nakanishi +4
This paper considers the query complexity of the functions in the family F_{N,M} of N-variable Boolean functions with onset size M, i.e., the number of inputs for which the functio…
Unbounded-Error Classical and Quantum Communication Complexity
Kazuo Iwama, Harumichi Nishimura, Rudy Raymond +1
Since the seminal work of Paturi and Simon \cite[FOCS'84 & JCSS'86]{PS86}, the unbounded-error classical communication complexity of a Boolean function has been studied based on th…
Unbounded-error One-way Classical and Quantum Communication Complexity
Kazuo Iwama, Harumichi Nishimura, Rudy Raymond +1
This paper studies the gap between quantum one-way communication complexity and its classical counterpart , under the {\em unbounded-error} setting, i.e., it is enough…
Quantum Network Coding for General Graphs
Kazuo Iwama, Harumichi Nishimura, Rudy Raymond +1
Network coding is often explained by using a small network model called Butterfly. In this network, there are two flow paths, s_1 to t_1 and s_2 to t_2, which share a single bottle…