Anurag Anshu

FOCS Conference 2025 Conference Paper

Learning quantum Gibbs states locally and efficiently

• Chi-Fang Chen
• Anurag Anshu
• Quynh T. Nguyen

Learning the Hamiltonian underlying a quantum many-body system in thermal equilibrium is a fundamental task in quantum learning theory and experimental sciences. To learn the Gibbs state of local Hamiltonians at any constant inverse temperature, the state-of-the-art provable algorithms fall short of the optimal sample and computational complexity, in sharp contrast with the locality and simplicity in the classical cases. In this work, we present a learning algorithm that learns each local term of a n-qubit Hamiltonian on any bounded-degree graph to a constant additive error with the optimal sample complexity $\mathcal{O}(\log n)$. The protocol uses parallelizable local quantum measurements that act within bounded neighborhoods of the graph and near-linear-time classical post-processing. We also give a learning algorithm for lattice Hamiltonians with near-optimal scaling on the learning precision and the inverse temperature. At the heart of our algorithm is the interplay between locality, the Kubo-MartinSchwinger condition, and the operator Fourier transform at arbitrary temperatures.

STOC Conference 2025 Conference Paper

On the Computational Power of QAC0 with Barely Superlinear Ancillae

• Anurag Anshu
• Yangjing Dong
• Fengning Ou
• Penghui Yao

QAC 0 is the family of constant-depth polynomial-size quantum circuits consisting of arbitrary single qubit unitaries and multi-qubit Toffoli gates. It was introduced by Moore as a quantum counterpart of AC 0 , along with the conjecture that QAC 0 circuits can not compute PARITY. In this work we make progress on this longstanding conjecture: we show that any depth- d QAC 0 circuit requires n 1+3 − d ancillae to compute a function with approximate degree Θ( n ), which includes PARITY, MAJORITY and MOD k . We further establish superlinear lower bounds on quantum state synthesis and quantum channel synthesis. This is the first superlinear lower bound on the super-linear sized QAC 0 . Regarding PARITY, we show that any further improvement on the size of ancillae to n 1+exp(− o ( d )) would imply that PARITY ∉ QAC0. These lower bounds are derived by giving low-degree approximations to QAC 0 circuits. We show that a depth- d QAC 0 circuit with a ancillae, when applied to low-degree operators, has a degree ( n + a ) 1−3 − d polynomial approximation in the spectral norm. This implies that the class QLC 0 , corresponding to linear size QAC 0 circuits, has approximate degree o ( n ). This is a quantum generalization of the result that LC 0 circuits have approximate degree o ( n ) by Bun, Robin, and Thaler. Our result also implies that QLC 0 ≠ NC 1 .

STOC Conference 2024 Conference Paper

Circuit-to-Hamiltonian from Tensor Networks and Fault Tolerance

• Anurag Anshu
• Nikolas P. Breuckmann
• Quynh T. Nguyen

STOC Conference 2024 Conference Paper

Learning Shallow Quantum Circuits

• Hsin-Yuan Huang
• Yunchao Liu 0002
• Michael Broughton
• Isaac Kim 0001
• Anurag Anshu
• Zeph Landau
• Jarrod R. McClean

STOC Conference 2023 Conference Paper

NLTS Hamiltonians from Good Quantum Codes

• Anurag Anshu
• Nikolas P. Breuckmann
• Chinmay Nirkhe

The NLTS (No Low-Energy Trivial State) conjecture of Freedman and Hastings posits that there exist families of Hamiltonians with all low energy states of non-trivial complexity (with complexity measured by the quantum circuit depth preparing the state). We prove this conjecture by showing that a particular family of constant-rate and linear-distance qLDPC codes correspond to NLTS local Hamiltonians, although we believe this to be true for all current constructions of good qLDPC codes.

STOC Conference 2022 Conference Paper

An area law for 2d frustration-free spin systems

• Anurag Anshu
• Itai Arad
• David Gosset

We prove that the entanglement entropy of the ground state of a locally gapped frustration-free 2D lattice spin system satisfies an area law with respect to a vertical bipartition of the lattice into left and right regions. We first establish that the ground state projector of any locally gapped frustration-free 1D spin system can be approximated to within error є by a degree O (√ n log(є −1 )) multivariate polynomial in the interaction terms of the Hamiltonian. This generalizes the optimal bound on the approximate degree of the boolean AND function, which corresponds to the special case of commuting Hamiltonian terms. For 2D spin systems we then construct an approximate ground state projector (AGSP) that employs the optimal 1D approximation in the vicinity of the boundary of the bipartition of interest. This AGSP has sufficiently low entanglement and error to establish the area law using a known technique.

STOC Conference 2022 Conference Paper

Distributed Quantum inner product estimation

• Anurag Anshu
• Zeph Landau
• Yunchao Liu 0002

