329 citations · 351 across the 2 of their papers we have counts for
Showing quant-phShow all
3 papers · 1 filter
quant-ph2004★ 329 cited
A new quantum ripple-carry addition circuit
Steven A. Cuccaro, Thomas G. Draper, Samuel A. Kutin +1
We present a new linear-depth ripple-carry quantum addition circuit. Previous addition circuits required linearly many ancillary qubits; our new adder uses only a single ancillary…
quant-ph2003★ 22 cited
A quantum lower bound for the collision problem
Samuel Kutin
We extend Shi's 2002 quantum lower bound for collision in -to-one functions with inputs. Shi's bound of is tight, but his proof applies only in the case whe…
quant-ph2001
On the Quantum Black-Box Complexity of Majority
Thomas Hayes, Samuel Kutin, Dieter van Melkebeek
We describe a quantum black-box network computing the majority of N bits with zero-sided error eps using only 2N/3 + O(sqrt{N (log log N + log 1/eps)}) queries: the algorithm retur…