Results 431 - 440 of 24335

We present a method of integrating low-energy assumptions into a variety of quantum algorithms for physical simulation that leverages Hamiltonians represented as a sum of squares and spectral amplification. Spectral amplification minimizes query costs by useful uncertainty propagation when performing a parameter estimation task if the initial state is in the low-energy sector of a non-negative Hamiltonian. The non-negative Hamiltonian representations we utilize are sum-of-squares certificates on the lowest eigenvalue. This work connects non-commutative polynomial optimization to quantum algorithms and is demonstrated to lower quantum gate complexities when computing the ground state of strongly correlated electronic systems in first and second quantization. We will also highlight how sum-of-squares Hamiltonian representations can be used in classical electronic structure simulation with potentially reduced costs.

Modern algorithms increasingly rely on data to make decisions, but acquiring data can itself be costly. In this talk, we consider a class of selection problems with stochastic inputs, where an algorithm may learn about each input random variable only through a sequence of costly actions. The goal is to determine what information to acquire before optimizing the downstream objective. This framework generalizes the classical Pandora’s Box problem.

I will describe new results that connect costly-information optimization to well-studied models in stochastic online selection, including prophet inequalities and the query-commit model. This talk is based on joint work with Dimitris Christou and Trung Dang.

A major problem in the study of large language models is to understand their inherent low-dimensional structure. We introduce an approach to study the low-dimensional structure of language models at a model-agnostic level: as sequential probabilistic models. We first empirically demonstrate that a wide range of modern language models exhibit low-rank structure: in particular, matrices built from the model’s logits for varying sets of prompts and responses have low approximate rank. Taking a theoretical perspective, we then show that any distribution over sequences with such structure of low approximate logit rank can be provably learned using polynomially many queries to the model's logits and polynomial time. Finally, we show that insights resulting from this perspective of low-rank can be leveraged for generation— for instance, we can generate a response to a target prompt using a linear combination of the model’s outputs on unrelated, or even nonsensical prompts. Further, we show how such insights can explain phenomena observed in fine-tuning of LLMs, namely those relating to subliminal learning.

While quantum chemistry is widely considered a leading application for quantum computing, the standard task of ground-state energy estimation is not the only approach with a potential quantum speed-up. Simulating spectroscopy of molecules and materials offers a tractable and industrially relevant computational task. This talk presents a generalized quantum algorithm for simulating momentum- resolved spectroscopies, including EELS, XAS, and more, based on computing the time-domain Green's function. We highlight critical algorithmic optimizations in Hamiltonian representation and efficient classical-to-quantum state preparation that significantly reduce logical overhead. Finally, we share logical resource estimations for prototypical complex materials, demonstrating the utility of quantum spectroscopy as a key application for fault-tolerant quantum computers.

Simulations of chemical dynamics are a powerful means for understanding chemistry. However, classical computers struggle to simulate many chemical processes, especially non-adiabatic ones, where the Born-Oppenheimer approximation breaks down. Quantum computers could simulate quantum-chemical dynamics more efficiently than classical computers, but there is currently no complete quantum algorithm for calculating dynamical observables to within a known error. Here, we develop an efficient, end-to-end quantum algorithm for simulating chemical dynamics that avoids all uncontrolled approximations (including the Born-Oppenheimer approximation) and whose error is bounded subject to mild assumptions. To do so, we treat the nuclei and the electrons on an equal footing and simulate the full molecular wavefunction on a momentum-space grid in first quantization, including all algorithmic steps: initial-state preparation, time evolution using qubitization, and measurement of chemical observables such as reaction yields and rates. Our work gives the first algorithm for quantum simulation of chemistry whose end-to-end complexity achieves sublinear scaling in the size of the grid. We achieve this by developing an exponentially faster method for initial-state-preparation. Photochemistry is a likely early application of our algorithm and we estimate resources required for end-to-end simulations of non-adiabatic dynamics of atmospherically important molecules. Classically intractable photochemical computations could be performed using resources comparable to those required for other chemical applications of quantum computing.

Large language models (LLMs) are increasingly deployed on complex tasks that require multi-step decision-making, making it crucial to understand their algorithmic reasoning abilities. However, existing benchmarks do not provide fine-grained diagnostics for evaluating these capabilities. We propose to use data structures as a principled lens: as fundamental building blocks of algorithms, they naturally probe structural reasoning—the ability to understand and manipulate relationships such as order, hierarchy, connectivity, and composition. We introduce the Data Structure Reasoning Benchmark (DSR-Bench), which spans 20 data structures, 35 operations, and 4,140 problem instances. DSR-Bench supports fully automated generation and evaluation, and enables fine-grained diagnosis of where structural reasoning breaks down. Evaluating 13 state-of-the-art LLMs reveals critical limitations: failures emerge under compositional and multi-hop reasoning, length scaling, user-specified constraints, spatial distribution shift, and natural-language framing.

This talk describes joint work with Yu He, Yingxi Li, and Colin White.