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.