544 citations · 1.3k across the 26 of their papers we have counts for
27 papers · 1 filter
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…
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…
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 …
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…
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…
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…
Two new results about quantum exact learning
Srinivasan Arunachalam, Sourav Chakraborty, Troy Lee +2
We present two new results about exact learning by quantum computers. First, we show how to exactly learn a -Fourier-sparse -bit Boolean function from …
Quantum Query Algorithms are Completely Bounded Forms
Srinivasan Arunachalam, Jop Briët, Carlos Palazuelos
We prove a characterization of -query quantum algorithms in terms of the unit ball of a space of degree- polynomials. Based on this, we obtain a refined notion of approximat…
Optimizing quantum optimization algorithms via faster quantum gradient computation
András Gilyén, Srinivasan Arunachalam, Nathan Wiebe
We consider a generic framework of optimization algorithms based on gradient descent. We develop a quantum algorithm that computes the gradient of a multi-variate real-valued funct…
A Survey of Quantum Learning Theory
Srinivasan Arunachalam, Ronald de Wolf
This paper surveys quantum learning theory: the theoretical aspects of machine learning using quantum computers. We describe the main results known for three models of learning: ex…
Optimal Quantum Sample Complexity of Learning Algorithms
Srinivasan Arunachalam, Ronald de Wolf
In learning theory, the VC dimension of a concept class is the most common way to measure its "richness." In the PAC model $$ Θ\Big(\frac{d}{\…
Optimizing the Number of Gates in Quantum Search
Srinivasan Arunachalam, Ronald de Wolf
In its usual form, Grover's quantum search algorithm uses queries and other elementary gates to find a solution in an -bit database. Grover…