Quantum algorithms solve certain computational problems faster than the best known classical algorithms. Many algorithms, including Shor's for factoring, Grover's for unstructured search, and the HHL for solving linear systems, rely on quantum phase estimation (QPE) as a fundamental subroutine. The QPE protocol proceeds through the initialization of a control register in a uniform superposition, controlled unitary evolution encoding the eigenphase, and a final inverse quantum Fourier transform followed by measurement to extract the phase. Here, we address a special class of unitary operators that frequently appear in quantum Fourier transform-based protocols, cyclic group representations, and periodically evolving quantum systems. We introduce a QPE algorithm that successfully reduces the circuit complexity from O(n2) to O(n) for a special class of unitary operators and implement it on a four-qubit photonic system. The four-qubit system is realised using a photon pair, with two qubits encoded in its polarization degree of freedom and the remaining two in its path modes. In contrast to previous photonic implementations of QPE based on dual-rail encoding and KLM protocol, where controlled operations are inherently probabilistic and thus reduce the overall success probability of phase estimation, our scheme is fully deterministic. Moreover, it is scalable to higher-dimensional unitaries, provided the underlying structure of the unitaries is preserved.
We study the randomized classical query complexity of cyclic Forrelation, a cyclic analogue of k-Forrelation [AA15, STOC'15; BS21, STOC'21]. Given k Boolean functions f1,…,fk:F2n→{−1,1}, the goal is to estimate Tk=N−1Tr(Df1H⊗n⋯DfkH⊗n), where Dfi=diag(fi(x):x∈F2n), H is the Hadamard gate, and N=2n. This normalized-trace problem can be solved with k quantum queries in the DQC1 model. Its classical query complexity was left open in [JLS+26, FOCS'26], which conjectured a lower bound of Ω(N1−2/k).
We establish a nearly complete characterization of the nonadaptive classical query complexity of cyclic Forrelation. For even k≥4, we prove a tight bound of Θk(N1−2/k) for constant additive error. For odd k≥5, we obtain a lower bound of Ωk(N1−2/(k−1)) and an upper bound of Ok(N1−2/k). Surprisingly, k=3 admits a polylogarithmic-query nonadaptive classical algorithm, disproving the conjecture in this case. These results suggest an unexpected parity-dependent structure: the nonadaptive complexity may be governed by the independence number of the k-cycle, leading to the exponent 1−1/⌊k/2⌋, rather than the previously conjectured 1−2/k, which was motivated by a Fourier-growth heuristic. Finally, allowing adaptivity, we prove a lower bound of Ω(N1/4) for every k≥4.
Although formally close to k-Forrelation, the cyclic structure leads to rather different classical behavior and requires different techniques. Our lower bounds are based on hidden-shift collision constructions, and our upper bounds follow from randomized sampling together with cycle-specific conditional-moment estimates. Our results provide a systematic understanding of its query advantages over classical computation.
Gate-based quantum computers can in principle simulate the adiabatic dynamics of a large class of Hamiltonians. Here, we consider the cyclic adiabatic evolution of a parameter in the Hamiltonian. We propose a quantum algorithm to estimate the Berry phase and use it to classify the topological order of both single-particle and interacting models, highlighting the differences between the two. This algorithm is extensible to an interacting topological system. Our results evidence the potential of near-term quantum hardware for the topological classification of quantum matter.