Search

The Burrows-Wheeler transform (BWT) is integral to the FM-index, which is used extensively in text compression, indexing, pattern search, and bioinformatic problems as de novo assembly and read alignment. Thus, efficient construction of the BWT in terms of time and memory usage is key to these applications. We present a novel external algorithm called Improved-Bucket Burrows-Wheeler transform (IBB) for constructing the BWT of DNA datasets with highly diverse sequence lengths. IBB uses a right-aligned approach to efficiently handle sequences of varying lengths, a tree-based data structure to manage relative insert positions and ranks, and fine buckets to reduce the necessary amount of input and output to external memory. Our experiments demonstrate that IBB is 10% to 40% faster than the best existing state-of-the-art BWT construction algorithms on most datasets while maintaining competitive memory consumption.

We use heuristic optimization methods in extensive computations to determine with low systematic error ground state configurations of the mean-field $p$-spin glass model with $p=3$. Here, all possible triplets in a system of $N$ Ising spins are connected with a bond. This model has been of recent interest, since it exhibits the ``overlap gap condition'', which should make it prohibitive to find ground states asymptotically with local search methods when compared, for instance, with the $p=2$ case better-known as the Sherrington-Kirkpatrick model (SK). Indeed, it proves more costly to find good approximations for $p=3$ than for SK, even for our heuristic. Compared to SK, the ground-state behavior for $p=3$ is quite distinct also in other ways. For SK, finite-size corrections for large system sizes $N\to\infty$ of both, the ensemble average over ground state energy densities and the width of their distribution, vary anomalously with non-integer exponents. In the $p=3$ case here, the energy density and its distribution appear to scale with $\ln N/N$ and $1/N$ corrections, respectively. The distribution itself is consistent with a Gumbel form. Even more stark is the contrast for the bond-diluted case, where SK has shown previously a notable variation of the anomalous corrections exponent with the bond density, while for $p=3$ no such variation is found here. Hence, for the 3-spin model, all measured corrections scale the same as for the random energy model (REM), corresponding to $p=\infty$. This would suggest that all $p$-spin models with $p\geq3$ exhibit the same ground-state corrections as in REM., Comment: RevTex 4.2, 5 pages, 5 pdf-figures incl., related information can be found at https://faculty.college.emory.edu/sites/boettcher/

We consider the hysteretic behavior of Ising spin glasses at $T=0$ for various modes of driving. Previous studies mostly focused on an infinitely slow speed $\dot{H}$ by which the external field $H$ was ramped to trigger avalanches of spin flips by starting with destabilizing a single spin while few have focused on the effect of different driving methods. First, we show that this conventional protocol imposes a system size dependence. Then, we numerically analyze the response of Ising spin glasses at rates $\dot{H}$ that are fixed as well, to elucidate the differences in the response. Specifically, we compare three different modes of ramping ($\dot{H}=c/N$, $\dot{H}=c/\sqrt{N}$, and $\dot{H}=c$ for constant $c$) for two types of spin glass systems of size $N$, representing dense networks by the Sherrington-Kirkpatrick model and sparse networks by the lattice spin glass in $d=3$ dimensions known as the Edwards Anderson model. Depending on the mode of ramping, we find that the response of each system, in form of spin-flip avalanches and other observables, can vary considerably. In particular, in the $N$-independent mode applied to the lattice spin glass, which is closest to experimental reality, we observe a percolation transition with a broad avalanche distribution between phases of localized and system-spanning responses. We explore implications for combinatorial optimization problems pertaining to sparse systems., Comment: 8 pages, 7 figures, RevTex, final version. For related work, see https://physics.emory.edu/faculty/boettcher/

We present a collection of simulations of the Edwards-Anderson lattice spin glass at $T=0$ to elucidate the nature of low-energy excitations over a range of dimensions that reach from physically realizable systems to the mean-field limit. Using heuristic methods, we sample ground states of instances to determine their energies while eliciting excitations through manipulating boundary conditions. We exploit the universality of the phase diagram of bond-diluted lattices to make such a study in higher dimensions computationally feasible. As a result, we obtain a verity of accurate exponents for domain wall stiffness and finite-size corrections that allow us to examine their dimensional behavior and their connection with predictions from mean-field theory. We also provide an experimentally testable prediction for the thermal-to-percolative crossover exponent in dilute lattices Ising spin glasses., Comment: 12 pages, 4 figs, 1 table. Review summarizing several dispersed papers with improved figures, published version. Related information can be found at https://physics.emory.edu/faculty/boettcher/

Constructing the Burrows-Wheeler transform (BWT) for long strings poses significant challenges regarding construction time and memory usage. We use a prefix of the suffix array to partition a long string into shorter substrings, thereby enabling the use of multi-string BWT construction algorithms to process these partitions fast. We provide an implementation partDNA for DNA sequences. Through comparison with state-of-the-art BWT construction algorithms, we show that partDNA with ropebwt2 offers a novel trade-off for construction time and memory usage for BWT construction on real genome datasets. Beyond this, the proposed partitioning strategy is applicable to strings of any alphabet.

