Comparison between a quantum annealer and a classical approximation algorithm for computing the ground state of an Ising spin glass.

Finding the ground state of an Ising spin glass on general graphs belongs to the class of NP-hard problems, widely believed to have no efficient polynomial-time algorithms to solve them. An approach developed in computer science for dealing with such problems is to devise approximation algorithms; these are algorithms, whose run time scales polynomially with the input size, that provide solutions with provable guarantees on their quality in terms of the optimal unknown solution. Recently, several algorithms for the Ising spin-glass problem on a bounded degree graph that provide different approximation guarantees were introduced. D-Wave, a Canadian-based company, has constructed a physical realization of a quantum annealer and has enabled researchers and practitioners to access it via their cloud service. D-Wave is particularly suited for computing an approximation for the ground state of an Ising spin glass on its Chimera and Pegasus graphs-both with a bounded degree. To assess the quality of D-Wave's solution, it is natural to compare it to classical approximation algorithms specifically designed to solve the same problem. In this work, we compare the performance of a recently developed approximation algorithm to solve the Ising spin-glass problem on graphs of bounded degree against the performance of the D-Wave computer. We also compared the performance of D-Wave's computer in the Chimera architecture against the performance of a heuristic tailored specifically to handle the Chimera graph. We found that the D-Wave computer was able to find better approximations for all the random instances of the problem we studied-Gaussian weights, uniform weights, and discrete binary weights. Furthermore, the convergence times of D-Wave's computer were also significantly better. These results indicate the merit of D-Wave's computer under certain specific instances. More broadly, our method is relevant to a wider class of performance comparison studies, and we suggest that it is important to compare the performance of quantum computers not only against exact classical algorithms with exponential run-time scaling, but also against approximation algorithms with polynomial run-time scaling and a provable guarantee of performance.

A unifying autocatalytic network-based framework for bacterial growth laws.

Recently discovered simple quantitative relations, known as bacterial growth laws, hint at the existence of simple underlying principles at the heart of bacterial growth. In this work, we provide a unifying picture of how these known relations, as well as relations that we derive, stem from a universal autocatalytic network common to all bacteria, facilitating balanced exponential growth of individual cells. We show that the core of the cellular autocatalytic network is the transcription-translation machinery-in itself an autocatalytic network comprising several coupled autocatalytic cycles, including the ribosome, RNA polymerase, and transfer RNA (tRNA) charging cycles. We derive two types of growth laws per autocatalytic cycle, one relating growth rate to the relative fraction of the catalyst and its catalysis rate and the other relating growth rate to all the time scales in the cycle. The structure of the autocatalytic network generates numerous regimes in state space, determined by the limiting components, while the number of growth laws can be much smaller. We also derive a growth law that accounts for the RNA polymerase autocatalytic cycle, which we use to explain how growth rate depends on the inducible expression of the rpoB and rpoC genes, which code for the RpoB and C protein subunits of RNA polymerase, and how the concentration of rifampicin, which targets RNA polymerase, affects growth rate without changing the RNA-to-protein ratio. We derive growth laws for tRNA synthesis and charging and predict how growth rate depends on temperature, perturbation to ribosome assembly, and membrane synthesis.

Lorentzian-geometry-based analysis of airplane boarding policies highlights "slow passengers first" as better.

We study airplane boarding in the limit of a large number of passengers using geometric optics in a Lorentzian metric. The airplane boarding problem is naturally embedded in a (1+1)-dimensional space-time with a flat Lorentzian metric. The duration of the boarding process can be calculated based on a representation of the one-dimensional queue of passengers attempting to reach their seats in a two-dimensional space-time diagram. The ability of a passenger to delay other passengers depends on their queue positions and row designations. This is equivalent to the causal relationship between two events in space-time, whereas two passengers are timelike separated if one is blocking the other and spacelike if both can be seated simultaneously. Geodesics in this geometry can be utilized to compute the asymptotic boarding time, since space-time geometry is the many-particle (passengers) limit of airplane boarding. Our approach naturally leads to the introduction of an effective refractive index that enables an analytical calculation of the average boarding time for groups of passengers with different aisle-clearing time distribution. In the past, airline companies attempted to shorten the boarding times by trying boarding policies that allow either slow or fast passengers to board first. Our analytical calculations, backed by discrete-event simulations, support the counterintuitive result that the total boarding time is shorter with the slow passengers boarding before the fast passengers. This is a universal result, valid for any combination of the parameters that characterize the problem: the percentage of slow passengers, the ratio between aisle-clearing times of the fast and the slow group, and the density of passengers along the aisle. We find an improvement of up to 28% compared with the fast-first boarding policy. Our approach opens up the possibility to unify numerous simulation-based case studies under one framework.

