  In an ordinary quantum algorithm the gates are applied in a fixed order on
the systems. The introduction of indefinite causal structures allows to relax
this constraint and control the order of the gates with an additional quantum
state. It is known that this quantum-controlled ordering of gates can reduce
the query complexity in deciding a property of black-box unitaries with respect
to the best algorithm in which the gates are applied in a fixed order. However,
all tasks explicitly found so far require unitaries that either act on
unbounded dimensional quantum systems in the asymptotic limit (the limiting
case of a large number of black-box gates) or act on qubits, but then involve
only a few unitaries. Here we introduce tasks (1) for which there is a provable
computational advantage of a quantum-controlled ordering of gates in the
asymptotic case and (2) that require only qubit gates and are therefore
suitable to demonstrate this advantage experimentally. We study their solutions
with the quantum-$n$-switch and within the quantum circuit model and find that
while the $n$-switch requires to call each gate only once, a causal algorithm
has to call at least $2n-1$ gates. Furthermore, the best known solution with a
fixed gate ordering calls $O(n\log_2{(n)})$ gates.