The process of aging following a hard quench into a glassy state is characterized universally, for a wide class of materials, by logarithmic evolution of state variables and a power-law decay of two-time correlation functions that collapse only for the ratio of those times. This stands in stark contrast with relaxation in equilibrium materials, where time-translational invariance holds. It is by now widely recognized that these aging processes, which ever so slowly relax a complex disordered material after a quench, are facilitated by activated events. Yet, theories often cited to describe such a non-equilibrium process can be shown to miss pertinent aspects that are inherent to many experiments. A case in point are recent experiments on crumpling sheets of mylar loaded by a weight whose acoustic emissions are measured while the material buckles. Analyzing those local avalanches shows that crumpling is a log-Poisson process activated by increasingly rare record-sized fluctuations in a slowly stiffening material. Crumpling thus adds to a range of glassy materials exhibiting the log-Poisson property, which can be used to discriminate between theories., Comment: Formerly a comment, now expanded into full paper, with additional data and analysis. 5 pages, 5 figures, new supplement. For related information, see https://physics.emory.edu/faculty/boettcher/

Neighborhood queries and triple queries are the most common queries on graphs; thus, it is desirable to answer them efficiently on compressed data structures. We present a compression scheme called Incidence-Type-RePair (ITR) for graphs with labeled nodes and labeled edges based on RePair and apply the scheme to network, version, and RDF graphs. We show that ITR performs neighborhood queries and triple queries within only a few milliseconds and thereby outperforms existing RePair-based solutions on graphs while providing a compression size comparable to existing graph compressors.

