Search for: All records

Diffusion models (DMs) create samples from a data distribution by starting from random noise and iteratively solving a reverse-time ordinary differential equation (ODE). Because each step in the iterative solution requires an expensive neural function evaluation (NFE), there has been significant interest in approximately solving these diffusion ODEs with only a few NFEs without modifying the underlying model. However, in the few NFE regime, we observe that tracking the true ODE evolution is fundamentally impossible using traditional ODE solvers. In this work, we propose a new method that learns a good solver for the DM, which we call Solving for the Solver (S4S). S4S directly optimizes a solver to obtain good generation quality by learning to match the output of a strong teacher solver. We evaluate S4S on six different pre-trained DMs, including pixel-space and latent-space DMs for both conditional and unconditional sampling. In all settings, S4S uniformly improves the sample quality relative to traditional ODE solvers. Moreover, our method is lightweight, data-free, and can be plugged in black-box on top of any discretization schedule or architecture to improve performance. Building on top of this, we also propose S4S-Alt, which optimizes both the solver and the discretization schedule. By exploiting the full design space of DM solvers, with 5 NFEs, we achieve an FID of 3.73 on CIFAR10 and 13.26 on MS-COCO, representing a 1.5x improvement over previous training-free ODE methods. 

We investigate the problem of predicting the output behavior of unknown quantum channels. Given query access to an -qubit channel and an observable , we aim to learn the mapping to within a small error for most sampled from a distribution . Previously, Huang, Chen, and Preskill proved a surprising result that even if is arbitrary, this task can be solved in time roughly , where is the target prediction error. However, their guarantee applied only to input distributions invariant under all single-qubit Clifford gates, and their algorithm fails for important cases such as general product distributions over product states . In this work, we propose a new approach that achieves accurate prediction over essentially any product distribution , provided it is not "classical" in which case there is a trivial exponential lower bound. Our method employs a "biased Pauli analysis," analogous to classical biased Fourier analysis. Implementing this approach requires overcoming several challenges unique to the quantum setting, including the lack of a basis with appropriate orthogonality properties. The techniques we develop to address these issues may have broader applications in quantum information. 

We develop theory to understand an intriguing property of diffusion models for image generation that we term critical windows. Empirically, it has been observed that there are narrow time intervals in sampling during which particular features of the final image emerge, e.g. the image class or background color (Ho et al., 2020b; Meng et al., 2022; Choi et al., 2022; Raya & Ambrogioni, 2023; Georgiev et al., 2023; Sclocchi et al., 2024; Biroli et al., 2024). While this is advantageous for interpretability as it implies one can localize properties of the generation to a small segment of the trajectory, it seems at odds with the continuous nature of the diffusion. We propose a formal framework for studying these windows and show that for data coming from a mixture of strongly log-concave densities, these windows can be provably bounded in terms of certain measures of inter- and intra-group separation. We also instantiate these bounds for concrete examples like well-conditioned Gaussian mixtures. Finally, we use our bounds to give a rigorous interpretation of diffusion models as hierarchical samplers that progressively "decide" output features over a discrete sequence of times. We validate our bounds with synthetic experiments. Additionally, preliminary experiments on Stable Diffusion suggest critical windows may serve as a useful tool for diagnosing fairness and privacy violations in real-world diffusion models. 

The authors provide the first tight sample complexity bounds for shadow tomography and classical shadows in the regime where the target error is below some sufficiently small inverse polynomial in the dimension of the Hilbert space. Specifically, they present a protocol that, given any 𝑚 ∈ 𝑁 m∈N and 𝜖 ≤ 𝑂 ( 𝑑 − 1 / 2 ) ϵ≤O(d −1/2 ), measures 𝑂 ( log ⁡ ( 𝑚 ) / 𝜖 2 ) O(log(m)/ϵ 2 ) copies of an unknown mixed state 𝜌 ∈ 𝐶 𝑑 × 𝑑 ρ∈C d×d and outputs a classical description of 𝜌 ρ. This description can then be used to estimate any collection of 𝑚 m observables to within additive accuracy 𝜖 ϵ. Previously, even for the simpler case of shadow tomography where observables are known in advance, the best known rates either scaled benignly but suboptimally in all of 𝑚 , 𝑑 , 𝜖 m,d,ϵ, or scaled optimally in 𝜖 , 𝑚 ϵ,m but included additional polynomial factors in 𝑑 d. Interestingly, the authors also show via dimensionality reduction that one can rescale 𝜖 ϵ and 𝑑 d to reduce to the regime where 𝜖 ≤ 𝑂 ( 𝑑 − 1 / 2 ) ϵ≤O(d −1/2 ). Their algorithm draws on representation-theoretic tools developed in the context of full state tomography.