One oracle query can require many ordinary gates

The parity oracle is exactly one application of the supplied $O_{f_m}$, so its query count is one by [F1]. In an ordinary circuit, form the interaction graph whose vertices are all circuit wires and whose edges join the two wires acted on by each two-wire gate occurrence. If the target's connected component omitted an address bit, then no gate couples that bit to the target or to any intermediary on its component; the circuit factors across this separation, making the target output independent of the omitted bit. This contradicts parity's dependence on each input bit: fixing the other bits and changing the omitted bit changes the target. Hence the graph contains a connected subgraph joining the target and all $m$ address wires. Any connected graph containing these $m+1$ distinct terminals has at least $m$ edges, even if it also contains ancilla vertices; each edge comes from a gate occurrence.

For the explicit upper-bound constructions, choose an ordinary gate alphabet containing CNOT, with basis action $\mathrm{\mid }a,b⟩\mapsto \mathrm{\mid }a,b\oplus a⟩$; this is an additional model choice, not a consequence of [F2]. Applying the $m$ CNOT gates from each address bit to the target computes parity into that target and gives an exact $m$-gate implementation. In QRAM, store $z_i=f_m(i)$ and use one addressed swap to move $z_i$ to a clean scratch bit, copy it by CNOT into the oracle target, and use a second addressed swap to restore the memory and clear the scratch. This is a constant number of RAM calls by [F3], but it still requires the table to have been constructed and maintained. The online gate models therefore count one oracle call versus at least $m$ ordinary two-wire gates for this function, with RAM construction cost recorded separately.