Computational Advantage from Quantum-Controlled Ordering of Gates

It is usually assumed that a quantum computation is performed by applying gates in a specific order. One can relax this assumption by allowing a control quantum system to switch the order in which the gates are applied. This provides a more general kind of quantum computing that allows transformations on blackbox quantum gates that are impossible in a circuit with fixed order. Here we show that this model of quantum computing is physically realizable, by proposing an interferometric setup that can implement such a quantum control of the order between the gates. We show that this new resource provides a reduction in computational complexity: we propose a problem that can be solved by using $O(n)$ blackbox queries, whereas the best known quantum algorithm with fixed order between the gates requires $O(n^2)$ queries. Furthermore, we conjecture that solving this problem in a classical computer takes exponential time, which may be of independent interest.

Figure 1

Linear optical implementation of the 2-switch. The unitaries $U_0$ and $U_1$ act on internal degrees of freedom of a single photon, such as space bins, time bins, or angular momentum modes. The polarization state of the photon determines the order in which the unitaries are applied. A photon with polarization $|H⟩$ is transmitted by the polarizing beam splitters (PBSs), so that $U_0$ is applied before $U_1$. For a photon with polarization $|V⟩$, reflected by the PBSs, $U_1$ is applied first and $U_0$ second.

Figure 2

Implementation of the $n$-switch (in the figure, $n=3$). Both the control and target, in state $|x⟩$ and $|\psi ⟩$, respectively, are encoded in a single (possibly multiparticle) system. When the system enters the $n$-routers ($R_n$) in mode $j$, it is redirected to mode ${\sigma }_x(j)$, and the unitary $U_{{\sigma }_x(j)}$ is applied to $|\psi ⟩$. $R_n^{-1}$ performs the inverse permutation and sends the system to mode $j+1$ of the first router. In this way, a system entering mode 0 of the first router eventually exits mode $n-1$ of the second router with the target in the state ${\mathrm{\Pi }}_x|\psi ⟩$.