A note on the depth of optimal fanout-bounded prefix circuits
By: Igor S. Sergeev
It is shown that the minimal depth of an optimal prefix circuit (i.e., a zero-deficiency circuit) on $N$ inputs with fanout bounded by $k$ is ${\log_{α_k} N \pm O(1)}$, where $α_k$ is the unique positive root of the polynomial ${2+x+ x^2+\ldots + x^{k-2}-x^k}$. This bound was previously known in the cases $k=2$ and $k=\infty$.
Similar Papers
Prefix Sums via Kronecker Products
Quantum Physics
Makes computers add numbers much faster.
Prefix Sums via Kronecker Products
Quantum Physics
Makes computers add numbers much faster.
Unitary designs in nearly optimal depth
Quantum Physics
Makes quantum computers more reliable and faster.