Search

The temperature of a bosonic/fermionic environment can be measured by coupling a fully characterised $N$-dimensional probe to it. While prepare-measure-reset strategies offer optimal thermometry precision, they overlook the required time for the preparation and reset, and require excessive control of the probe at all times. Continuously monitored probes are more practical in this sense, as they take into account finite-time limitations. Thus, we study the ultimate limits and the optimal structure of continuously monitored $N$-dimensional thermometers. With the local estimation scheme our figure of merit is the Fisher information, which inversely bounds the mean square error. We provide an optimal strategy for both fermionic and bosonic environments. Under reasonable assumptions it turns out that the optimal thermometer is an effective two-level system, with a degeneracy of the ground state that increases with $N$ -- contrary to the optimal thermometers at equilibrium that have a single ground state degeneracy. The optimal gap also differs from the equilibrium case, as it depends on the bath type (fermionic/bosonic) and the specific spectral density. For $N\gg 1$, the Fisher information can grow linearly with $N$ regardless of bath type, significantly improving the well-known $\log^2 N$ scaling for equilibrium thermometry. Another remarkable observation is that the scaling with $N$ does not vanish in presence of prior ignorance, i.e., in a Bayesian setup even non-adaptive strategies can lead to an estimation error that scales with $1/N$. In comparison, a no-go theorem prohibits the ultimate equilibrium scaling $1/\log^2 N$ without adaptive strategies., Comment: Any feedback/comments are very wellcome

Physical devices operating out of equilibrium are inherently affected by thermal fluctuations, limiting their operational precision. This issue is pronounced at microscopic and especially quantum scales and can only be mitigated by incurring additional entropy dissipation. Understanding this constraint is crucial for both fundamental physics and technological design. For instance, clocks are inherently governed by the second law of thermodynamics and need a thermodynamic flux towards equilibrium to measure time, which results in a minimum entropy dissipation per clock tick. Classical and quantum models and experiments often show a linear relationship between precision and dissipation, but the ultimate bounds on this relationship are unknown. Our theoretical discovery presents an extensible quantum many-body system that achieves clock precision scaling exponentially with entropy dissipation. This finding demonstrates that coherent quantum dynamics can surpass the traditional thermodynamic precision limits, potentially guiding the development of future high-precision, low-dissipation quantum devices., Comment: 6 + 14 pages, 9 figures, comments welcome

Time estimation is a fundamental task that underpins precision measurement, global navigation systems, financial markets, and the organisation of everyday life. Many biological processes also depend on time estimation by nanoscale clocks, whose performance can be significantly impacted by random fluctuations. In this work, we formulate the problem of optimal time estimation for Markovian stochastic processes, and present its general solution in the asymptotic (long-time) limit. Specifically, we obtain a tight upper bound on the precision of any time estimate constructed from sustained observations of a classical, Markovian jump process. This bound is controlled by the mean residual time, i.e. the expected wait before the first jump is observed. As a consequence, we obtain a universal bound on the signal-to-noise ratio of arbitrary currents and counting observables in the steady state. This bound is similar in spirit to the kinetic uncertainty relation but provably tighter, and we explicitly construct the counting observables that saturate it. Our results establish ultimate precision limits for an important class of observables in non-equilibrium systems, and demonstrate that the mean residual time, not the dynamical activity, is the measure of freneticity that tightly constrains fluctuations far from equilibrium., Comment: 13+16 pages, 9 figures. Comments welcome!