In Changjun Fan et al. [Nature Communications https://doi.org/10.1038/s41467-023-36363-w (2023)], the authors present a deep reinforced learning approach to augment combinatorial optimization heuristics. In particular, they present results for several spin glass ground state problems, for which instances on non-planar networks are generally NP-hard, in comparison with several Monte Carlo based methods, such as simulated annealing (SA) or parallel tempering (PT). Indeed, those results demonstrate that the reinforced learning improves the results over those obtained with SA or PT, or at least allows for reduced runtimes for the heuristics before results of comparable quality have been obtained relative to those other methods. To facilitate the conclusion that their method is ''superior'', the authors pursue two basic strategies: (1) A commercial GUROBI solver is called on to procure a sample of exact ground states as a testbed to compare with, and (2) a head-to-head comparison between the heuristics is given for a sample of larger instances where exact ground states are hard to ascertain. Here, we put these studies into a larger context, showing that the claimed superiority is at best marginal for smaller samples and becomes essentially irrelevant with respect to any sensible approximation of true ground states in the larger samples. For example, this method becomes irrelevant as a means to determine stiffness exponents $\theta$ in $d>2$, as mentioned by the authors, where the problem is not only NP-hard but requires the subtraction of two almost equal ground-state energies and systemic errors in each of $\approx 1\%$ found here are unacceptable. This larger picture on the method arises from a straightforward finite-size corrections study over the spin glass ensembles the authors employ, using data that has been available for decades., Comment: 5 pages, 2 figures, comment on arXiv:2109.14411, related information can be found at https://physics.emory.edu/faculty/boettcher/

In Nature Machine Intelligence 4, 367 (2022), Schuetz et al provide a scheme to employ graph neural networks (GNN) as a heuristic to solve a variety of classical, NP-hard combinatorial optimization problems. It describes how the network is trained on sample instances and the resulting GNN heuristic is evaluated applying widely used techniques to determine its ability to succeed. Clearly, the idea of harnessing the powerful abilities of such networks to ``learn'' the intricacies of complex, multimodal energy landscapes in such a hands-off approach seems enticing. And based on the observed performance, the heuristic promises to be highly scalable, with a computational cost linear in the input size $n$, although there is likely a significant overhead in the pre-factor due to the GNN itself. However, closer inspection shows that the reported results for this GNN are only minutely better than those for gradient descent and get outperformed by a greedy algorithm, for example, for Max-Cut. The discussion also highlights what I believe are some common misconceptions in the evaluations of heuristics., Comment: RevTex4, 2 pages, 1 figure; comment on arXiv:2107.01188. Related information at http://www.physics.emory.edu/faculty/boettcher/

We offer an alternative real-space description, based purely on activated processes, for the understanding of relaxation dynamics in hierarchical landscapes. To this end, we use the cluster model, a coarse-grained lattice model of a jammed system, to analyze rejuvenation and memory effects during aging after a hard quench. In this model, neighboring particles on a lattice aggregate through local interactions into clusters that fragment with a probability based on their size. Despite the simplicity of the cluster model, it has been shown to reproduce salient observables of the aging dynamics in colloidal systems, such as those accounting for particle mobility and displacements. Here, we probe the model for more complex quench protocols and show that it exhibits rejuvenation and memory effects similar to those attributed to the complex hierarchical structure of a glassy energy landscape., Comment: 7 pages, 4 figures, RevTex4, final version with many revisions and improved figures, related information can be found at https://physics.emory.edu/faculty/boettcher/

We study transport within a spatially heterogeneous one-dimensional quantum walk with a combination of hierarchical and random barriers. Recent renormalization group calculations for a spatially disordered quantum walk with a regular hierarchy of barriers alone have shown a gradual decrease in transport but no localization for increasing (but finite) barrier sizes. In turn, it is well-known that extensive random disorder in the spatial barriers is sufficient to localize a quantum walk on the line. Here we show that adding only a sparse (sub-extensive) amount of randomness to a hierarchy of barriers is sufficient to induce localization such that transport ceases. Our numerical results suggest the existence of a localization transition for a combination of both, the strength of the regular barrier hierarchy at large enough randomness as well as the increasing randomness at sufficiently strong barriers in the hierarchy., Comment: 9 pages, 6 figures, RevTex, accepted manuscript available online at J. Phys. A. For related information, see http://www.physics.emory.edu/faculty/boettcher/

The transition into a glassy state of the ensemble of static, mechanically stable configurations of a tapped granular pile is explored using extensive molecular dynamics simulations. We show that different horizontal sub-regions ("layers") along the height of the pile traverse this transition in a similar manner but at distinct tap intensities. We supplement the conventional approach based purely on properties of the static configurations with investigations of the grain-scale dynamics by which the tap energy is transmitted throughout the pile. We find that the effective energy that particles dissipate is a function of each particle's location in the pile and, moreover, that its value plays a distinctive role in the transformation between configurations. This internal energy provides a "temperature-like" parameter that allows us to align the transition into the glassy state for all layers, as well as different annealing schedules, at a critical value., Comment: 8 pages, 5 figures; for related information, see http://www.physics.emory.edu/faculty/boettcher/

Cooperative events requiring anomalously large fluctuations are a defining characteristic for the onset of glassy relaxation across many materials. The importance of such intermittent events has been noted in systems as diverse as superconductors, metallic glasses, gels, colloids, and granular piles. Here, we show that prohibiting the attainment of new record-high energy fluctuations -- by explicitly imposing a ``lid'' on the fluctuation spectrum -- impedes further relaxation in the glassy phase. This lid allows us to directly measure the impact of record events on the evolving system in extensive simulations of aging in such vastly distinct glass formers as spin glasses and tapped granular piles. Interpreting our results in terms of a dynamics of records succeeds in explaining the ubiquity of both, the logarithmic decay of the energy and the memory effects encoded in the scaling of two-time correlation functions of aging systems., Comment: 6 pages, RevTex4, 6 pdf-figs, some revisions and new section on fluctuations in granular piles added. Related information can be found at http://www.physics.emory.edu/faculty/boettcher/

We explore the compaction dynamics of a granular pile after a hard quench from a liquid into the glassy regime. First, we establish that the otherwise athermal granular pile during tapping exhibits annealing behavior comparable to glassy polymer or colloidal systems. Like those other systems, the pile undergoes a glass transition and "freezes" into different non-equilibrium glassy states at low agitation for different annealing speeds, starting from the same initial equilibrium state at high agitation. Then, we quench the system instantaneously from the highly-agitated state to below the glass transition regime to study the ensuing aging dynamics. In this classical aging protocol, the density increases (i.e., the potential energy of the pile decreases) logarithmically over several decades in time. Instead of system-wide, thermodynamic measures, here we identify the intermittent, irreversible events ("quakes") that actually drive the glassy relaxation process. We find that the event rate decelerates hyperbolically, which explains the observed increase in density when the integrated contribution to the downward displacements is evaluated. We argue that such a hyperbolically decelerating event rate is consistent with a log-Poisson process, also found as a universal feature of aging in many thermal glasses., Comment: 5 pages (RevTex4) + 3 pages Supplementary Material (pdf), 5 figures (eps). Updated Supplement and added mp4-animation. Related information can be found at http://www.physics.emory.edu/faculty/boettcher/

We use record dynamics (RD), a coarse-grained description of the ubiquitous relaxation phenomenology known as "aging", as a diagnostic tool to find universal features that distinguish between the energy landscapes of Ising spin models and the ferromagnet. According to RD, a non-equilibrium system after a quench relies on fluctuations that randomly generate a sequence of irreversible record-sized events (quakes or avalanches) that allow the system to escape ever-higher barriers of meta-stable states within a complex, hierarchical energy landscape. Once these record events allow the system to overcome such barriers, the system relaxes by tumbling into the following meta-stable state that is marginally more stable. Within this framework, a clear distinction can be drawn between the coarsening dynamics of an Ising ferromagnet and the aging of the spin glass, which are often put in the same category. To that end, we interpolate between the spin glass and ferromagnet by varying the admixture $p$ of ferromagnetic over anti-ferromagnetic bonds from the glassy state (at 50% each) to wherever clear ferromagnetic behavior emerges. The accumulation of record events grows logarithmic with time in the glassy regime, with a sharp transition at a specific admixture into the ferromagnetic regime where such activations saturate quickly. We show this effect both for the Edwards-Anderson model on a cubic lattice as well as the Sherrington-Kirkpatrick (mean-field) spin glass. While this transition coincides with a previously observed zero-temperature equilibrium transition in the former, that transition has not yet been described for the latter., Comment: 8 pages, RevTex4, some improved explanations, related information can be found at http://www.physics.emory.edu/faculty/boettcher/

Record Dynamics (RD) deals with complex systems evolving through a sequence of metastable stages. These are macroscopically distinguishable and appear stationary, except for the sudden and rapid changes, called quakes, which induce the transitions from one stage to the next. This phenomenology is well known in physics as "physical aging", but from the vantage point of RD the evolution of a class of systems of physical, biological and cultural origin is rooted in a hierarchically structured configuration space and can therefore be analyzed by similar statistical tools. This colloquium paper strives to present in a coherent fashion methods and ideas that have gradually evolved over time. To this end, it first describes the differences and similarities between RD and two widespread paradigms of complex dynamics, Self Organized Criticality and Continuous Time Random Walks. It then outlines the Poissonian nature of records events in white noise time series, and connects it to the statistics of quakes in metastable hierarchical systems, arguing that the relaxation effects of quakes can generally be described by power laws unrelated to criticality. Several different applications of RD have been developed over the years. Some of these are described, showinghe basic RD hypothesis, the log time homogeneity of quake dynamics, can be empirically verified in a given context. The discussion summarizes the paper and briefly mentions applications not discussed in detail. Finally, the outlook points to possible improvements and to new areas of research where RG could be of use.

Like [1], we present an algorithm to compute the simulation of a query pattern in a graph of labeled nodes and unlabeled edges. However, our algorithm works on a compressed graph grammar, instead of on the original graph. The speed-up of our algorithm compared to the algorithm in [1] grows with the size of the graph and with the compression strength.

We present a numerical study of ground states of the dilute versions of the Sherrington-Kirkpatrick (SK) mean-field spin glass. In contrast to so-called "sparse" mean-field spin glasses that have been studied widely on random networks of finite (average or regular) degree, the networks studied here are randomly bond-diluted to an overall density $p$, such that the average degree diverges as $\sim pN$ with the system size $N$. Ground-state energies are obtained with high accuracy for random instances over a wide range of fixed $p$. Since this is a NP-hard combinatorial problem, we employ the Extremal Optimization heuristic to that end. We find that the exponent describing the finite-size corrections, $\omega$, varies continuously with $p$, a somewhat surprising result, as one would not expect that gradual bond-dilution would change the $T=0$ universality class of a statistical model. For $p\to1$, the familiar result of $\omega(p=1)\approx\frac{2}{3}$ for SK is obtained., Comment: 5 pages, RevTex, 3 Figs., 1 Tab. Several corrections and refinements. For related information see http://www.physics.emory.edu/faculty/boettcher/

We discuss the model of a one-dimensional, discrete-time walk on a line with spatial heterogeneity in the form of a variable set of ultrametric barriers. Inspired by the homogeneous quantum walk on a line, we develop a formalism by which the classical ultrametric random walk as well as the quantum walk can be treated in parallel by using a "coined" walk with internal degrees of freedom. For the random walk, this amounts to a $2^{{\rm nd}}$-order Markov process with a \emph{stochastic} coin, better known as an (anti-)persistent walk. When this coin varies spatially in the hierarchical manner of "ultradiffusion," it reproduces the well-known results of that model. The exact analysis employed for obtaining the walk dimension $d_{w}$, based on the real-space renormalization group (RG), proceeds virtually identical for the corresponding quantum walk with a $unitary$ coin. However, while the classical walk remains robustly diffusive ($d_{w}=\frac{1}{2}$) for a wide range of barrier heights, unitarity provides for a quantum walk dimension $d_{w}$ that varies continuously, for even the smallest amount of heterogeneity, from ballistic spreading ($d_{w}=1$) in the homogeneous limit to confinement ($d_{w}=\infty$) for diverging barriers. Yet for any $d_{w}<\infty$ the quantum ultra-walk never appears to localize., Comment: 10 pages, 4 figures. Extended version to provide more physical context; as to appear in PRR. For related information, see http://www.physics.emory.edu/faculty/boettcher/

We analyze the transformation of QUBO from its conventional Boolean presentation into an equivalent spin glass problem with coupled $\pm1$ spin variables exposed to a site-dependent external field. We find that in a widely used testbed for QUBO these fields tend to be rather large compared to the typical coupling and many spins in each optimal configurations simply align with the fields irrespective of their constraints. Thereby, the testbed instances tend to exhibit large redundancies - seemingly independent variables which contribute little to the hardness of the problem, however. We demonstrate various consequences of this insight, for QUBO solvers as well as for heuristics developed for finding spin glass ground states. To this end, we implement the Extremal Optimization (EO) heuristic, in a new adaptation for the QUBO problem. We also propose a novel way to assess the quality of heuristics for increasing problem sizes based on asymptotic scaling., Comment: RevTex, 9 pages, 7 figs, 2 tabs. Numerous clarifications. For related information, see http://www.physics.emory.edu/faculty/boettcher/

Experimental and theoretical studies of manganese deposition on graphene/Ni(111) shows that a thin ferromagnetic Ni3Mn layer, which is protected by the graphene overlayer, is formed upon Mn intercalation. The electronic bands of graphene are affected by Ni3Mn interlayer formation through a slight reduction of n-type doping compared to graphene/Ni(111) and a suppression of the interface states characteristic of graphene/Ni(111). Our DFT-based theoretical analysis of interface geometric, electronic, and magnetic structure gives strong support to our interpretation of the experimental scanning tunneling microscopy, low energy electron diffraction, and photoemission results, and shows that the magnetic structure of graphene is strongly influenced by Ni3Mn formation.

A discrete-time staggered quantum walk was recently introduced as a generalization that allows to unify other versions, such as the coined and Szegedy's walk. However, it also produces new forms of quantum walks not covered by previous versions. To explore their properties, we study here the staggered walk on a hexagonal lattice. Such a walk is defined using a set of overlapping tessellations that cover the graph edges, and each tessellation is a partition of the node set into cliques. The hexagonal lattice requires at least three tessellations. Each tessellation is associated with a local unitary operator and the product of the local operators defines the evolution operator of the staggered walk on the graph. After defining the evolution operator on the hexagonal lattice, we analyze the quantum walk dynamics with the focus on the position standard deviation and localization. We also obtain analytic results for the time complexity of spatial search algorithms with one marked node using cyclic boundary conditions., Comment: 8 pages, 5 figures

Aging is a ubiquitous relaxation dynamic in disordered materials. It ensues after a rapid quench from an equilibrium "fluid" state into a non-equilibrium, history-dependent jammed state. We propose a physically motivated description that contrasts sharply with a continuous-time random walk (CTRW) with broadly distributed trapping times commonly used to fit aging data. A renewal process like CTRW proves irreconcilable with the log-Poisson statistic exhibited, for example, by jammed colloids as well as by disordered magnets. A log-Poisson process is characteristic of the intermittent and decelerating dynamics of jammed matter usually activated by record-breaking fluctuations ("quakes"). We show that such a record dynamics (RD) provides a universal model for aging, physically grounded in generic features of free-energy landscapes of disordered systems., Comment: RevTex, 5 pages, removed supplement and added some clarifications. For related information, see http://www.physics.emory.edu/faculty/boettcher/

Isothermal simulational data for the 3D Edwards-Anderson spin glass are collected at several temperatures below $T_{\rm c}$ and, in analogy with a recent model of dense colloidal suspensions,interpreted in terms of clusters of contiguous spins overturned by quakes, non-equilibrium events linked to record sized energy fluctuations. We show numerically that, to a good approximation, these quakes are statistically independent and constitute a Poisson process whose average grows logarithmically in time. The overturned clusters are local projections on one of the two ground states of the model, and grow likewise logarithmically in time. Data collected at different temperatures $T$ can be collapsed by scaling them with $T^{1.75}$, a hitherto unnoticed feature of the E-A model, which we relate on the one hand to the geometry of configuration space and on the other to experimental memory and rejuvenation effects. The rate at which a cluster flips is shown to decrease exponentially with the size of the cluster, as recently assumed in a coarse grained model of dense colloidal dynamics. The evolving structure of clusters in real space is finally sssociated to the decay of the thermo-remanent magnetization. Our analysis provides an unconventional coarse-grained description of spin glass aging as statistically subordinated to a Poisson quaking process and highlights record dynamics as a viable common theoretical framework for aging in different systems., Comment: 13 pages, 6 figs. Revised text and notation, several typos corrected

We present results for the aging dynamics of a jammed 2D colloidal system obtained with molecular dynamics simulations. We performed extensive simulations to gather detailed statistics about rare rearrangement events. With a simple criterion for identifying irreversible events based on Voronoi tessellations, we find that the rate of those events decelerates hyperbolically. We track the probability density function for particle displacements, the van-Hove function, with sufficient statistics as to reveal its two-time dependence that is indicative of aging. Those displacements, measured from a waiting time $t_{w}$ after the quench up to times $t=t_{w}+\Delta t$, exhibit a data collapse as a function of $\Delta t/t_{w}$. These findings can be explained comprehensively as manifestations of "record dynamics", i.e., a relaxation dynamic driven by record-breaking fluctuations. We show that an on-lattice model of a colloid that was built on record dynamics indeed reproduces the experimental results in great detail.

The implementation of graphene in semiconducting technology requires the precise knowledge about the graphene-semiconductor interface. In our work the structure and electronic properties of the graphene/$n$-Ge(110) interface are investigated on the local (nm) and macro (from $\mu\mathrm{m}$ to mm) scales via a combination of different microscopic and spectroscopic surface science techniques accompanied by density functional theory calculations. The electronic structure of freestanding graphene remains almost completely intact in this system, with only a moderate $n$-doping indicating weak interaction between graphene and the Ge substrate. With regard to the optimization of graphene growth it is found that the substrate temperature is a crucial factor, which determines the graphene layer alignment on the Ge(110) substrate during its growth from the atomic carbon source. Moreover, our results demonstrate that the preparation routine for graphene on the doped semiconducting material ($n$-Ge) leads to the effective segregation of dopants at the interface between graphene and Ge(110). Furthermore, it is shown that these dopant atoms might form regular structures at the graphene/Ge interface and induce the doping of graphene. Our findings help to understand the interface properties of the graphene-semiconductor interfaces and the effect of dopants on the electronic structure of graphene in such systems., Comment: submitted on 21.12.2017; manuscript and supplementary info

We present an in-depth analytic study of discrete-time quantum walks driven by a non-reflective coin. Specifically, we compare the properties of the widely-used Grover coin ${\cal C}_{G}$ that is unitary and reflective (${\cal C}_{G}^{2}=\mathbb{I}$) with those of a $3\times3$ "rotational" coin ${\cal C}_{60}$ that is unitary but non-reflective (${\cal C}_{60}^{2}\not=\mathbb{I}$) and satisfies instead ${\cal C}_{60}^{6}=\mathbb{I}$, which corresponds to a rotation by $60^{\circ}$. While such a modification apparently changes the real-space renormalization group (RG) treatment, we show that nonetheless this non-reflective quantum walk remains in the same universality class as the Grover walk. We first demonstrate the procedure with ${\cal C}_{60}$ for a 3-state quantum walk on a one-dimensional (\emph{1d}) line, where we can solve the RG-recursions in closed form, in the process providing exact solutions for some difficult non-linear recursions. Then, we apply the procedure to a quantum walk on a dual Sierpinski gasket (DSG), for which we reproduce ultimately the same results found for ${\cal C}_{G}$, further demonstrating the robustness of the universality class., Comment: 14 pages, RevTex4, related information can be found at http://www.physics.emory.edu/faculty/boettcher/

We establish a lower bound concerning the computational complexity of Grover's algorithms on fractal networks. This bound provides general predictions for the quantum advantage gained for searching unstructured lists. It yields a fundamental criterion, derived from quantum transport properties, for the improvement a quantum search algorithm achieves over the corresponding classical search in a network based solely on its spectral dimension, $d_{s}$. Our analysis employs recent advances in the interpretation of the venerable real-space renormalization group (RG) as applied to quantum walks. It clarifies the competition between Grover's abstract algorithm, i.e., a rotation in Hilbert space, and quantum transport in an actual geometry. The latter is characterized in terms of the quantum walk dimension $d_{w}^{Q}$ and the spatial (fractal) dimension $d_{f}$ that is summarized simply by the spectral dimension of the network. The analysis simultaneously determines the optimal time for a quantum measurement and the probability for successfully pin-pointing a marked element in the network. The RG further encompasses an optimization scheme devised by Tulsi that allows to tune this probability to certainty, leaving quantum transport as the only limiting process. It considers entire families of problems to be studied, thereby establishing large universality classes for quantum search, which we verify with extensive simulations. The methods we develop could point the way towards systematic studies of universality classes in computational complexity to enable modification and control of search behavior., Comment: 12 pages, revtex-4.1, enclosed is also a Mathematica Notebook to reproduce and experiment with the calculations; related information can be found at http://www.physics.emory.edu/faculty/boettcher/

We introduce a new framework to analyze quantum algorithms with the renormalization group (RG). To this end, we present a detailed analysis of the real-space RG for discrete-time quantum walks on fractal networks and show how deep insights into the analytic structure as well as generic results about the long-time behavior can be extracted. The RG-flow for such a walk on a dual Sierpinski gasket and a Migdal-Kadanoff hierarchical network is obtained explicitly from elementary algebraic manipulations, after transforming the unitary evolution equation into Laplace space. Unlike for classical random walks, we find that the long-time asymptotics for the quantum walk requires consideration of a diverging number of Laplace-poles, which we demonstrate exactly for the closed form solution available for the walk on a 1d-loop. In particular, we calculate the probability of the walk to overlap with its starting position, which oscillates with a period that scales as $N^{d_{w}^{Q}/d_{f}}$ with system size $N$. While the largest Jacobian eigenvalue $\lambda_{1}$ of the RG-flow merely reproduces the fractal dimension, $d_{f}=\log_{2}\lambda_{1}$, the asymptotic analysis shows that the second Jacobian eigenvalue $\lambda_{2}$ becomes essential to determine the dimension of the quantum walk via $d_{w}^{Q}=\log_{2}\sqrt{\lambda_{1}\lambda_{2}}$. We trace this fact to delicate cancellations caused by unitarity. We obtain identical relations for other networks, although the details of the RG-analysis may exhibit surprisingly distinct features. Thus, our conclusions -- which trivially reproduce those for regular lattices with translational invariance with $d_{f}=d$ and $d_{w}^{Q}=1$ -- appear to be quite general and likely apply to networks beyond those studied here., Comment: 9 pages, revtex4, 3 figures, for related information, see http://www.physics.emory.edu/faculty/boettcher/

We consider discrete-time evolution equations in which the stochastic operator of a classical random walk is replaced by a unitary operator. Such a problem has gained much attention as a framework for coined quantum walks that are essential for attaining the Grover limit for quantum search algorithms in physically realizable, low-dimensional geometries. In particular, we analyze the exact real-space renormalization group (RG) procedure recently introduced to study the scaling of quantum walks on fractal networks. While this procedure, when implemented numerically, was able to provide some deep insights into the relation between classical and quantum walks, its analytic basis has remained obscure. Our discussion here is laying the groundwork for a rigorous implementation of the RG for this important class of transport and algorithmic problems, although some instances remain unresolved. Specifically, we find that the RG fixed-point analysis of the classical walk, which typically focuses on the dominant Jacobian eigenvalue $\lambda_{1}$, with walk dimension $d_{w}^{RW}=\log_{2}\lambda_{1}$, needs to be extended to include the subdominant eigenvalue $\lambda_{2}$, such that the dimension of the quantum walk obtains $d_{w}^{QW}=\log_{2}\sqrt{\lambda_{1}\lambda_{2}}$. With that extension, we obtain analytically previously conjectured results for $d_{w}^{QW}$ of Grover walks on all but one of the fractal networks that have been considered., Comment: 7 pages, RevTex4, 2 figures, for related information, see http://www.physics.emory.edu/faculty/boettcher/

In a broad class of complex materials a quench leads to a multi-scaled relaxation process known as aging. To explain its commonality and the astounding insensitivity to most microscopic details, record dynamics (RD) posits that a small set of increasingly rare and irreversible events, so called quakes, controls the dynamics. While key predictions of RD are known to concur with a number of experimental and simulational results, its basic assumption on the nature of quake statistics has proven extremely difficult to verify experimentally. The careful distinction of rare ("record") cage-breaking events from in-cage rattle accomplished in previous experiments on jammed colloids, enables us to extract the first direct experimental evidence for the fundamental hypothesis of RD that the rate of quakes decelerates with the inverse of the system age. The resulting description shows the predicted growth of the particle mean square displacement and of a mesoscopic lengthscale with the logarithm of time., Comment: 6 pages, RevTex, changed title, many updates and corrections; for related information, see http://www.physics.emory.edu/faculty/boettcher/

We consider the quantum search problem with a continuous time quantum walk for networks of finite spectral dimension d_{s} of the network Laplacian. For general networks of fractal (integer or non-integer) dimension d_{f}, for which in general d_{f}\not=d_{s}, it suggests that d_{s} is the scaling exponent that determines the computational complexity of the search. Our results are consistent with those of Childs and Goldstone [Phys. Rev. A 70 (2004), 022314] for lattices of integer dimension, where d=d_{f}=d_{s}. For general fractals, we find that the Grover limit of quantum search can be obtained whenever d_{s}>4. This complements the recent discussion of mean-field (i.e., d_{s}\to\infty) networks by Chakraborty et al. [Phys. Rev. Lett. 116 (2016), 100501] showing that for all those networks spatial search by quantum walk is optimal., Comment: 5 pages, 2 fitures

We evaluate spectral zeta-functions of certain network Laplacians that can be treated exactly with the renormalization group. As specific examples we consider a class of Hanoi networks and those hierarchical networks obtained by the Migdal-Kadanoff bond moving scheme from regular lattices. As possible applications of these results we mention quantum search algorithms as well as synchronization, which we discuss in more detail., Comment: 24 pages, 7 figures, numerous updates

We present an analytical and numerical study of the parking lot model (PLM) of granular relaxation and make a connection to the aging dynamics of dense colloids. As we argue, the PLM is a Kinetically Constrained Model which features astronomically large equilibration times and displays a characteristic aging behavior on all observable time scales. The density of parked cars displays quasi-equilibrium Gaussian fluctuations interspersed by increasingly rare intermittent events, quakes, which can lead to an increase of the density to new record values. Defining active clusters as the shortest domains of parked cars which must be re-arranged to allow further insertions, we find that their typical length grows logarithmically with time for low enough temperatures and show how the number of active clusters on average gradually decreases as the system approaches equilibrium. We further characterize the aging process in terms of the statistics of the record sized fluctuations in the interstitial free volume which lead to quakes and show that quakes are uncorrelated and that they can be approximately described as a Poisson process in logarithmic time., Comment: 9 pages, final version. For related information, see http://www.physics.emory.edu/faculty/boettcher/

We examine the effect of network heterogeneity on the performance of quantum search algorithms. To this end, we study quantum search on a tree for the oracle Hamiltonian formulation employed by continuous-time quantum walks. We use analytical and numerical arguments to show that the exponent of the asymptotic running time $\sim N^{\beta}$ changes uniformly from $\beta=0.5$ to $\beta=1$ as the searched-for site is moved from the root of the tree towards the leaves. These results imply that the time complexity of the quantum search algorithm on a balanced tree is closely correlated with certain path-based centrality measures of the searched-for site.

We derive the determinant of the Laplacian for the Hanoi networks and use it to determine their number of spanning trees (or graph complexity) asymptotically. While spanning trees generally proliferate with increasing average degree, the results show that modifications within the basic patterns of design of these hierarchical networks can lead to significant variations in their complexity. To this end, we develop renormalization group methods to obtain recursion equations from which many spectral properties can be obtained. This provides the basis for future applications to explore the physics of several dynamic processes., Comment: 14 pages, RevTex, 2 pdf figures. Numerous corrections and improvements. For related work, see http://www.physics.emory.edu/faculty/boettcher/

The properties of the coinless quantum walk model have not been as thoroughly analyzed as those of the coined model. Both evolve in discrete time steps but the former uses a smaller Hilbert space, which is spanned merely by the site basis. Besides, the evolution operator can be obtained using a process of lattice tessellation, which is very appealing. The moments of the probability distribution play an important role in the context of quantum walks. The ballistic behavior of the mean square displacement indicates that quantum-walk-based algorithms are faster than random-walk-based ones. In this paper, we obtain analytical expressions for the moments of the coinless model on $d$-dimensional lattices. The mean square displacement for large times is explicitly calculated for the one- and two-dimensional lattices and, using optimization methods, the parameter values that give the largest spread are calculated and compared with the equivalent ones of the coined model. Although we have employed asymptotic methods, our approximations are accurate even for small numbers of time steps., Comment: 13 pages, 1 figure

Based on studies on four specific networks, we conjecture a general relation between the walk dimensions $d_{w}$ of discrete-time random walks and quantum walks with the (self-inverse) Grover coin. In each case, we find that $d_{w}$ of the quantum walk takes on exactly half the value found for the classical random walk on the same geometry. Since walks on homogeneous lattices satisfy this relation trivially, our results for heterogeneous networks suggests that such a relation holds irrespective of whether translational invariance is maintained or not. To develop our results, we extend the renormalization group analysis (RG) of the stochastic master equation to one with a unitary propagator. As in the classical case, the solution $\rho(x,t)$ in space and time of this quantum walk equation exhibits a scaling collapse for a variable $x^{d_{w}}/t$ in the weak limit, which defines $d_{w}$ and illuminates fundamental aspects of the walk dynamics, e.g., its mean-square displacement. We confirm the collapse for $\rho(x,t)$ in each case with extensive numerical simulation. The exact values for $d_{w}$ in themselves demonstrate that RG is a powerful complementary approach to study the asymptotics of quantum walks that weak-limit theorems have not been able to access, such as for systems lacking translational symmetries beyond simple trees., Comment: 8 pages, RevTex4-1; several corrections and upgrades; for related information, see http://www.physics.emory.edu/faculty/boettcher/

We analyze a semi-infinite one-dimensional random walk process with a biased motion that is incremental in one direction and long-range in the other. On a network with a fixed hierarchy of long-range jumps, we find with exact renormalization group calculations that there is a dynamical transition between a localized adsorption phase and an anomalous diffusion phase in which the mean-square displacement exponent depends non-universally on the Bernoulli coin. We relate these results to similar findings of unconventional phase behavior in hierarchical networks., Comment: 7 pages, RevTex4.1; for related information, see http://www.physics.emory.edu/faculty/boettcher/

We study the Biroli-Mezard model for lattice glasses on a number of hierarchical networks. These networks combine certain lattice-like features with a recursive structure that makes them suitable for exact renormalization group studies and provide an alternative to the mean-field approach. In our numerical simulations here, we first explore their equilibrium properties with the Wang-Landau algorithm. Then, we investigate their dynamical behavior using a grand-canonical annealing algorithm. We find that the dynamics readily falls out of equilibrium and jams in many of our networks with certain constraints on the neighborhood occupation imposed by the Biroli-Mezard model, even in cases where exact results indicate that no ideal glass transition exists. But while we find that time-scales for the jams diverge, our simulations cannot ascertain such a divergence for a packing fraction distinctly above random close packing. In cases where we allow hopping in our dynamical simulations, the jams on these networks generally disappear., Comment: 9 pages, several corrections. For related information, see http://www.physics.emory.edu/faculty/boettcher/

A coinless, discrete-time quantum walk possesses a Hilbert space whose dimension is smaller compared to the widely-studied coined walk. Coined walks require the direct product of the site basis with the coin space, coinless walks operate purely in the site basis, which is clearly minimal. These coinless quantum walks have received considerable attention recently because they have evolution operators that can be obtained by a graphical method based on lattice tessellations and they have been shown to be as efficient as the best known coined walks when used as a quantum search algorithm. We argue that both formulations in their most general form are equivalent. In particular, we demonstrate how to transform the one-dimensional version of the coinless quantum walk into an equivalent extended coined version for a specific family of evolution operators. We present some of its basic, asymptotic features for the one-dimensional lattice with some examples of tessellations, and analyze the mixing time and limiting probability distributions on cycles., Comment: 16 pages, 6 figs, added a reference

We analyze the phase transitions that emerge from the recursive design of certain hyperbolic networks that includes, for instance, a discontinuous ("explosive") transition in ordinary percolation. To this end, we solve the $q$-state Potts model in the analytic continuation for non-integer $q$ with the real-space renormalization group. We find exact expressions for this one-parameter family of models that describe the dramatic transformation of the transition. In particular, this variation in $q$ shows that the discontinuous transition is generic in the regime $q<2$ that includes percolation. A continuous ferromagnetic transition is recovered in a singular manner only for the Ising model, $q=2$. For $q>2$ the transition immediately transforms into an infinitely smooth order parameter of the Berezinskii-Kosterlitz-Thouless (BKT) type., Comment: 6 pages, 5 figures, http://www.physics.emory.edu/faculty/boettcher/

We revisit the one dimensional discrete time quantum walk with 3 states and the Grover coin. We derive analytic expressions for observed the localization, an long time approximation for the probability density function (PDF). We also connect the time averaged approximation to the PDF found by Inui et. al. to a spatial average of the walk. We show that this smooth approximation constitutes a proper PDF that predicts moments of the real PDF accurately., Comment: 8 pages, revtex, for related information see http://www.physics.emory.edu/faculty/boettcher/ v2: minor changes, references added

We investigate the onset of the discontinuous percolation transition in small-world hyperbolic networks by studying the systems-size scaling of the typical largest cluster approaching the transition, $p\nearrow p_{c}$. To this end, we determine the average size of the largest cluster $\left\langle s_{{\rm max}}\right\rangle \sim N^{\Psi\left(p\right)}$ in the thermodynamic limit using real-space renormalization of cluster generating functions for bond and site percolation in several models of hyperbolic networks that provide exact results. We determine that all our models conform to the recently predicted behavior regarding the growth of the largest cluster, which found diverging, albeit sub-extensive, clusters spanning the system with finite probability well below $p_{c}$ and at most quadratic corrections to unity in $\Psi\left(p\right)$ for $p\nearrow p_{c}$. Our study suggest a large universality in the cluster formation on small-world hyperbolic networks and the potential for an alternative mechanism in the cluster formation dynamics at the onset of discontinuous percolation transitions., Comment: Pages 12, For more information visit: http://www.physics.emory.edu/faculty/boettcher/

A coarse-grained model of dense hard sphere colloids building on simple notions of particle mobility and spatial coherence is presented and shown to reproduce results of experiments and simulations for key quantities such as the intermediate scattering function, the particle mean-square displacement and the $\chi_{4}$ mobility correlation function. All results are explained by two emerging and interrelated dynamical properties: i) a rate of intermittent events, quakes, which decreases as the inverse of the system age t; ii) a length scale characterizing correlated domains, which increases linearly in log t. This leads to simple and accurate scaling forms expressed in terms of a single scaling variable Finally, we propose a method to experimentally extract the growing length scale of an aging colloid and suggest that a suitable scaling of the probability density function of particle displacement can experimentally reveal the rate of quakes., Comment: 5 pages 6 figures

In contrast to XML query languages as e.g. XPath which require knowledge on the query language as well as on the document structure, keyword search is open to anybody. As the size of XML sources grows rapidly, the need for efficient search indices on XML data that support keyword search increases. In this paper, we present an approach of XML keyword search which is based on the DAG of the XML data, where repeated substructures are considered only once, and therefore, have to be searched only once. As our performance evaluation shows, this DAG-based extension of the set intersection search algorithm[1], [2], can lead to search times that are on large documents more than twice as fast as the search times of the XML-based approach. Additionally, we utilize a smaller index, i.e., we consume less main memory to compute the results.

The paper by Bowen, Mancini, Fessatidis, and Murawski (2012 Phys. Scr. {\bf 85}, 065005) demonstrates in a dramatic fashion the serious difficulties that can arise when one rushes to perform numerical studies before understanding the physics and mathematics of the problem at hand and without understanding the limitations of the numerical methods used. Based on their flawed numerical work, the authors conclude that the work of Bender and Boettcher is wrong even though it has been verified at a completely rigorous level. Unfortunately, the numerical procedures performed and described in the paper by Bowen et al are incorrectly applied and wrongly interpreted., Comment: Two pages, no figures. This manuscript was submitted and received by Physica Scripta on September 8, 2012