Mathematical discoveries from program search with large language models.

Large language models (LLMs) have demonstrated tremendous capabilities in solving complex tasks, from quantitative reasoning to understanding natural language. However, LLMs sometimes suffer from confabulations (or hallucinations), which can result in them making plausible but incorrect statements1,2. This hinders the use of current large models in scientific discovery. Here we introduce FunSearch (short for searching in the function space), an evolutionary procedure based on pairing a pretrained LLM with a systematic evaluator. We demonstrate the effectiveness of this approach to surpass the best-known results in important problems, pushing the boundary of existing LLM-based approaches3. Applying FunSearch to a central problem in extremal combinatorics-the cap set problem-we discover new constructions of large cap sets going beyond the best-known ones, both in finite dimensional and asymptotic cases. This shows that it is possible to make discoveries for established open problems using LLMs. We showcase the generality of FunSearch by applying it to an algorithmic problem, online bin packing, finding new heuristics that improve on widely used baselines. In contrast to most computer search approaches, FunSearch searches for programs that describe how to solve a problem, rather than what the solution is. Beyond being an effective and scalable strategy, discovered programs tend to be more interpretable than raw solutions, enabling feedback loops between domain experts and FunSearch, and the deployment of such programs in real-world applications.

Metabolomic profiling of bacterial biofilm: trends, challenges, and an emerging antibiofilm target.

Biofilm-related infections substantially contribute to bacterial illnesses, with estimates indicating that at least 80% of such diseases are linked to biofilms. Biofilms exhibit unique metabolic patterns that set them apart from their planktonic counterparts, resulting in significant metabolic reprogramming during biofilm formation. Differential glycolytic enzymes suggest that central metabolic processes are markedly different in biofilms and planktonic cells. The glycolytic enzyme glyceraldehyde-3-phosphate dehydrogenase (GAPDH) is highly expressed in Staphylococcus aureus biofilm progenitors, indicating that changes in glycolysis activity play a role in biofilm development. Notably, an important consideration is a correlation between elevated cyclic di-guanylate monophosphate (c-di-GMP) activity and biofilm formation in various bacteria. C-di-GMP plays a critical role in maintaining the persistence of Pseudomonas aeruginosa biofilms by regulating alginate production, a significant biofilm matrix component. Furthermore, it has been demonstrated that S. aureus biofilm development is initiated by several tricarboxylic acid (TCA) intermediates in a FnbA-dependent manner. Finally, Glucose 6-phosphatase (G6P) boosts the phosphorylation of histidine-containing protein (HPr) by increasing the activity of HPr kinase, enhancing its interaction with CcpA, and resulting in biofilm development through polysaccharide intercellular adhesion (PIA) accumulation and icaADBC transcription. Therefore, studying the metabolic changes associated with biofilm development is crucial for understanding the complex mechanisms involved in biofilm formation and identifying potential targets for intervention. Accordingly, this review aims to provide a comprehensive overview of recent advances in metabolomic profiling of biofilms, including emerging trends, prevailing challenges, and the identification of potential targets for anti-biofilm strategies.

Chain Rule for the Quantum Relative Entropy.

The chain rule for the classical relative entropy ensures that the relative entropy between probability distributions on multipartite systems can be decomposed into a sum of relative entropies of suitably chosen conditional distributions on the individual systems. Here, we prove a chain rule inequality for the quantum relative entropy. The new chain rule allows us to solve an open problem in the context of asymptotic quantum channel discrimination: surprisingly, adaptive protocols cannot improve the error rate for asymmetric channel discrimination compared to nonadaptive strategies.

Computing conditional entropies for quantum correlations.

The rates of quantum cryptographic protocols are usually expressed in terms of a conditional entropy minimized over a certain set of quantum states. In particular, in the device-independent setting, the minimization is over all the quantum states jointly held by the adversary and the parties that are consistent with the statistics that are seen by the parties. Here, we introduce a method to approximate such entropic quantities. Applied to the setting of device-independent randomness generation and quantum key distribution, we obtain improvements on protocol rates in various settings. In particular, we find new upper bounds on the minimal global detection efficiency required to perform device-independent quantum key distribution without additional preprocessing. Furthermore, we show that our construction can be readily combined with the entropy accumulation theorem in order to establish full finite-key security proofs for these protocols.

Practical device-independent quantum cryptography via entropy accumulation.

Device-independent cryptography goes beyond conventional quantum cryptography by providing security that holds independently of the quality of the underlying physical devices. Device-independent protocols are based on the quantum phenomena of non-locality and the violation of Bell inequalities. This high level of security could so far only be established under conditions which are not achievable experimentally. Here we present a property of entropy, termed "entropy accumulation", which asserts that the total amount of entropy of a large system is the sum of its parts. We use this property to prove the security of cryptographic protocols, including device-independent quantum key distribution, while achieving essentially optimal parameters. Recent experimental progress, which enabled loophole-free Bell tests, suggests that the achieved parameters are technologically accessible. Our work hence provides the theoretical groundwork for experimental demonstrations of device-independent cryptography.

Universal recovery map for approximate Markov chains.

A central question in quantum information theory is to determine how well lost information can be reconstructed. Crucially, the corresponding recovery operation should perform well without knowing the information to be reconstructed. In this work, we show that the quantum conditional mutual information measures the performance of such recovery operations. More precisely, we prove that the conditional mutual information I(A:C|B) of a tripartite quantum state ρABC can be bounded from below by its distance to the closest recovered state [Formula: see text], where the C-part is reconstructed from the B-part only and the recovery map [Formula: see text] merely depends on ρBC . One particular application of this result implies the equivalence between two different approaches to define topological order in quantum systems.