The second law of thermodynamics states that the entropy of an isolated system can only increase over time. This appears to conflict with the reversible evolution of isolated quantum systems under the Schr\"odinger equation, which preserves the von Neumann entropy. Nonetheless, one finds that with respect to many observables, expectation values approach a fixed value -- their equilibrium value. This ultimately raises the question: in what sense does the entropy of an isolated quantum system increase over time? For classical systems, one introduces the assumption of a low entropy initial state along with the concept of ignorance about the microscopic details of the physical system, leading to a statistical interpretation of the second law. By considering the observables through which we examine quantum systems, both these assumptions can be incorporated, building upon recent studies of the equilibration on average of observables. While the statistical behavior of observable expectation values is well-established, a quantitative connection to entropy increase has been lacking so far. In deriving novel bounds for the equilibration of observables, and considering the entropy of the system relative to observables, we recover a variant of the second law: the entropy with respect to a given observable tends towards its equilibrium value in the course of the system's unitary evolution. These results also support recent findings which question the necessity of non-integrability for equilibration in quantum systems. We further illustrate our bounds using numerical results from the paradigmatic example of a quantum Ising model on a chain of spins. There, we observe entropy increasing up to equilibrium values, as well as fluctuations which expose the underlying reversible evolution in accordance with the derived bounds., Comment: 7+10 pages; 3 figures; update: clarifications OE, Lemma 3; comments welcome

Computation is an input-output process, where a program encoding a problem to be solved is inserted into a machine that outputs a solution. Whilst a formalism for quantum Turing machines which lifts this input-output feature into the quantum domain has been developed, this is not how quantum computation is physically conceived. Usually, such a quantum computation is enacted by the manipulation of macroscopic control interactions according to a program executed by a classical system. To understand the fundamental limits of computation, especially in relation to the resources required, it is pivotal to work with a fully self-contained description of a quantum computation where computational and thermodynamic resources are not be obscured by the classical control. To this end, we answer the question; "Can we build a physical model for quantum computation that is fully autonomous?", i.e., where the program to be executed as well as the control are both quantum. We do so by developing a framework that we dub the autonomous Quantum Processing Unit (aQPU). This machine, consisting of a timekeeping mechanism, instruction register and computational system allows an agent to input their problem and receive the solution as an output, autonomously. Using the theory of open quantum systems and results from the field of quantum clocks we are able to use the aQPU as a formalism to investigate relationships between the thermodynamics, complexity, speed and fidelity of a desired quantum computation., Comment: 21 + 18 pages, 1 table, 6 figures. Comments welcome

Energy consumption in solving computational problems has been gaining growing attention as a part of the performance measures of computers. Quantum computation is known to offer advantages over classical computation in terms of various computational resources; however, its advantage in energy consumption has been challenging to analyze due to the lack of a theoretical foundation to relate the physical notion of energy and the computer-scientific notion of complexity for quantum computation with finite computational resources. To bridge this gap, we introduce a general framework for studying the energy consumption of quantum and classical computation based on a computational model that has been conventionally used for studying query complexity in computational complexity theory. With this framework, we derive an upper bound for the achievable energy consumption of quantum computation. We also develop techniques for proving a nonzero lower bound of energy consumption of classical computation based on the energy-conservation law and Landauer's principle. With these general bounds, we rigorously prove that quantum computation achieves an exponential energy-consumption advantage over classical computation for solving a specific computational problem, Simon's problem. Furthermore, we clarify how to demonstrate this energy-consumption advantage of quantum computation in an experimental setting. These results provide a fundamental framework and techniques to explore the physical meaning of quantum advantage in the query-complexity setting based on energy consumption, opening an alternative way to study the advantages of quantum computation., Comment: 46 pages, 4 figures

In order to unitarily evolve a quantum system, an agent requires knowledge of time, a parameter which no physical clock can ever perfectly characterise. In this letter, we study how limitations on acquiring knowledge of time impact controlled quantum operations in different paradigms. We show that the quality of timekeeping an agent has access to limits the circuit complexity they are able to achieve within circuit-based quantum computation. We do this by deriving an upper bound on the average gate fidelity achievable under imperfect timekeeping for a general class of random circuits. Another area where quantum control is relevant is quantum thermodynamics. In that context, we show that cooling a qubit can be achieved using a timer of arbitrary quality for control: timekeeping error only impacts the rate of cooling and not the achievable temperature. Our analysis combines techniques from the study of autonomous quantum clocks and the theory of quantum channels to understand the effect of imperfect timekeeping on controlled quantum dynamics., Comment: V3 5 + 8 pages, Published version

