Experimental computational advantage from superposition of multiple temporal orders of quantum gates

Advanced models for quantum computation where even the circuit connections are subject to the quantum superposition principle have been recently introduced. There, a control quantum system can coherently control the order in which a target quantum system undergoes $N$ gate operations. This process is known as the quantum $N$-switch, and has been identified as a resource for several information-processing tasks. In particular, the quantum $N$-switch provides a computational advantage -- over all circuits with fixed gate orders -- for phase-estimation problems involving $N$ unknown unitary gates. However, the corresponding algorithm requires the target-system dimension to grow (super-)exponentially with $N$, making it experimentally demanding. In fact, all implementations of the quantum $N$-switch reported so far have been restricted to $N=2$. Here, we introduce a promise problem for which the quantum $N$-switch gives an equivalent computational speed-up but where the target-system dimension can be as small as 2 regardless of $N$. We use state-of-the-art multi-core optical fiber technology to experimentally demonstrate the quantum $N$-switch with $N = 4$ gates acting on a photonic-polarization qubit. This is the first observation of a quantum superposition of more than 2 temporal orders, and also demonstrates its usefulness for efficient phase-estimation.