69 citations · 261 across the 33 of their papers we have counts for
4 papers · 1 filter
Quantum Addition Circuits and Unbounded Fan-Out
Yasuhiro Takahashi, Seiichiro Tani, Noboru Kunihiro
We first show how to construct an O(n)-depth O(n)-size quantum circuit for addition of two n-bit binary numbers with no ancillary qubits. The exact size is 7n-6, which is smaller t…
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…
The quantum query complexity of certification
Andris Ambainis, Andrew M. Childs, François Le Gall +1
We study the quantum query complexity of finding a certificate for a d-regular, k-level balanced NAND formula. Up to logarithmic factors, we show that the query complexity is Theta…
The One-Way Communication Complexity of Group Membership
Scott Aaronson, François Le Gall, Alexander Russell +1
This paper studies the one-way communication complexity of the subgroup membership problem, a classical problem closely related to basic questions in quantum computing. Here Alice…