A quantum impurity model describes a small interacting subsystem embedded into a large bath of free fermions. Here we study the computational complexity of calculating the ground energy, thermal equilibrium, and dynamical properties of these models. Our work reveals a sharp contrast: equilibrium properties can be effic...
Srinivasan Arunachalam, S. Bravyi, Anirban Narayan Chowdhury et al.· 0 citations
In this note, we consider tomography of $n$-qubit quantum states $|\psi \rangle$ that are promised to have stabilizer rank $k$ i.e., admit a stabilizer decomposition of $|\psi\rangle = \sum_{i=1}^k c_i |\phi_i\rangle$ where each $|\phi_i\rangle$ is a stabilizer state. We give a tomography protocol for such states up to...
This work proves unconditional separations between low-depth quantum computation and the corresponding bounded-resource classical language-model architectures in both regimes, and initiates the study of quantum advantage in the era of large language models.
Srinivasan Arunachalam, Arkopal Dutt, H. Krovi et al.· 2 citations
Gowers, Green, Manners, and Tao (Annals'25) recently resolved Marton's polynomial Freiman-Ruzsa conjecture. We give an algorithmic counterpart to their result: given uniform sampling and membership-oracle access to a set $A \subseteq \mathbb{F}_2^n$ with doubling constant at most $K$, our algorithm outputs a subspace o...
The results expand the range of dynamical systems that quantum computers can simulate efficiently by developing efficient algorithms for linear Volterra integro-differential equations with a convolution memory kernel that output a quantum state encoding the state description over a time interval or at a particular time...
Abtin Ameri, Arkopal Dutt, H. Krovi· 0 citations
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.
