9 papers · 1 filter
Separating quantum circuits from classical LLMs
Srinivasan Arunachalam, Arkopal Dutt, Hari Krovi +1
Modern large language models - transformers and diffusion language models - are built around two canonical algorithmic tasks: prediction and generation. We prove unconditional sepa…
No low-degree tests for quantum states
Omar Alrabiah, Srinivasan Arunachalam, Sabee Grewal +1
We study the problem of testing low-degree phase states, namely m-qudit quantum states of the form , where is a degree- po…
Optimal Stabilizer Testing and Learning with Limited Quantum Memory
Srinivasan Arunachalam, Louis Schatzki
We study stabilizer state testing and learning with limited coherent quantum memory. Here an algorithm sequentially receives copies of an unknown -qubit state, but may keep only…
Tomography of quantum states with bounded extent
Srinivasan Arunachalam, Arkopal Dutt
We give a general framework for tomography of states that have bounded-extent with respect to a structured class of states. Let be a family of -qubit states such th…
Learning stabilizer structure of quantum states
Srinivasan Arunachalam, Arkopal Dutt
We consider the task of learning a structured stabilizer decomposition of an arbitrary -qubit quantum state : for , output a state with stabilizer-r…
Learning depth-3 circuits via quantum agnostic boosting
Srinivasan Arunachalam, Arkopal Dutt, Alexandru Gheorghiu +1
We initiate the study of quantum agnostic learning of phase states with respect to a function class : given copies of an unk…