The quantum query complexity of evaluating any read-once formula with n

black-box input bits is Theta(sqrt(n)). However, the corresponding problem for

read-many formulas (i.e., formulas in which the inputs have fanout) is not well

understood. Although the optimal read-once formula evaluation algorithm can be

applied to any formula, it can be suboptimal if the inputs have large fanout.

We give an algorithm for evaluating any formula with n inputs, size S, and G

gates using O(min{n, sqrt{S}, n^{1/2} G^{1/4}}) quantum queries. Furthermore,

we show that this algorithm is optimal, since for any n,S,G there exists a

formula with n inputs, size at most S, and at most G gates that requires

Omega(min{n, sqrt{S}, n^{1/2} G^{1/4}}) queries. We also show that the

algorithm remains nearly optimal for circuits of any particular depth k >= 3,

and we give a linear-size circuit of depth 2 that requires Omega (n^{5/9})

queries. Applications of these results include a Omega (n^{19/18}) lower bound

for Boolean matrix product verification, a nearly tight characterization of the

quantum query complexity of evaluating constant-depth circuits with bounded

fanout, new formula gate count lower bounds for several functions including

PARITY, and a construction of an AC^0 circuit of linear size that can only be

evaluated by a formula with Omega(n^{2-epsilon}) gates.