Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Algorithm structures for cyclic phase estimation

José M. N. Leitão, José M. F. Moura

Published Jan 1, 1981• 2 citations
OpenAlex

Related papers

Mitigating noise effects in phase estimation via a quantum cyclic n -switch

Zhen-Dong Wei, Wei‐Bin Yan, Zhong‐Xiao Man +3 more

Physical Review A•Jun 23, 2026•0 citations

Deterministic Quantum Phase Estimation with Linear Circuit Complexity in a Photonic System

M. Midhuna, Ajay Jayachandran, Kanad Sengupta +2 more

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 $\mathcal{O}(n^2)$ to $\mathcal{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.

quant-pharXiv:2607.13404•Jul 16, 2026•0 citations

High Precision Algorithm for Phase Estimation

Alexander Steingaß

•Jan 1, 2001•0 citations

Exponential quantum-classical query separations for cyclic Forrelation

Yuxin Zhang, Changpeng Shao

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 $f_1,\ldots,f_k:\mathbb{F}_2^n\to\{-1,1\}$, the goal is to estimate $T_k=N^{-1}\operatorname{Tr}(D_{f_1}H^{\otimes n}\cdots D_{f_k}H^{\otimes n}),$ where $D_{f_i}=\operatorname{diag}(f_i(x):x\in\mathbb{F}_2^n)$, $H$ is the Hadamard gate, and $N=2^n$. 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 $\widetildeΩ(N^{1-2/k})$. We establish a nearly complete characterization of the nonadaptive classical query complexity of cyclic Forrelation. For even $k\ge 4$, we prove a tight bound of $Θ_k(N^{1-2/k})$ for constant additive error. For odd $k\ge 5$, we obtain a lower bound of $Ω_k(N^{1-2/(k-1)})$ and an upper bound of $O_k(N^{1-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/\lfloor k/2\rfloor$, 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 $Ω(N^{1/4})$ for every $k\ge4$. 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.

quant-pharXiv:2610.41694•Nov 2, 2026•0 citations

Phase Estimation and Its Applications

Weng-Long Chang, Athanasios V. Vasilakos

Studies in big data•Dec 21, 2020•0 citations

Berry phase estimation in gate-based adiabatic quantum simulation

Bruno Murta, Gonçalo Catarina, Joaquín Fernández-Rossier

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.

arXiv:1909.09415•Physical Review A•Feb 11, 2020•18 citations
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)\mathcal{O}(n^2)O(n2) to O(n)\mathcal{O}(n)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 kkk-Forrelation [AA15, STOC'15; BS21, STOC'21]. Given kkk Boolean functions f1,…,fk:F2n→{−1,1}f_1,\ldots,f_k:\mathbb{F}_2^n\to\{-1,1\}f1​,…,fk​:F2n​→{−1,1}, the goal is to estimate Tk=N−1Tr⁡(Df1H⊗n⋯DfkH⊗n),T_k=N^{-1}\operatorname{Tr}(D_{f_1}H^{\otimes n}\cdots D_{f_k}H^{\otimes n}),Tk​=N−1Tr(Df1​​H⊗n⋯Dfk​​H⊗n), where Dfi=diag⁡(fi(x):x∈F2n)D_{f_i}=\operatorname{diag}(f_i(x):x\in\mathbb{F}_2^n)Dfi​​=diag(fi​(x):x∈F2n​), HHH is the Hadamard gate, and N=2nN=2^nN=2n. This normalized-trace problem can be solved with kkk 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)\widetildeΩ(N^{1-2/k})Ω(N1−2/k). We establish a nearly complete characterization of the nonadaptive classical query complexity of cyclic Forrelation. For even k≥4k\ge 4k≥4, we prove a tight bound of Θk(N1−2/k)Θ_k(N^{1-2/k})Θk​(N1−2/k) for constant additive error. For odd k≥5k\ge 5k≥5, we obtain a lower bound of Ωk(N1−2/(k−1))Ω_k(N^{1-2/(k-1)})Ωk​(N1−2/(k−1)) and an upper bound of Ok(N1−2/k)O_k(N^{1-2/k})Ok​(N1−2/k). Surprisingly, k=3k=3k=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 kkk-cycle, leading to the exponent 1−1/⌊k/2⌋1-1/\lfloor k/2\rfloor1−1/⌊k/2⌋, rather than the previously conjectured 1−2/k1-2/k1−2/k, which was motivated by a Fourier-growth heuristic. Finally, allowing adaptivity, we prove a lower bound of Ω(N1/4)Ω(N^{1/4})Ω(N1/4) for every k≥4k\ge4k≥4. Although formally close to kkk-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.