From a thermodynamic point of view, all clocks are driven by irreversible processes. Additionally, one can use oscillatory systems to temporally modulate the thermodynamic flux towards equilibrium. Focusing on the most elementary thermalization events, this modulation can be thought of as a temporal probability concentration for these events. There are two fundamental factors limiting the performance of clocks: On the one level, the inevitable drifts of the oscillatory system, which are addressed by finding stable atomic or nuclear transitions that lead to astounding precision of today's clocks. On the other level, there is the intrinsically stochastic nature of the irreversible events upon which the clock's operation is based. This becomes relevant when seeking to maximize a clock's resolution at high accuracy, which is ultimately limited by the number of such stochastic events per reference time unit. We address this essential trade-off between clock accuracy and resolution, proving a universal bound for all clocks whose elementary thermalization events are memoryless., Comment: 5 + 5 pages, 8 figures

Recent research has shown how strongly Wikipedia and other web services or platforms are connected. For example, search engines rely heavily on surfacing Wikipedia links to satisfy their users' information needs and volunteer-created Wikipedia content frequently gets re-used on other social media platforms like Reddit. However, publicly accessible datasets that enable researchers to study the interrelationship between Wikipedia and other platforms are sparse. In addition to that, most studies only focus on certain points in time and don't consider the historical perspective. To begin solving these problems we developed TWikiL, the Twitter Wikipedia Link Dataset, which contains all Wikipedia links posted on Twitter in the period 2006 to January 2021. We extract Wikipedia links from Tweets and enrich the referenced articles with their respective Wikidata identifiers and Wikipedia topic categories, which will make this dataset immediately useful for a large range of scholarly use cases. In this paper, we describe the data collection process, perform an initial exploratory analysis and present a comprehensive overview of how this dataset can be useful for the research community.

We consider two bottlenecks in quantum computing: limited memory size and noise caused by heat dissipation. Trying to optimize both, we investigate "on-the-go erasure" of quantum registers that are no longer needed for a given algorithm: freeing up auxiliary qubits as they stop being useful would facilitate the parallelization of computations. We study the minimal thermodynamic cost of erasure in these scenarios, applying results on the Landauer erasure of entangled quantum registers. For the class of algorithms solving the Abelian hidden subgroup problem, we find optimal on-the-go erasure protocols. We conclude that there is a trade-off: if we have enough partial information about a problem to build efficient on-the-go erasure, we can use it to instead simplify the algorithm, so that fewer qubits are needed to run the computation in the first place. We provide explicit protocols for these two approaches., Comment: 10+9 pages, 12 figures

Evolutionary Strategies (ES) are known to be an effective black-box optimization technique for deep neural networks when the true gradients cannot be computed, such as in Reinforcement Learning. We continue a recent line of research that uses surrogate gradients to improve the gradient estimation of ES. We propose a novel method to optimally incorporate surrogate gradient information. Our approach, unlike previous work, needs no information about the quality of the surrogate gradients and is always guaranteed to find a descent direction that is better than the surrogate gradient. This allows to iteratively use the previous gradient estimate as surrogate gradient for the current search point. We theoretically prove that this yields fast convergence to the true gradient for linear functions and show under simplifying assumptions that it significantly improves gradient estimates for general functions. Finally, we evaluate our approach empirically on MNIST and reinforcement learning tasks and show that it considerably improves the gradient estimation of ES at no extra computational cost.

We study unbiased $(1+1)$ evolutionary algorithms on linear functions with an unknown number $n$ of bits with non-zero weight. Static algorithms achieve an optimal runtime of $O(n (\ln n)^{2+\epsilon})$, however, it remained unclear whether more dynamic parameter policies could yield better runtime guarantees. We consider two setups: one where the mutation rate follows a fixed schedule, and one where it may be adapted depending on the history of the run. For the first setup, we give a schedule that achieves a runtime of $(1\pm o(1))\beta n \ln n$, where $\beta \approx 3.552$, which is an asymptotic improvement over the runtime of the static setup. Moreover, we show that no schedule admits a better runtime guarantee and that the optimal schedule is essentially unique. For the second setup, we show that the runtime can be further improved to $(1\pm o(1)) e n \ln n$, which matches the performance of algorithms that know $n$ in advance. Finally, we study the related model of initial segment uncertainty with static position-dependent mutation rates, and derive asymptotically optimal lower bounds. This answers a question by Doerr, Doerr, and K\"otzing.

