16 citations · 62 across the 29 of their papers we have counts for
8 papers · 1 filter
One-dimensional quantum Gibbs states in constant circuit depth
Saúl Pilatowsky-Cameo, Georgios Styliaris, Ainesh Bakshi +1
We prove that the Gibbs state of any spin chain can be exactly decomposed into a mixture of product states over contiguous blocks of qubits with bounded length, at any constant tem…
Optimal spectrum estimation
Ainesh Bakshi, Apoorv Vikram Singh, Xinyu Tan
We prove that the spectrum of an unknown -dimensional quantum state can be estimated to error in total variation distance using \[ O\!\left(d^2\min\left\{ \frac{1}…
Lower Bounds for Linear Hashing via Arithmetic Kakeya
Ainesh Bakshi, Alex Conway, Hanna Komlós +2
Affine modular linear hashing is one of the simplest classical hash families. For a prime , the hash function is obtained by choosing uniformly from and…
On the Approximability of Boolean Max--CSP
Ainesh Bakshi
Consider the problem of maximizing the number of satisfied constraints of an arbitrary boolean constraint satisfaction problem with arity . We obtain a polynomial time algorithm…
Sharp Bounds on the Eigenvalues of Kikuchi Graphs and Applications to Quantum Max Cut
Ainesh Bakshi, Arpon Basu, Pravesh Kothari +1
We prove that the maximum eigenvalue of the (both signed and unsigned) Laplacian of level Kikuchi graph of any graph with edges is at most . This confirms four rec…
Entrywise Low-Rank Approximation and Matrix Norms via Global Correlation Rounding
Prashanti Anderson, Ainesh Bakshi, Samuel B. Hopkins
Given a matrix , the goal of the entrywise low-rank approximation problem is to find over all rank- matrices , where is t…
Algorithmic Aspects of the Fermi--Hubbard Model
Ainesh Bakshi, Ankur Moitra, Xinyu Tan
Preparing Gibbs states on a quantum computer offers a way to computationally probe how microscopic interactions give rise to macroscopic phenomena at finite temperature. However, a…
Entanglement in quantum spin chains is strictly finite at any temperature
Ainesh Bakshi, Soonwon Choi, Saúl Pilatowsky-Cameo
Entanglement is the hallmark of quantum physics, yet its characterization in interacting many-body systems at thermal equilibrium remains one of the most important challenges in qu…