Person: Anshu, Anurag
Loading...
Email Address
AA Acceptance Date
Birth Date
Research Projects
Organizational Units
Job Title
Last Name
Anshu
First Name
Anurag
Name
Anshu, Anurag
55 results
Search Results
Now showing 1 - 10 of 55
Publication A lower bound on the crossing number of uniform hypergraphs(Elsevier BV, 2016-08) Anshu, Anurag; Shannigrahi, SaswataIn this paper, we consider the embedding of a complete d-uniform geometric hypergraph with n vertices in general position in ℝd, where each hyperedge is represented as a (d−1)-simplex, and a pair of hyperedges is defined to cross if they are vertex-disjoint and contains a common point in the relative interior of the simplices corresponding to them. As a corollary of the Van Kampen-Flores Theorem, it can be seen that such a hypergraph contains Ω(2dd√) (n2d) crossing pairs of hyperedges. Using Gale Transform and Ham Sandwich Theorem, we improve this lower bound to Ω(2dlogdd√) (n2d).Publication A Unified Approach to Source and Message Compression(2019-06-05) Anshu, Anurag; Jain, Rahul; Warsi, Naqueeb AhmadWe study the problem of source and message compression in the one-shot setting for the point-to-point and multi-party scenarios (with and without side information). We derive achievability results for these tasks in a unified manner, using the techniques of convex-split, which was introduced in [Anshu,Devabathini and Jain 2014] and position-based decoding introduced in [Anshu, Jain and Warsi 2017], which in turn uses hypothesis testing between distributions. These results are in terms of smooth max divergence and smooth hypothesis testing divergence. As a by-product of the tasks studied in this work, we obtain several known source compression results (originally studied in the asymptotic and i.i.d. setting) in the one-shot case. One of our achievability results includes the problem of message compression with side information, originally studied in [Braverman and Rao 2011]. We show that both our result and the result in [Braverman and Rao 2011] are near optimal in the one-shot setting by proving a converse bound.Publication Partially Smoothed Information Measures(Institute of Electrical and Electronics Engineers (IEEE), 2020-08) Anshu, Anurag; Berta, Mario; Jain, Rahul; Tomamichel, MarcoSmooth entropies are a tool for quantifying resource trade-offs in (quantum) information theory and cryptography. In typical bi- and multi-partite problems, however, some of the sub-systems are often left unchanged and this is not reflected by the standard smoothing of information measures over a ball of close states. We propose to smooth instead only over a ball of close states which also have some of the reduced states on the relevant sub-systems fixed. This partial smoothing of information measures naturally allows to give more refined characterizations of various information-theoretic problems in the one-shot setting. In particular, we immediately get asymptotic second-order characterizations for tasks such as privacy amplification against classical side information or classical state splitting. For quantum problems like state merging the general resource trade-off is tightly characterized by partially smoothed information measures as well.Publication Quantum Communication Using Coherent Rejection Sampling(American Physical Society (APS), 2017-09-21) Anshu, Anurag; Devabathini, Vamsi Krishna; Jain, RahulWe present a new scheme for the compression of one-way quantum messages, in the setting of coherent entanglement assisted quantum communication. For this, we present a new technical tool that we call the convex split lemma, which is inspired by the classical compression schemes that use rejection sampling procedure. As a consequence, we show new bounds on the quantum communication cost of single-shot entanglement-assisted one-way quantum state redistribution task and for the sub-tasks quantum state splitting and quantum state merging. Our upper and lower bounds are tight up to a constant and hence stronger than previously known best bounds for above tasks. Our protocols use explicit quantum operations on the sides of Alice and Bob, which are different from the decoupling by random unitaries approach used in previous works. As another application, we present a port-based teleportation scheme which works when the set of input states is restricted to a known ensemble, hence potentially saving the number of required ports. Furthermore, in case of no prior knowledge about the set of input states, our average success fidelity matches the known average success fidelity, providing a new port-based teleportation scheme with similar performance as appears in literature.Publication Beyond Product State Approximations for a Quantum Analogue of Max Cut(2020-03-31) Anshu, Anurag; Gosset, David; Morenz, KarenWe consider a computational problem where the goal is to approximate the maximum eigenvalue of a two-local Hamiltonian that describes Heisenberg interactions between qubits located at the vertices of a graph. Previous work has shed light on this problem's approximability by product states. For any instance of this problem the maximum energy attained by a product state is lower bounded by the Max Cut of the graph and upper bounded by the standard Goemans-Williamson semidefinite programming relaxation of it. Gharibian and Parekh described an efficient classical approximation algorithm for this problem which outputs a product state with energy at least 0.498 times the maximum eigenvalue in the worst case, and observe that there exist instances where the best product state has energy 1/2 of optimal. We investigate approximation algorithms with performance exceeding this limitation which are based on optimizing over tensor products of few-qubit states and shallow quantum circuits. We provide an efficient classical algorithm which achieves an approximation ratio of at least 0.53 in the worst case. We also show that for any instance defined by a 3- or 4-regular graph, there is an efficiently computable shallow quantum circuit that prepares a state with energy larger than the best product state (larger even than its semidefinite programming relaxation).Publication Quantum Log-Approximate-Rank Conjecture is Also False(IEEE, 2019-11) Anshu, Anurag; Boddu, Naresh Goud; Touchette, DaveIn 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.Publication A Composition Theorem for Randomized Query Complexity(2017-06-14) Anshu, Anurag; Gavinsky, Dmitry; Jain, Rahul; Kundu, Srijita; Lee, Troy; Mukhopadhyay, Priyanka; Santha, Miklos; Sanyal, SwagatoLet the randomized query complexity of a relation for error probability ϵ be denoted by Rϵ(⋅). We prove that for any relation f⊆{0,1}n× and Boolean function g:{0,1}m→{0,1}, R1/3(f∘gn)=Ω(R4/9(f)⋅R1/2−1/n4(g)), where f∘gn is the relation obtained by composing f and g. We also show that R1/3(f∘(g⊕O(logn))n)=Ω(logn⋅R4/9(f)⋅R1/3(g)), where g⊕O(logn) is the function obtained by composing the xor function on O(logn) bits and gt.Publication On Query-to-Communication Lifting for Adversary Bounds(ACM, 2020-12-07) Anshu, Anurag; Shalev, Ben-David; Srijita, KunduWe investigate query-to-communication lifting theorems for models related to the quantum adversary bounds. Our results are as follows: 1. We show that the classical adversary bound lifts to a lower bound on randomized communication complexity with a constant-sized gadget. We also show that the classical adversary bound is a strictly stronger lower bound technique than the previously-lifted measure known as critical block sensitivity, making our lifting theorem one of the strongest lifting theorems for randomized communication complexity using a constant-sized gadget. 2. Turning to quantum models, we show a connection between lifting theorems for quantum adversary bounds and secure 2-party quantum computation in a certain "honest-but-curious" model. Under the assumption that such secure 2-party computation is impossible, we show that a simplified version of the positive-weight adversary bound lifts to a quantum communication lower bound using a constant-sized gadget. We also give an unconditional lifting theorem which lower bounds bounded-round quantum communication protocols. 3. Finally, we give some new results in query complexity. We show that the classical adversary and the positive-weight quantum adversary are quadratically related. We also show that the positive-weight quantum adversary is never larger than the square of the approximate degree. Both relations hold even for partial functions.Publication Separating Quantum Communication and Approximate Rank(2016-11-17) Anshu, Anurag; Ben-David, Shalev; Garg, Ankit; Jain, Rahul; Kothari, Robin; Lee, TroyOne of the best lower bound methods for the quantum communication complexity of a function H (with or without shared entanglement) is the logarithm of the approximate rank of the communication matrix of H. This measure is essentially equivalent to the approximate gamma_2 norm and generalized discrepancy, and subsumes several other lower bounds. All known lower bounds on quantum communication complexity in the general unbounded-round model can be shown via the logarithm of approximate rank, and it was an open problem to give any separation at all between quantum communication complexity and the logarithm of the approximate rank. In this work we provide the first such separation: We exhibit a total function H with quantum communication complexity almost quadratically larger than the logarithm of its approximate rank. We construct H using the communication lookup function framework of Anshu et al. (FOCS 2016) based on the cheat sheet framework of Aaronson et al. (STOC 2016). From a starting function F, this framework defines a new function H=F_G. Our main technical result is a lower bound on the quantum communication complexity of F_G in terms of the discrepancy of F, which we do via quantum information theoretic arguments. We show the upper bound on the approximate rank of F_G by relating it to the Boolean circuit size of the starting function F.Publication Sample-efficient learning of quantum many-body systems(IEEE, 2020-11) Anshu, Anurag; Arunachalam, Srinivasan; Kuwahara, Tomotaka; Soleimanifar, MehdiWe 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 l_2-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.