Despite all the impressive advances of recurrent neural networks, sequential data is still in need of better modelling. Truncated backpropagation through time (TBPTT), the learning algorithm most widely used in practice, suffers from the truncation bias, which drastically limits its ability to learn long-term dependencies.The Real-Time Recurrent Learning algorithm (RTRL) addresses this issue, but its high computational requirements make it infeasible in practice. The Unbiased Online Recurrent Optimization algorithm (UORO) approximates RTRL with a smaller runtime and memory cost, but with the disadvantage of obtaining noisy gradients that also limit its practical applicability. In this paper we propose the Kronecker Factored RTRL (KF-RTRL) algorithm that uses a Kronecker product decomposition to approximate the gradients for a large class of RNNs. We show that KF-RTRL is an unbiased and memory efficient online learning algorithm. Our theoretical analysis shows that, under reasonable assumptions, the noise introduced by our algorithm is not only stable over time but also asymptotically much smaller than the one of the UORO algorithm. We also confirm these theoretical results experimentally. Further, we show empirically that the KF-RTRL algorithm captures long-term dependencies and almost matches the performance of TBPTT on real world tasks by training Recurrent Highway Networks on a synthetic string memorization task and on the Penn TreeBank task, respectively. These results indicate that RTRL based approaches might be a promising future alternative to TBPTT.

We study the entanglement game, which is a version of cops and robbers, on sparse graphs. While the minimum degree of a graph G is a lower bound for the number of cops needed to catch a robber in G, we show that the required number of cops can be much larger, even for graphs with small maximum degree. In particular, we show that there are 3-regular graphs where a linear number of cops are needed.

Processing sequential data of variable length is a major challenge in a wide range of applications, such as speech recognition, language modeling, generative image modeling and machine translation. Here, we address this challenge by proposing a novel recurrent neural network (RNN) architecture, the Fast-Slow RNN (FS-RNN). The FS-RNN incorporates the strengths of both multiscale RNNs and deep transition RNNs as it processes sequential data on different timescales and learns complex transition functions from one time step to the next. We evaluate the FS-RNN on two character level language modeling data sets, Penn Treebank and Hutter Prize Wikipedia, where we improve state of the art results to $1.19$ and $1.25$ bits-per-character (BPC), respectively. In addition, an ensemble of two FS-RNNs achieves $1.20$ BPC on Hutter Prize Wikipedia outperforming the best known compression algorithm with respect to the BPC measure. We also present an empirical investigation of the learning and network dynamics of the FS-RNN, which explains the improved performance compared to other RNN architectures. Our approach is general as any kind of RNN cell is a possible building block for the FS-RNN architecture, and thus can be flexibly applied to different tasks., Comment: Corrected minor typos in Figure 1 and Zoneout citation

We study the Moran process as adapted by Lieberman, Hauert and Nowak. This is a model of an evolving population on a graph or digraph where certain individuals, called "mutants" have fitness r and other individuals, called non-mutants have fitness 1. We focus on the situation where the mutation is advantageous, in the sense that r>1. A family of digraphs is said to be strongly amplifying if the extinction probability tends to 0 when the Moran process is run on digraphs in this family. The most-amplifying known family of digraphs is the family of megastars of Galanis et al. We show that this family is optimal, up to logarithmic factors, since every strongly-connected n-vertex digraph has extinction probability Omega(n^(-1/2)). Next, we show that there is an infinite family of undirected graphs, called dense incubators, whose extinction probability is O(n^(-1/3)). We show that this is optimal, up to constant factors. Finally, we introduce sparse incubators, for varying edge density, and show that the extinction probability of these graphs is O(n/m), where m is the number of edges. Again, we show that this is optimal, up to constant factors.