544 citations · 1.3k across the 26 of their papers we have counts for
36 papers
Learning SYK Hamiltonians
Anurag Anshu, Srinivasan Arunachalam, Sitan Chen +1
We study the problem of learning the dense Sachdev--Ye--Kitaev (SYK) Hamiltonian from copies of its Gibbs state. Existing algorithms for Hamiltonian learning typically rely on geom…
Optimal Quantum-Classical Separations for Exact Learning
Srinivasan Arunachalam, Amin Shiraz Gilani, Nikhil S. Mande
We study exact learning with membership queries for concept classes , focusing on the relationships among their deterministic, randomized, and quantum…
Quantum Query Complexity Beyond the Worst Case
Srinivasan Arunachalam, Yanlin Chen, Amin Shiraz Gilani
Smoothed analysis is a central framework in classical algorithms for explaining the performance of algorithms beyond the worst case, often explaining why algorithms perform well in…
Quantum Computing for High-Energy Physics: State of the Art and Challenges. Summary of the QC4HEP Working Group
Alberto Di Meglio, Karl Jansen, Ivano Tavernelli +43
Quantum computers offer an intriguing path for a paradigmatic change of computing in the natural sciences and beyond, with the potential for achieving a so-called quantum advantage…
On the Role of Entanglement and Statistics in Learning
Srinivasan Arunachalam, Vojtech Havlicek, Louis Schatzki
In this work we make progress in understanding the relationship between learning models with access to entangled, separable and statistical measurements in the quantum statistical…
Trade-offs between Entanglement and Communication
Srinivasan Arunachalam, Uma Girish
We study the advantages of quantum communication models over classical communication models that are equipped with a limited number of qubits of entanglement. In this direction, we…
A survey on the complexity of learning quantum states
Anurag Anshu, Srinivasan Arunachalam
We survey various recent results that rigorously study the complexity of learning quantum states. These include progress on quantum tomography, learning physical quantum states, al…
A note on the partition bound for one-way classical communication complexity
Srinivasan Arunachalam, João F. Doriguello, Joao F. Doriguello +1
We present a linear program for a one-way version of the partition bound of Jain and Klauck, denoted , and show that it characterizes the one-way ran…
Optimal algorithms for learning quantum phase states
Srinivasan Arunachalam, Sergey Bravyi, Arkopal Dutt +1
We analyze the complexity of learning -qubit quantum phase states. A degree- phase state is defined as a superposition of all basis vectors with amplitudes proporti…
The Parameterized Complexity of Quantum Verification
Srinivasan Arunachalam, Sergey Bravyi, Chinmay Nirkhe +1
We initiate the study of parameterized complexity of problems in terms of the number of non-Clifford gates in the problem description. We show that for the problem o…
No Significant Correlation between Line-emission and Continuum Substructures in the Molecules with ALMA at Planet-forming Scales Program
Haochang Jiang, Wei Zhu, Chris W. Ormel
Recently, the Molecules with ALMA at Planet-forming Scales (MAPS) ALMA Large Program reported a high number of line emission substructures coincident with dust rings and gaps in th…
Matrix hypercontractivity, streaming algorithms and LDCs: the large alphabet case
Srinivasan Arunachalam, Joao F. Doriguello
We prove a hypercontractive inequality for matrix-valued functions defined over large alphabets. In order to do so, we prove a generalization of the powerful -uniform convexity…
Private learning implies quantum stability
Srinivasan Arunachalam, Yihui Quek, John Smolin
Learning an unknown -qubit quantum state is a fundamental challenge in quantum computing. Information-theoretically, it is known that tomography requires exponential in …
Positive spectrahedra: Invariance principles and Pseudorandom generators
Srinivasan Arunachalam, Penghui Yao
In a recent work, O'Donnell, Servedio and Tan (STOC 2019) gave explicit pseudorandom generators (PRGs) for arbitrary -facet polytopes in variables with seed length poly-loga…
Quantum learning algorithms imply circuit lower bounds
Srinivasan Arunachalam, Alex B. Grilo, Tom Gur +2
We establish the first general connection between the design of quantum algorithms and circuit lower bounds. Specifically, let be a class of polynomial-size concepts…
A rigorous and robust quantum speed-up in supervised machine learning
Yunchao Liu, Srinivasan Arunachalam, Kristan Temme
Over the past few years several quantum machine learning algorithms were proposed that promise quantum speed-ups over their classical counterparts. Most of these learning algorithm…
Simpler (classical) and faster (quantum) algorithms for Gibbs partition functions
Srinivasan Arunachalam, Vojtech Havlicek, Giacomo Nannicini +2
We present classical and quantum algorithms for approximating partition functions of classical Hamiltonians at a given temperature. Our work has two main contributions: first, we m…
Communication memento: Memoryless communication complexity
Srinivasan Arunachalam, Supartha Podder
We study the communication complexity of computing functions in the memoryless communication model. Here, Alice is given $x\in \{0…
Sample-efficient learning of quantum many-body systems
Anurag Anshu, Srinivasan Arunachalam, Tomotaka Kuwahara +1
We study the problem of learning the Hamiltonian of a quantum many-body system given samples from its Gibbs (thermal) state. The classical analog of this problem, known as learning…
Quantum Coupon Collector
Srinivasan Arunachalam, Aleksandrs Belovs, Andrew M. Childs +3
We study how efficiently a -element set can be learned from a uniform superposition of its elements. One can think of $|S\rangle=\sum_{i\in S}|i\rang…
Quantum statistical query learning
Srinivasan Arunachalam, Alex B. Grilo, Henry Yuen
We propose a learning model called the quantum statistical learning QSQ model, which extends the SQ learning model introduced by Kearns to the quantum setting. Our model can be als…
Quantum Boosting
Srinivasan Arunachalam, Reevu Maity
Suppose we have a weak learning algorithm for a Boolean-valued problem: produces hypotheses whose bias is small, only slightly better than random gu…
The asymptotic induced matching number of hypergraphs: balanced binary strings
Srinivasan Arunachalam, Péter Vrana, Jeroen Zuiddam
We compute the asymptotic induced matching number of the -partite -uniform hypergraphs whose edges are the -bit strings of Hamming weight , for any large enough even…
Quantum hardness of learning shallow classical circuits
Srinivasan Arunachalam, Alex B. Grilo, Aarthi Sundaram
In this paper we study the quantum learnability of constant-depth classical circuits under the uniform distribution and in the distribution-independent framework of PAC learning. I…