Higher-order networks with multiway interactions can exhibit collective dynamical phenomena that are absent in traditional pairwise network models. However, analyzing such dynamics becomes computationally prohibitive as their state space grows combinatorially in the multiway interaction order. Here we develop quantum algorithms for two central tasks -- synchronization estimation and certification of the no-phase-locking regime -- in the simplicial Kuramoto model. This model is a higher-order generalization of the celebrated Kuramoto model for coupled oscillators on graph-based networks. Under explicit assumptions on data access and types, and simplicial structure, we derive end-to-end quantum gate complexities and identify regimes with polynomial quantum advantage for synchronization estimation and super-polynomial quantum advantage for no-phase-locking certification over classical methods. More broadly, these results extend quantum algorithms for higher-order networks from structural analysis to nonlinear dynamical diagnostics, easing a major computational bottleneck and opening a route to quantum methods for probing higher-order phenomena beyond the reach of direct classical approaches.
Higher-order networks with multiway interactions can exhibit collective dynamical phenomena that are absent in traditional pairwise network models. However, analyzing such dynamics becomes computationally prohibitive as their state space grows combinatorially in the multiway interaction order. Here we develop quantum algorithms for two central tasks -- synchronization estimation and certification of the no-phase-locking regime -- in the simplicial Kuramoto model. This model is a higher-order generalization of the celebrated Kuramoto model for coupled oscillators on graph-based networks. Under explicit assumptions on data access and types, and simplicial structure, we derive end-to-end quantum gate complexities and identify regimes with polynomial quantum advantage for synchronization estimation and super-polynomial quantum advantage for no-phase-locking certification over classical methods. More broadly, these results extend quantum algorithms for higher-order networks from structural analysis to nonlinear dynamical diagnostics, easing a major computational bottleneck and opening a route to quantum methods for probing higher-order phenomena beyond the reach of direct classical approaches.
Synchronization is a collective phenomenon in which interacting nonlinear oscillators develop a persistent relation between their phases and frequencies. In quantum systems, its description requires connecting the classical dynamics of limit-cycle oscillators with quantum fluctuations, dissipation, and the notion of phase. In this tutorial review, we offer a systematic framework for analyzing synchronization in classical and quantum dynamical systems. Starting from amplitude-phase dynamics, we introduce successively topics of relevance, such as phase locking, the Adler equation, Arnold tongues, and the Kuramoto model, and use these concepts to analyze coupled oscillators and their stability. We then formulate the corresponding description for quantum limit-cycle oscillators using Lindblad master equations and phase-space methods, with explicit examples of two and many coupled oscillators. We further discuss noise, synchronization measures, and the extreme quantum regime, including synchronization in spin systems. The emphasis throughout is on analytical derivations and a practical methodology for identifying synchronized states, determining their stability, and characterizing synchronization in quantum systems. The review is designed as a self-contained guide from which we hope that students can learn the essential concepts and techniques, while researchers can readily find the analytical tools and methodological insights needed to approach new synchronization problems.
Higher-order networks (HONs) represent interactions among groups of objects, supporting the study of collective behaviour that pairwise models can miss. In simplicial models of these networks, Hodge Laplacian linear systems provide a common mathematical framework for analysis, for example, for solving statistical ranking problems and investigating long-term stability in coupled oscillator systems. The large number of variables associated with edges, triangles, and higher-dimensional simplices can make these systems costly to solve. Recent quantum algorithms address this bottleneck. However, comparisons with particular classical algorithms do not decision output whether solving these linear system problems establishes a quantum complexity foundation for provable quantum advantage. We prove that preparing a quantum state encoding the normalized minimum-norm solution of Hodge Laplacian linear systems is BQP-hard under the specified sparse oracle model and parameter promises. Our sequence of reductions maps an arbitrary polynomial-time bounded-error quantum computation to such linear systems. Each reduction allows efficient recovery of the normalized minimum-norm solution of the preceding linear system. Together with an efficient quantum algorithm for the associated decision problem from the approximate solution state, we show that this problem is BQP-complete. These results provide a worst-case complexity foundation for evaluating quantum advantage in HON analysis and show that the BQP-hardness of the quantum linear system problem (QLSP) persists even when the matrices are restricted to Hodge Laplacians.
Abstract We investigate a non-Abelian generalization of the Kuramoto model proposed by Lohe and given by N quantum oscillators (‘nodes’) connected by a quantum network where the wavefunction at each node is distributed over quantum channels to all other connected nodes. It leads to a system of Schrödinger equations coupled by nonlinear self-interacting potentials given by their correlations. We give a complete picture of synchronization results, given on the relative size of the natural frequency and the coupling constant, for two non-identical oscillators and show complete phase synchronization for arbitrary N > 2 identical oscillators. Our results are mainly based on the analysis of the ODE system satisfied by the correlations and on the introduction of a quantum order parameter, which is analogous to the one defined by Kuramoto in the classical model. As a consequence of the previous results, we obtain the synchronization of the probability and the current densities defined via the Madelung transformations.
This work investigates whether quantum walks on simplicial complexes exhibit quantum advantages. We introduce a novel quantum walk that encodes the combinatorial Laplacian, a key object reflecting the topology of the simplicial complex. We construct a unitary encoding projecting onto the kernel of the Laplacian, representing the harmonic cycles in the complex's homology. Our efficient construction of quantum walk unitaries for clique complexes paves the way for exploring higher-order interactions within topological structures. Our construction requires O ( n 3 log ( 1 / ϵ ) / λ k ) gates, where n is the number of vertices, λ k is the smallest non-zero eigenvalue of the Laplacian, and ϵ is the projection error. Our results indicate apparent superpolynomial quantum speedup with quantum walks, without quantum oracles, provided the spectral gap of the Laplacian is inverse-polynomially bounded and efficient simplex sampling is available.Crucially, the walk operates on a state space encompassing both positively and negatively oriented simplices, effectively doubling its size compared to unoriented approaches. Through coherent interference of these paired simplices, we are able to successfully encode the combinatorial Laplacian, which would otherwise be impossible. This is our major technical contribution. We also extend the framework by constructing variant quantum walks that enable us to: (1) estimate normalized persistent Betti numbers throughout a deformation process, (2) verify a specific QMA 1 -hard problem related to clique complex homology, showcasing potential applications in computational complexity theory, and (3) solve the high-dimensional discrete Dirichlet problem (HDDP), generalizing the classical discrete Dirichlet problem on graphs to simplicial complexes, with an apparent superpolynomial speedup over the best known classical algorithm.
We provide a rigorous theoretical analysis of quantum algorithms for shortest path problems in weighted graphs, establishing complexity-theoretic foundations for quantum acceleration in this fundamental computational domain. Building upon recent quantum adaptations of classical graph algorithms, we develop a unified framework that characterizes when and why quantum approaches offer computational advantages for single-source and all-pairs shortest path computations. Our analysis encompasses both positive-weight and negative-weight scenarios, deriving conditional speedup theorems that depend on graph structure, weight distribution, and oracle access models. We prove that quantum amplitude amplification and quantum walks can provide polynomial to exponential speedups under specific structural assumptions, while establishing hardness results that identify problem instances where quantum advantage is provably absent. The theoretical framework introduces novel complexity measures that capture graph-theoretic properties relevant to quantum algorithm performance, including quantum diameter, entanglement capacity, and interference efficiency. We extend our analysis to dynamic graph scenarios where edge weights evolve over time, establishing bounds on quantum advantage preservation under graph modifications. This work contributes fundamental insights into quantum algorithmic graph theory, clarifying the boundaries of quantum computational advantage and providing theoretical guidance for algorithm design in network optimization, routing, and graph analytics applications.
Abstract Nonlinear spectroscopy is a cornerstone of quantum science, providing unique access to multi-point correlations, quantum coherence, and couplings that are invisible to linear methods. However, classical simulation of these phenomena is fundamentally limited by the exponential growth of the Hilbert space, and practical quantum algorithms for the nonlinear regime have remained largely unexplored. Here, we present a unified quantum algorithmic framework for computing n-th order nonlinear spectroscopies. By reformulating multi-time responses as a weighted sum of expectation values at finite pump amplitudes via a generalized parameter shift rule, our approach bypasses the costly evaluation of high-order commutators and time-dependent operator expansions. This reformulation enables efficient execution via real-time evolution on current quantum hardware, ensuring inherent noise resilience. We validate the framework on IBM's superconducting quantum processors, successfully obtain higher-order response functions of a 12-qubit XXZ spin-chain. Furthermore, the versatility of our method is demonstrated by resolving quasi-particle excitation spectra in spin-liquids and identifying interaction-induced cross-peaks in atomic systems. Our results establish a practical and scalable pathway for probing complex quantum dynamics on near-term quantum devices, extending the reach of quantum simulation into the nonlinear domain.