  Research on indefinite causal structures is a rapidly evolving field that has
a potential not only to make a radical revision of the classical understanding
of space-time but also to achieve enhanced functionalities of quantum
information processing. For example, it is known that indefinite causal
structures provide exponential advantage in communication complexity when
compared to causal protocols. In quantum computation, such structures can
decide whether two unitary gates commute or anticommute with a single call to
each gate, which is impossible with conventional (causal) quantum algorithms. A
generalization of this effect to $n$ unitary gates, originally introduced in M.
Ara\'ujo et al., Phys. Rev. Lett. 113, 250402 (2014) and often called Fourier
promise problem (FPP), can be solved with the quantum-$n$-switch and a single
call to each gate, while the best known causal algorithm so far calls $O(n^2)$
gates. In this work, we show that this advantage is smaller than expected. In
fact, we present a causal algorithm that solves the only known specific FPP
with $O(n \log(n))$ queries and a causal algorithm that solves every FPP with
$O(n\sqrt{n})$ queries. Besides the interest in such algorithms on their own,
our results limit the expected advantage of indefinite causal structures for
these problems.
