Reassessing the computational advantage of quantum-controlled ordering of gates

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 Araújo 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\left(n^2\right)$ gates. In this article, 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(nlog\left(n\right))$ queries and a causal algorithm that solves every FPP with $O\left(n\sqrt{n}\right)$ queries. Besides the interest in such algorithms on their own, our results limit the expected advantage of indefinite causal structures for these problems.

Figure 1

The quantum-3-switch: Depending on the state of the control system, the gates act on the target system in a different order. For the case of $n=3$, each basis state of the six-dimensional control system realizes a different permutation of the gates. If the control system is initialized in a superposition, the $n$-switch can be used to solve Fourier promise problems. In this way, each unitary $U_i$ is called only once.

Figure 2

Solution of every FPP with the simulation of the quantum-$n$-switch: With a Fourier transform the control system is prepared in an equal superposition of all states $x$. The simulation of the $n$-switch $S_n^{\text{sim}}$ applies, depending on the state of the control system $|x\rangle$, the permutation ${\mathrm{\Pi }}_x$ on the target system. The solution $y$ can be read out after applying the inverse Fourier transform to the control system.

Figure 3

A simulation of the $n$-switch with a causal algorithm: The permutation ${\mathrm{\Pi }}_x$ is applied on $|{\mathrm{\Psi }}_t\rangle$ by swapping the target system in each step $i=0,1,...,n-1$ with the auxiliary system $|a_{{\sigma }_x\left(i\right)}\rangle$.

Figure 4

General structure of the algorithms in this article: With a quantum Fourier transform the control system is initialized in an equal superposition of all states $|x\rangle$. After the transformation $T_n^{\text{FPP}}$ (see main text) is applied, the final state of each target and auxiliary system becomes independent of $x$ and the solution $y$ can be read out by a measurement of the control system in the Fourier basis.

Figure 5

Simulation of the 3-switch ($S_3^{\text{sim.}}$) with the smallest possible number of used black-box gates.

Figure 6

An implementation of $T_3^{\text{FPP}}$ that solves every FPP for three unitaries.

Figure 7

Implementation of the transformation $T_4^{\text{FPP}}$ for the factoradic labeling of the permutations. The labeling of the target systems $|{\mathrm{\Psi }}_{2^i,j}\rangle$ is introduced in Sec. 5b. For the moment, it is only important that each target system is initialized in an arbitrary $d$-dimensional state.

Figure 8

The quantum circuit implementing the transformation $T_n^{\text{FPP}}$ for the FPP with the factoradic labeling of the permutations: Depending on the state of the control qubits, the gates are applied on the target systems in a certain order. Due to the pairwise commutation relations, the final state of each target system can always be reordered but certain phases are picked up when two unitaries are commuted. For every $x\in \{0,1,...,n!-1\}$, these phases multiply together to ${\omega }^{x·y}$ (see main text).

Figure 9

Each control qubit $|c_{k,i}^x\rangle$ controls whether the gate $U_k$ (with $k\equiv j\left(\mathrm{mod}{2}^i\right)$) is applied either before or after an entire block of unitaries with a smaller index. For example, if $|c_{2^i+j,i}^x=1\rangle$ the gate $U_{2^i+j}$ is applied before $U_0$ and $U_j$, while if $|c_{2^i+j,i}^x=0\rangle$ it is applied after these two gates. Rewriting the final state leads to a factor of ${\omega }^{2·(2^i+j)!·y}$ whenever $|c_{2^i+j,i}^x=1\rangle$.

Figure 10

The quantum algorithm that implements $T_n^{\text{FPP}}$ for every FPP with $O\left(n\sqrt{n}\right)$ queries. The circuit is decomposed into three parts that are explained in the main text.

Figure 11

Implementation of $V_{{\mathrm{\Psi }}_k}$.

Figure 12

Implementation of $W_{{\mathrm{\Phi }}_k}$.

Figure 13

Implementation of $X_{\text{Part}\text{2}}$.

Figure 14

The algorithm of Sec. 5b (Fig. 8) for $n=8$.