As small quantum computers are becoming available on different physical platforms, a benchmarking task known as cross-platform verification has been proposed that aims to estimate the fidelity of states prepared on two quantum computers. This task is fundamentally distributed, as no quantum communication can be performed between the two physical platforms due to hardware constraints, which prohibits a joint SWAP test. In this paper we settle the sample complexity of this task across all measurement and communication settings. The essence of the task, which we call distributed quantum inner product estimation, involves two players Alice and Bob who have k copies of unknown states ρ,σ (acting on ℂ d ) respectively. Their goal is to estimate Tr (ρσ) up to additive error ε∈(0,1), using local quantum operations and classical communication. In the weakest setting where only non-adaptive single-copy measurements and simultaneous message passing are allowed, we show that k = O (max{1/ε 2 ,√ d /ε}) copies suffice. This achieves a savings compared to full tomography which takes Ω( d 3 ) copies with single-copy measurements. Surprisingly, we also show that the sample complexity must be at least Ω(max{1/ε 2 ,√ d /ε}), even in the strongest setting where adaptive multi-copy measurements and arbitrary rounds of communication are allowed. This shows that the success achieved by shadow tomography, for sample-efficiently learning the properties of a single system, cannot be generalized to the distributed setting. Furthermore, the fact that the sample complexity remains the same with single and multi-copy measurements contrasts with single system quantum property testing, which often demonstrate exponential separations in sample complexity with single and multi-copy measurements.

STOC Conference 2020 Conference Paper

Entanglement subvolume law for 2d frustration-free spin systems

• Anurag Anshu
• Itai Arad
• David Gosset

FOCS Conference 2020 Conference Paper

Sample-efficient learning of quantum many-body systems

• Anurag Anshu
• Srinivasan Arunachalam
• Tomotaka Kuwahara
• Mehdi Soleimanifar

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 graphical models or Boltzmann machines, is a well-studied question in machine learning and statistics. In this work, we give the first sample-efficient algorithm for the quantum Hamiltonian learning problem. In particular, we prove that polynomially many samples in the number of particles (qudits) are necessary and sufficient for learning the parameters of a spatially local Hamiltonian in l2-norm. Our main contribution is in establishing the strong convexity of the log-partition function of quantum many-body systems, which along with the maximum entropy estimation yields our sample-efficient algorithm. Classically, the strong convexity for partition functions follows from the Markov property of Gibbs distributions. This is, however, known to be violated in its exact form in the quantum case. We introduce several new ideas to obtain an unconditional result that avoids relying on the Markov property of quantum systems, at the cost of a slightly weaker bound. In particular, we prove a lower bound on the variance of quasi-local operators with respect to the Gibbs state, which might be of independent interest. Our work paves the way toward a more rigorous application of machine learning techniques to quantum many-body problems.

FOCS Conference 2019 Conference Paper

Quantum Log-Approximate-Rank Conjecture is Also False

• Anurag Anshu
• Naresh Goud Boddu
• Dave Touchette

In a recent breakthrough result, Chattopadhyay, Mande and Sherif [ECCC TR18-17] showed an exponential separation between the log approximate rank and randomized communication complexity of a total function f, hence refuting the log approximate rank conjecture of Lee and Shraibman [2009]. We provide an alternate proof of their randomized communication complexity lower bound using the information complexity approach. Using the intuition developed there, we derive a polynomially-related quantum communication complexity lower bound using the quantum information complexity approach, thus providing an exponential separation between the log approximate rank and quantum communication complexity of f. Previously, the best known separation between these two measures was (almost) quadratic, due to Anshu, Ben-David, Garg, Jain, Kothari and Lee [CCC, 2017]. This settles one of the main question left open by Chattopadhyay, Mande and Sherif, and refutes the quantum log approximate rank conjecture of Lee and Shraibman [2009]. Along the way, we develop a Shearer-type protocol embedding for product input distributions that might be of independent interest.

STOC Conference 2017 Conference Paper

Exponential separation of quantum communication and classical information

• Anurag Anshu
• Dave Touchette
• Penghui Yao
• Nengkun Yu

We exhibit a Boolean function for which the quantum communication complexity is exponentially larger than the classical information complexity . An exponential separation in the other direction was already known from the work of Kerenidis et. al. [SICOMP 44, pp. 1550-1572], hence our work implies that these two complexity measures are incomparable.

FOCS Conference 2016 Conference Paper

Separations in Communication Complexity Using Cheat Sheets and Information Complexity

• Anurag Anshu
• Aleksandrs Belovs
• Shalev Ben-David
• Mika Göös
• Rahul Jain 0001
• Robin Kothari
• Troy Lee
• Miklos Santha

While exponential separations are known between quantum and randomized communication complexity for partial functions (Raz, STOC 1999), the best known separation between these measures for a total function is quadratic, witnessed by the disjointness function. We give the first super-quadratic separation between quantum and randomized communication complexity for a total function, giving an example exhibiting a power 2. 5 gap. We further present a 1. 5 power separation between exact quantum and randomized communication complexity, improving on the previous ≅ 1. 15 separation by Ambainis (STOC 2013). Finally, we present a nearly optimal quadratic separation between randomized communication complexity and the logarithm of the partition number, improving upon the previous best power 1. 5 separation due to Goos, Jayram, Pitassi, and Watson. Our results are the communication analogues of separations in query complexity proved using the recent cheat sheet framework of Aaronson, Ben-David, and Kothari (STOC 2016). Our main technical results are randomized communication and information complexity lower bounds for a family of functions, called lookup functions, that generalize and port the cheat sheet framework to communication complexity.