-
Rotation Sets and Topological Entropy for Random Circle Endomorphisms
Authors:
Zixu Li,
Simon Lloyd,
Sergio Romaña
Abstract:
We study the topological dynamics of random circle endomorphisms of degree one over an ergodic measure-preserving dynamical system. Under an integrability assumption, we prove that the random rotation set is almost surely the compact interval whose endpoints are the mean random rotation numbers of the associated lower and upper random maps. We also show that the natural orbitwise versions of the r…
▽ More
We study the topological dynamics of random circle endomorphisms of degree one over an ergodic measure-preserving dynamical system. Under an integrability assumption, we prove that the random rotation set is almost surely the compact interval whose endpoints are the mean random rotation numbers of the associated lower and upper random maps. We also show that the natural orbitwise versions of the random rotation set agree almost surely, and on the same full-measure set, every value in this interval is realised as the asymptotic average displacement along an individual orbit. In addition, every closed subinterval of the random rotation set is realised, on a full-measure set, as the set of accumulation values of the displacement averages along a single orbit. Finally, we prove that a positive length of the random rotation set implies a positive random topological entropy, in contrast to random monotone maps, which have zero random topological entropy. We illustrate the theory by computing the random rotation set and random topological entropy for a piecewise linear example.
△ Less
Submitted 15 June, 2026;
originally announced June 2026.
-
Lift-Free Approaches to Random Rotation Number and Numerical Approximation
Authors:
Zixu Li,
Simon Lloyd
Abstract:
We study the random rotation number for random circle homeomorphisms. We introduce two new definitions of the random rotation number that can be stated without reference to any choice of lift of the dynamics to the real line, and prove that they are equivalent to the standard random rotation number. We then prove that the mean random rotation number may be approximated within an error of $1/n$ whe…
▽ More
We study the random rotation number for random circle homeomorphisms. We introduce two new definitions of the random rotation number that can be stated without reference to any choice of lift of the dynamics to the real line, and prove that they are equivalent to the standard random rotation number. We then prove that the mean random rotation number may be approximated within an error of $1/n$ when using $n$ iterations of the dynamics. Finally, we develop numerical algorithms for approximation of the random rotation number which we test with several examples.
△ Less
Submitted 26 March, 2026;
originally announced March 2026.
-
Periodicity and Rotation Number for Random Circle Homeomorphisms
Authors:
Zixu Li,
Simon Lloyd
Abstract:
We study discrete-time random dynamical systems where each fibre map is an orientation-preserving homeomorphism of the circle. We prove that the existence of a random periodic cycle with period at least two implies that the random rotation number is rational almost surely. Moreover, in clear contrast with the deterministic setting, we demonstrate that a common fixed point for the fibre maps does n…
▽ More
We study discrete-time random dynamical systems where each fibre map is an orientation-preserving homeomorphism of the circle. We prove that the existence of a random periodic cycle with period at least two implies that the random rotation number is rational almost surely. Moreover, in clear contrast with the deterministic setting, we demonstrate that a common fixed point for the fibre maps does not imply that the random rotation number is an integer. Conversely, we show that if the mean random rotation number is an integer, then the fibre maps have a fixed point with positive probability.
△ Less
Submitted 19 March, 2026;
originally announced March 2026.
-
A quantum algorithm for Khovanov homology
Authors:
Alexander Schmidhuber,
Michele Reilly,
Paolo Zanardi,
Seth Lloyd,
Aaron Lauda
Abstract:
Khovanov homology is a topological knot invariant that categorifies the Jones polynomial, recognizes the unknot, and is conjectured to appear as an observable in $4D$ supersymmetric Yang--Mills theory. Despite its rich mathematical and physical significance, the computational complexity of Khovanov homology remains largely unknown. To address this challenge, this work initiates the study of effici…
▽ More
Khovanov homology is a topological knot invariant that categorifies the Jones polynomial, recognizes the unknot, and is conjectured to appear as an observable in $4D$ supersymmetric Yang--Mills theory. Despite its rich mathematical and physical significance, the computational complexity of Khovanov homology remains largely unknown. To address this challenge, this work initiates the study of efficient quantum algorithms for Khovanov homology.
We provide simple proofs that increasingly accurate additive approximations to the ranks of Khovanov homology are DQC1-hard, BQP-hard, and #P-hard, respectively. For the first two approximation regimes, we propose a novel quantum algorithm. Our algorithm is efficient provided the corresponding Hodge Laplacian thermalizes in polynomial time and has a sufficiently large spectral gap, for which we give numerical and analytical evidence.
Our approach introduces a pre-thermalization procedure that allows our quantum algorithm to succeed even if the Betti numbers of Khovanov homology are much smaller than the dimensions of the corresponding chain spaces, overcoming a limitation of prior quantum homology algorithms. We introduce novel connections between Khovanov homology and graph theory to derive analytic lower bounds on the spectral gap.
△ Less
Submitted 23 January, 2025; v1 submitted 21 January, 2025;
originally announced January 2025.
-
Block-encoding dense and full-rank kernels using hierarchical matrices: applications in quantum numerical linear algebra
Authors:
Quynh T. Nguyen,
Bobak T. Kiani,
Seth Lloyd
Abstract:
Many quantum algorithms for numerical linear algebra assume black-box access to a block-encoding of the matrix of interest, which is a strong assumption when the matrix is not sparse. Kernel matrices, which arise from discretizing a kernel function $k(x,x')$, have a variety of applications in mathematics and engineering. They are generally dense and full-rank. Classically, the celebrated fast mult…
▽ More
Many quantum algorithms for numerical linear algebra assume black-box access to a block-encoding of the matrix of interest, which is a strong assumption when the matrix is not sparse. Kernel matrices, which arise from discretizing a kernel function $k(x,x')$, have a variety of applications in mathematics and engineering. They are generally dense and full-rank. Classically, the celebrated fast multipole method performs matrix multiplication on kernel matrices of dimension $N$ in time almost linear in $N$ by using the linear algebraic framework of hierarchical matrices. In light of this success, we propose a block-encoding scheme of the hierarchical matrix structure on a quantum computer. When applied to many physical kernel matrices, our method can improve the runtime of solving quantum linear systems of dimension $N$ to $O(κ\operatorname{polylog}(\frac{N}{\varepsilon}))$, where $κ$ and $\varepsilon$ are the condition number and error bound of the matrix operation. This runtime is near-optimal and, in terms of $N$, exponentially improves over prior quantum linear systems algorithms in the case of dense and full-rank kernel matrices. We discuss possible applications of our methodology in solving integral equations and accelerating computations in N-body problems.
△ Less
Submitted 6 December, 2022; v1 submitted 27 January, 2022;
originally announced January 2022.
-
Quantum advantage for differential equation analysis
Authors:
Bobak T. Kiani,
Giacomo De Palma,
Dirk Englund,
William Kaminsky,
Milad Marvian,
Seth Lloyd
Abstract:
Quantum algorithms for both differential equation solving and for machine learning potentially offer an exponential speedup over all known classical algorithms. However, there also exist obstacles to obtaining this potential speedup in useful problem instances. The essential obstacle for quantum differential equation solving is that outputting useful information may require difficult post-processi…
▽ More
Quantum algorithms for both differential equation solving and for machine learning potentially offer an exponential speedup over all known classical algorithms. However, there also exist obstacles to obtaining this potential speedup in useful problem instances. The essential obstacle for quantum differential equation solving is that outputting useful information may require difficult post-processing, and the essential obstacle for quantum machine learning is that inputting the training set is a difficult task just by itself. In this paper, we demonstrate, when combined, these difficulties solve one another. We show how the output of quantum differential equation solving can serve as the input for quantum machine learning, allowing dynamical analysis in terms of principal components, power spectra, and wavelet decompositions. To illustrate this, we consider continuous time Markov processes on epidemiological and social networks. These quantum algorithms provide an exponential advantage over existing classical Monte Carlo methods.
△ Less
Submitted 26 April, 2022; v1 submitted 29 October, 2020;
originally announced October 2020.
-
The Quantum Wasserstein Distance of Order 1
Authors:
Giacomo De Palma,
Milad Marvian,
Dario Trevisan,
Seth Lloyd
Abstract:
We propose a generalization of the Wasserstein distance of order 1 to the quantum states of $n$ qudits. The proposal recovers the Hamming distance for the vectors of the canonical basis, and more generally the classical Wasserstein distance for quantum states diagonal in the canonical basis. The proposed distance is invariant with respect to permutations of the qudits and unitary operations acting…
▽ More
We propose a generalization of the Wasserstein distance of order 1 to the quantum states of $n$ qudits. The proposal recovers the Hamming distance for the vectors of the canonical basis, and more generally the classical Wasserstein distance for quantum states diagonal in the canonical basis. The proposed distance is invariant with respect to permutations of the qudits and unitary operations acting on one qudit and is additive with respect to the tensor product. Our main result is a continuity bound for the von Neumann entropy with respect to the proposed distance, which significantly strengthens the best continuity bound with respect to the trace distance. We also propose a generalization of the Lipschitz constant to quantum observables. The notion of quantum Lipschitz constant allows us to compute the proposed distance with a semidefinite program. We prove a quantum version of Marton's transportation inequality and a quantum Gaussian concentration inequality for the spectrum of quantum Lipschitz observables. Moreover, we derive bounds on the contraction coefficients of shallow quantum circuits and of the tensor product of one-qudit quantum channels with respect to the proposed distance. We discuss other possible applications in quantum machine learning, quantum Shannon theory, and quantum many-body systems.
△ Less
Submitted 13 January, 2022; v1 submitted 9 September, 2020;
originally announced September 2020.
-
Simplicial Ricci Flow: An Example of a Neck Pinch Singularity in 3D
Authors:
Paul M. Alsing,
Warner A. Miller,
Matthew Corne,
Xianfeng Gu,
Seth Lloyd,
Shannon Ray,
Shing-Tung Yau
Abstract:
We examine a Type-1 neck pinch singularity in simplicial Ricci flow (SRF) for an axisymmetric piecewise flat 3-dimensional geometry with 3-sphere topology. SRF was recently introduced as an unstructured mesh formulation of Hamilton's Ricci flow (RF). It describes the RF of a piecewise-flat simplicial geometry. In this paper, we apply the SRF equations to a representative double-lobed axisymmetric…
▽ More
We examine a Type-1 neck pinch singularity in simplicial Ricci flow (SRF) for an axisymmetric piecewise flat 3-dimensional geometry with 3-sphere topology. SRF was recently introduced as an unstructured mesh formulation of Hamilton's Ricci flow (RF). It describes the RF of a piecewise-flat simplicial geometry. In this paper, we apply the SRF equations to a representative double-lobed axisymmetric piecewise flat geometry with mirror symmetry at the neck similar to the geometry studied by Angenent and Knopf (A-K). We choose a specific radial profile and compare the SRF equations with the corresponding finite-difference solution of the continuum A-K RF equations. The piecewise-flat 3-geometries considered here are built of isosceles-triangle-based frustum blocks. The axial symmetry of this model allows us to use frustum blocks instead of tetrahedra. The 2-sphere cross-sectional geometries in our model are regular icosahedra. We demonstrate that, under a suitably-pinched initial geometry, the SRF equations for this relatively low-resolution discrete geometry yield the canonical Type-1 neck pinch singularity found in the corresponding continuum solution. We adaptively remesh during the evolution to keep the circumcentric dual lattice well-centered. Without such remeshing, we cannot evolve the discrete geometry to neck pinch. We conclude with a discussion of future generalizations and tests of this SRF model.
△ Less
Submitted 28 April, 2014; v1 submitted 19 August, 2013;
originally announced August 2013.
-
A semi-invertible Oseledets Theorem with applications to transfer operator cocycles
Authors:
Gary Froyland,
Simon Lloyd,
Anthony Quas
Abstract:
Oseledets' celebrated Multiplicative Ergodic Theorem (MET) is concerned with the exponential growth rates of vectors under the action of a linear cocycle on R^d. When the linear actions are invertible, the MET guarantees an almost-everywhere pointwise splitting of R^d into subspaces of distinct exponential growth rates (called Lyapunov exponents). When the linear actions are non-invertible, Osel…
▽ More
Oseledets' celebrated Multiplicative Ergodic Theorem (MET) is concerned with the exponential growth rates of vectors under the action of a linear cocycle on R^d. When the linear actions are invertible, the MET guarantees an almost-everywhere pointwise splitting of R^d into subspaces of distinct exponential growth rates (called Lyapunov exponents). When the linear actions are non-invertible, Oseledets' MET only yields the existence of a filtration of subspaces, the elements of which contain all vectors that grow no faster than exponential rates given by the Lyapunov exponents. The authors recently demonstrated that a splitting over R^d is guaranteed even without the invertibility assumption on the linear actions. Motivated by applications of the MET to cocycles of (non-invertible) transfer operators arising from random dynamical systems, we demonstrate the existence of an Oseledets splitting for cocycles of quasi-compact non-invertible linear operators on Banach spaces.
△ Less
Submitted 28 January, 2010;
originally announced January 2010.
-
Coherent sets for nonautonomous dynamical systems
Authors:
Gary Froyland,
Simon Lloyd,
Naratip Santitissadeekorn
Abstract:
We describe a mathematical formalism and numerical algorithms for identifying and tracking slowly mixing objects in nonautonomous dynamical systems. In the autonomous setting, such objects are variously known as almost-invariant sets, metastable sets, persistent patterns, or strange eigenmodes, and have proved to be important in a variety of applications. In this current work, we explain how to…
▽ More
We describe a mathematical formalism and numerical algorithms for identifying and tracking slowly mixing objects in nonautonomous dynamical systems. In the autonomous setting, such objects are variously known as almost-invariant sets, metastable sets, persistent patterns, or strange eigenmodes, and have proved to be important in a variety of applications. In this current work, we explain how to extend existing autonomous approaches to the nonautonomous setting. We call the new time-dependent slowly mixing objects coherent sets as they represent regions of phase space that disperse very slowly and remain coherent. The new methods are illustrated via detailed examples in both discrete and continuous time.
△ Less
Submitted 1 February, 2010; v1 submitted 3 November, 2009;
originally announced November 2009.
-
On the Closing Lemma problem for vector fields of bounded type on the torus
Authors:
Simon Lloyd
Abstract:
We investigate the open Closing Lemma problem for vector fields on the 2-dimensional torus. Under the assumption of bounded type rotation number, the $C^r$ Closing Lemma is verified for smooth vector fields that are area-preserving at all saddle points. Namely, given such a $C^r$ vector field $X$, $r\geq 4$, with a non-trivially recurrent point $p$, there exists a vector field $Y$ arbitrarily ne…
▽ More
We investigate the open Closing Lemma problem for vector fields on the 2-dimensional torus. Under the assumption of bounded type rotation number, the $C^r$ Closing Lemma is verified for smooth vector fields that are area-preserving at all saddle points. Namely, given such a $C^r$ vector field $X$, $r\geq 4$, with a non-trivially recurrent point $p$, there exists a vector field $Y$ arbitrarily near to $X$ in the $C^r$ topology and obtained from $X$ by a twist perturbation, such that $p$ is a periodic point of $Y$.
The proof relies on a new result in 1-dimensional dynamics on the non-existence of semi-wandering intervals of smooth maps of the circle.
△ Less
Submitted 7 November, 2008;
originally announced November 2008.
-
Coherent structures and isolated spectrum for Perron-Frobenius cocycles
Authors:
Gary Froyland,
Simon Lloyd,
Anthony Quas
Abstract:
We present an analysis of one-dimensional models of dynamical systems that possess 'coherent structures'; global structures that disperse more slowly than local trajectory separation. We study cocycles generated by expanding interval maps and the rates of decay for functions of bounded variation under the action of the associated Perron-Frobenius cocycles.
We prove that when the generators are…
▽ More
We present an analysis of one-dimensional models of dynamical systems that possess 'coherent structures'; global structures that disperse more slowly than local trajectory separation. We study cocycles generated by expanding interval maps and the rates of decay for functions of bounded variation under the action of the associated Perron-Frobenius cocycles.
We prove that when the generators are piecewise affine and share a common Markov partition, the Lyapunov spectrum of the Perron-Frobenius cocycle has at most finitely many isolated points. Moreover, we develop a strengthened version of the Multiplicative Ergodic Theorem for non-invertible matrices and construct an invariant splitting into Oseledets subspaces.
We detail examples of cocycles of expanding maps with isolated Lyapunov spectrum and calculate the Oseledets subspaces, which lead to an identification of the underlying coherent structures.
Our constructions generalise the notions of almost-invariant and almost-cyclic sets to non-autonomous dynamical systems and provide a new ensemble-based formalism for coherent structures in one-dimensional non-autonomous dynamics.
△ Less
Submitted 9 April, 2008;
originally announced April 2008.
-
Affine interval exchange transformations with flips and wandering intervals
Authors:
C. Gutierrez,
S. Lloyd,
B. Pires
Abstract:
There exist uniquely ergodic affine interval exchange transformations of [0,1] with flips having wandering intervals and such that the support of the invariant measure is a Cantor set.
There exist uniquely ergodic affine interval exchange transformations of [0,1] with flips having wandering intervals and such that the support of the invariant measure is a Cantor set.
△ Less
Submitted 28 February, 2008;
originally announced February 2008.
-
Unique ergodicity of circle and interval exchange transformations with flips
Authors:
C. Gutierrez,
S. Lloyd,
V. Medvedev,
B. Pires,
E. Zhuzhoma
Abstract:
We study the existence of transitive exchange maps with flips defined on the unit circle. We provide a complete answer to the question of whether there exists a transitive exchange map of the unit circle defined on n subintervals and having f flips.
We study the existence of transitive exchange maps with flips defined on the unit circle. We provide a complete answer to the question of whether there exists a transitive exchange map of the unit circle defined on n subintervals and having f flips.
△ Less
Submitted 9 September, 2008; v1 submitted 24 November, 2007;
originally announced November 2007.