69 citations · 261 across the 33 of their papers we have counts for
3 papers · 2 filters
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…