Fundamental principles in bacterial physiology-history, recent progress, and the future with focus on cell size control: a review.

Bacterial physiology is a branch of biology that aims to understand overarching principles of cellular reproduction. Many important issues in bacterial physiology are inherently quantitative, and major contributors to the field have often brought together tools and ways of thinking from multiple disciplines. This article presents a comprehensive overview of major ideas and approaches developed since the early 20th century for anyone who is interested in the fundamental problems in bacterial physiology. This article is divided into two parts. In the first part (sections 1-3), we review the first 'golden era' of bacterial physiology from the 1940s to early 1970s and provide a complete list of major references from that period. In the second part (sections 4-7), we explain how the pioneering work from the first golden era has influenced various rediscoveries of general quantitative principles and significant further development in modern bacterial physiology. Specifically, section 4 presents the history and current progress of the 'adder' principle of cell size homeostasis. Section 5 discusses the implications of coarse-graining the cellular protein composition, and how the coarse-grained proteome 'sectors' re-balance under different growth conditions. Section 6 focuses on physiological invariants, and explains how they are the key to understanding the coordination between growth and the cell cycle underlying cell size control in steady-state growth. Section 7 overviews how the temporal organization of all the internal processes enables balanced growth. In the final section 8, we conclude by discussing the remaining challenges for the future in the field.

Greedy scheduling of cellular self-replication leads to optimal doubling times with a log-Frechet distribution.

Bacterial self-replication is a complex process composed of many de novo synthesis steps catalyzed by a myriad of molecular processing units, e.g., the transcription-translation machinery, metabolic enzymes, and the replisome. Successful completion of all production tasks requires a schedule-a temporal assignment of each of the production tasks to its respective processing units that respects ordering and resource constraints. Most intracellular growth processes are well characterized. However, the manner in which they are coordinated under the control of a scheduling policy is not well understood. When fast replication is favored, a schedule that minimizes the completion time is desirable. However, if resources are scarce, it is typically computationally hard to find such a schedule, in the worst case. Here, we show that optimal scheduling naturally emerges in cellular self-replication. Optimal doubling time is obtained by maintaining a sufficiently large inventory of intermediate metabolites and processing units required for self-replication and additionally requiring that these processing units be "greedy," i.e., not idle if they can perform a production task. We calculate the distribution of doubling times of such optimally scheduled self-replicating factories, and find it has a universal form-log-Frechet, not sensitive to many microscopic details. Analyzing two recent datasets of Escherichia coli growing in a stationary medium, we find excellent agreement between the observed doubling-time distribution and the predicted universal distribution, suggesting E. coli is optimally scheduling its replication. Greedy scheduling appears as a simple generic route to optimal scheduling when speed is the optimization criterion. Other criteria such as efficiency require more elaborate scheduling policies and tighter regulation.

Phase-locking-level statistics of coupled random fiber lasers.

We measure the statistics of phase locking levels of coupled fiber lasers with fluctuating cavity lengths. We found that the measured distribution of the phase locking level of such coupled lasers can be described by the generalized extreme value distribution. For large number of lasers the distribution of the phase locking level can be approximated by a Gumbel distribution. We present a simple model, based on the spectral response of coupled lasers, and the calculated results are in good agreement with the experimental results.

Measuring maximal eigenvalue distribution of Wishart random matrices with coupled lasers.

We determined the probability distribution of the combined output power from 25 coupled fiber lasers and show that it agrees well with the Tracy-Widom and Majumdar-Vergassola distributions of the largest eigenvalue of Wishart random matrices with no fitting parameters. This was achieved with 500,000 measurements of the combined output power from the fiber lasers, that continuously changes with variations of the fiber lasers lengths. We show experimentally that for small deviations of the combined output power over its mean value the Tracy-Widom distribution is correct, while for large deviations the Majumdar-Vergassola distribution is correct.

Perfect imaging through a disordered waveguide lattice.

It is experimentally demonstrated that perfect imaging is possible in disordered wave guiding media, provided that the disorder is off-diagonal, i.e., that only the spacing varies randomly between the otherwise identical lattice sites. On-diagonal disorder or Kerr nonlinearity destroys the imaging.

Spectrum of two-level systems with discrete frequency fluctuations.

We study, theoretically and experimentally, an ensemble of two-level systems coupled to an environment which induces random jumps in their resonant frequency. We present a closed-form formula for the spectrum in terms of the resonant frequency distribution and the Poisson rate constant. For a normal distribution the spectrum deviates from a generalized Gumbel function, a well-known result for continuous stochastic Gaussian processes. We perform experiments with optically trapped cold 87Rb atoms and show that the predictions of our theory for a 3D harmonic trap match the measured spectra without fitting parameters.