Publications

Quantum many-body systems

Anurag Anshu, Nikolas P. Breuckmann, and Chinmay Nirkhe. 6/27/2022. “NLTS Hamiltonians from good quantum codes.” 55th Annual ACM Symposium on Theory of Computing (STOC 2023). ACM. Publisher's VersionAbstract
The NLTS (No Low-Energy Trivial State) conjecture of Freedman and Hastings [2014] 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 the recently discovered families of constant-rate and linear-distance QLDPC codes correspond to NLTS local Hamiltonians.
  • Quanta magazine article on the paper.
  • QIP 2023 (plenary talk)
Anurag Anshu and Nikolas P. Breuckmann. 12/1/2022. “A construction of Combinatorial NLTS.” Journal of Mathematical Physics, 63, 122201. Publisher's VersionAbstract
The NLTS (No Low-Energy Trivial State) conjecture of Freedman and Hastings [2014] posits that there exist families of Hamiltonians with all low energy states of high complexity (with complexity measured by the quantum circuit depth preparing the state). Here, we prove a weaker version called the combinatorial NLTS, where a quantum circuit lower bound is shown against states that violate a (small) constant fraction of local terms. This generalizes the prior NLETS results (Eldar and Harrow [2017]; Nirkhe, Vazirani and Yuen [2018]). Our construction is obtained by combining tensor networks with expander codes (Sipser and Spielman [1996]). The Hamiltonian is the parent Hamiltonian of a perturbed tensor network, inspired by the `uncle Hamiltonian' of Fernandez-Gonzalez et. al. [2015]. Thus, we deviate from the quantum CSS code Hamiltonians considered in most prior works.
Anurag Anshu, Itai Arad, and David Gosset. 6/24/2022. “An area law for 2D frustration-free spin systems.” 54th Annual ACM SIGACT Symposium on Theory of Computing (STOC 2022). Publisher's VersionAbstract
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(sqrt{nlog(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.
  • QIP 2022 (contributed talk)
Anurag Anshu, Itai Arad, and David Gosset. 4/15/2022. “Entanglement subvolume law for 2D frustration-free spin systems.” Communications in Mathematical Physics. Publisher's VersionAbstract
Let H be a frustration-free Hamiltonian describing a 2D grid of qudits with local interactions, a unique ground state, and local spectral gap lower bounded by a positive constant. For any bipartition defined by a vertical cut of length L running from top to bottom of the grid, we prove that the corresponding entanglement entropy of the ground state of H is upper bounded by Õ(L 5/3). For the special case of a 1D chain, our result provides a new area law which improves upon prior work, in terms of the scaling with qudit dimension and spectral gap. In addition, for any bipartition of the grid into a rectangular region A and its complement, we show that the entanglement entropy is upper bounded as Õ(|∂ A|5/3) where ∂ A is the boundary of A. This represents a subvolume bound on entanglement in frustration-free 2D systems. In contrast with previous work, our bounds depend on the local (rather than global) spectral gap of the Hamiltonian. We prove our results using a known method which bounds the entanglement entropy of the ground state in terms of certain properties of an approximate ground state projector (AGSP). To this end, we construct a new AGSP which is based on a robust polynomial approximation of the AND function and we show that it achieves an improved trade-off between approximation error and entanglement.
  • QIP 2020 (contributed talk)
  • Extended abstract in the 52nd Symposium on the Theory of Computing (STOC 2020)
Anurag Anshu, Aram W. Harrow, and Mehdi Soleimanifar. 9/15/2022. “Entanglement spread area law in gapped ground states.” Nature Physics. Publisher's VersionAbstract
Ground-state entanglement governs various properties of quantum many-body systems at low temperatures and is the key to understanding gapped quantum phases of matter. Here we identify a structural property of entanglement in the ground state of gapped local Hamiltonians. This property is captured using a quantum information quantity known as the entanglement spread, which measures the difference between Rényi entanglement entropies. Our main result shows that gapped ground states possess limited entanglement spread across any partition of the system, exhibiting an area-law scaling. Our result applies to systems with interactions described by any graph, but we obtain an improved bound for the special case of lattices. These interaction graphs include cases where entanglement entropy is known not to satisfy an area law. We achieve our results first by connecting the ground-state entanglement to the communication complexity of testing bipartite entangled states and then devising a communication scheme for testing ground states using recently developed quantum algorithms for Hamiltonian simulation.
Anurag Anshu, Srinivasan Arunachalam, Tomotaka Kuwahara, and Mehdi Soleimanifar. 5/24/2021. “Sample-efficient learning of interacting quantum systems.” Nature Physics, 17, Pp. 931–935. Publisher's VersionAbstract
Learning the Hamiltonian that describes interactions in a quantum system is an important task in both condensed-matter physics and the verification of quantum technologies. Its classical analogue arises as a central problem in machine learning known as learning Boltzmann machines. Previously, the best known methods for quantum Hamiltonian learning with provable performance guarantees required a number of measurements that scaled exponentially with the number of particles. Here we prove that only a polynomial number of local measurements on the thermal state of a quantum system are necessary and sufficient for accurately learning its Hamiltonian. We achieve this by establishing that the absolute value of the finite-temperature free energy of quantum many-body systems is strongly convex with respect to the interaction coefficients. The framework introduced in our work provides a theoretical foundation for applying machine learning techniques to quantum Hamiltonian learning, achieving a long-sought goal in quantum statistical learning.
  • News & Views by Vedran Dunjko
  • IBM blogpost
  • Extended abstract in 61st Annual IEEE Symposium on Foundations of Computer Science (FOCS), 2020
  • QIP 2021 (contributed talk).
Anurag Anshu, David Gosset, Karen J. Morenz Korol, and Mehdi Soleimanifar. 12/17/2021. “Improved approximation algorithms for bounded-degree local Hamiltonians.” Physical Review Letters. Publisher's VersionAbstract
We consider the task of approximating the ground state energy of two-local quantum Hamiltonians on bounded-degree graphs. Most existing algorithms optimize the energy over the set of product states. Here we describe a family of shallow quantum circuits that can be used to improve the approximation ratio achieved by a given product state. The algorithm takes as input an n-qubit product state |v⟩ with mean energy e0=⟨v|H|v⟩ and variance Var=⟨v|(H−e0)2|v⟩, and outputs a state with an energy that is lower than e0 by an amount proportional to Var2/n. In a typical case, we have Var=Ω(n) and the energy improvement is proportional to the number of edges in the graph. When applied to an initial random product state, we recover and generalize the performance guarantees of known algorithms for bounded-occurrence classical constraint satisfaction problems. We extend our results to k-local Hamiltonians and entangled initial states.
  • QIP 2022 (contributed talk)
Tomotaka Kuwahara, Alvaro M. Alhambra, and Anurag Anshu. 3/9/2021. “Improved thermal area law and quasi-linear time algorithm for quantum Gibbs states.” Physical Review X 11 (1), Pp. 011047. Publisher's VersionAbstract
One of the most fundamental problems in quantum many-body physics is the characterization of correlations among thermal states. Of particular relevance is the thermal area law, which justifies the tensor network approximations to thermal states with a bond dimension growing polynomially with the system size. In the regime of sufficiently low temperatures, which is crucially important for practical applications, the existing techniques do not yield optimal bounds. Here, we propose a new thermal area law that holds for generic many-body systems on lattices. We improve the temperature dependence from the original O(β) to O(β2/3) up to a logarithmic factor, thereby suggesting subballistic propagation of entanglement by imaginary-time evolution. This qualitatively differs from the real-time evolution, which usually induces linear growth of entanglement. We also prove analogous bounds for the Rényi entanglement of purification and the entanglement of formation. Our analysis is based on a polynomial approximation to the exponential function which provides a relationship between the imaginary-time evolution and random walks. Moreover, for one-dimensional (1D) systems with n spins, we prove that the Gibbs state is well approximated by a matrix product operator with a sublinear bond dimension for β=o[log(n)]. This proof allows us to rigorously establish, for the first time, a quasilinear time classical algorithm for constructing a matrix product state representation of 1D quantum Gibbs states at arbitrary temperatures of β=o[log(n)]. Our new technical ingredient is a block decomposition of the Gibbs state that bears a resemblance to the decomposition of real-time evolution given by Haah et al.
  • QIP 2021 (contributed talk)
Alvaro M. Alhambra, Anurag Anshu, and Henrik Wilming. 5/15/2020. “Revivals imply quantum many-body scars.” Physical Review B, 101, 20. Publisher's VersionAbstract
We derive general rigorous results relating revivals in the dynamics of quantum many-body systems to the entanglement properties of energy eigenstates. For a D-dimensional lattice system of N sites initialized in a low-entangled and short-range correlated state, our results show that a perfect revival of the state after a time of at most O(poly(N)) implies the existence of at least O(√N/log2D(N)) “quantum many-body scars”: energy eigenstates with energies placed in an equally spaced ladder and with Rényi entanglement entropy of at most O(log(N))+O(|∂A|) for any region A of the lattice. This shows that quantum many-body scars are a necessary consequence of revivals, independent of particularities of the Hamiltonian leading to them. We also present results for approximate revivals and for revivals of expectation values of observables and prove that the duration of revivals of states has to become vanishingly short with increasing system size.
Anurag Anshu. 4/6/2020. “Improved local spectral gap thresholds for lattices of finite dimension.” Physical Review B, 101, 16. Publisher's VersionAbstract
Knabe's theorem lower bounds the spectral gap of a one-dimensional frustration-free local Hamiltonian in terms of the local spectral gaps of finite regions. It also provides a local spectral gap threshold for Hamiltonians that are gapless in the thermodynamic limit, showing that the local spectral gap must scale inverse linearly with the length of the region for such systems. Recent works have further improved upon this threshold, tightening it in the one-dimensional case and extending it to higher dimensions. Here, we show a local spectral gap threshold for frustration-free Hamiltonians on a finite-dimensional lattice that is optimal up to a constant factor that depends on the dimension of the lattice. Our proof is based on the detectability lemma framework and uses the notion of a coarse-grained Hamiltonian (introduced in [Anshu et al., Phys. Rev. B 93, 205142]) as a link connecting the (global) spectral gap and the local spectral gap.
Anurag Anshu, David Gosset, and Karen Morenz. 3/1/2020. “Beyond product state approximations for a quantum analogue of Max Cut.” 15th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC), 158, 1868-8969. Publisher's VersionAbstract
We 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).
Anurag Anshu. 8/8/2016. “Concentration bounds for quantum states with finite correlation length on quantum spin lattice systems.” New Journal of Physics, 18, 8, Pp. 083011. Publisher's VersionAbstract
We consider the problem of determining the energy distribution of quantum states that satisfy exponential decay of correlation and product states, with respect to a quantum local Hamiltonian on a spin lattice. For a quantum state on a D-dimensional lattice that has correlation length σ and has average energy e with respect to a given local Hamiltonian (with n local terms, each of which has norm at most 1), we show that the overlap of this state with eigenspace of energy f is at most $\exp {(-({(e-f)}^{2}\sigma )}^{\tfrac{1}{D+1}}/{n}^{\tfrac{1}{D+1}}D\sigma )$. This bound holds whenever $| e-f| \gt {2}^{D}\sqrt{n\sigma }$. Thus, on a one-dimensional lattice, the tail of the energy distribution decays exponentially with the energy. For product states, we improve above result to obtain a Gaussian decay in energy, even for quantum spin systems without an underlying lattice structure. Given a product state on a collection of spins which has average energy e with respect to a local Hamiltonian (with n local terms and each local term overlapping with at most m other local terms), we show that the overlap of this state with eigenspace of energy f is at most $\exp (-{(e-f)}^{2}/{{nm}}^{2})$. This bound holds whenever $| e-f| \gt m\sqrt{n}$.
Anurag Anshu, Itai Arad, and Thomas Vidick. 5/15/2016. “Simple proof of the detectability lemma and spectral gap amplification.” Physical Review B, 93, 20, Pp. 205142. Publisher's VersionAbstract
The detectability lemma is a useful tool for probing the structure of gapped ground states of frustration-free Hamiltonians of lattice spin models. The lemma provides an estimate on the error incurred by approximating the ground space projector with a product of local projectors. We provide a new, simpler proof for the detectability lemma, which applies to an arbitrary ordering of the local projectors, and show that it is tight up to a constant factor. As an application we show how the lemma can be combined with a strong converse by Gao to obtain local spectral gap amplification: we show that by coarse-graining a local frustration-free Hamiltonian with a spectral gap γ>0 to a length scale O(γ−1/2), one gets an Hamiltonian with an Ω(1) spectral gap.
Anurag Anshu, Itai Arad, and Aditya Jain. 4/1/2016. “How local is the information in tensor networks of matrix product states or projected entangled pairs states.” Physical Review B, 94, 19, Pp. 195143. Publisher's VersionAbstract
Two-dimensional tensor networks such as projected entangled pairs states (PEPS) are generally hard to contract. This is arguably the main reason why variational tensor network methods in two dimensions are still not as successful as in one dimension. However, this is not necessarily the case if the tensor network represents a gapped ground state of a local Hamiltonian; such states are subject to many constraints and contain much more structure. In this paper, we introduce an approach for approximating the expectation value of a local observable in ground states of local Hamiltonians that are represented by PEPS tensor networks. Instead of contracting the full tensor network, we try to estimate the expectation value using only a local patch of the tensor network around the observable. Surprisingly, we demonstrate that this is often easier to do when the system is frustrated. In such case, the spanning vectors of the local patch are subject to nontrivial constraints that can be utilized via a semidefinite program to calculate rigorous lower and upper bounds on the expectation value. We test our approach in one-dimensional systems, where we show how the expectation value can be calculated up to at least 3 or 4 digits of precision, even when the patch radius is smaller than the correlation length.

Quantum complexity theory

Anurag Anshu, Zeph Landau, and Yunchao Liu. 6/24/2022. “Distributed quantum inner product estimation.” 54th Annual ACM SIGACT Symposium on Theory of Computing (STOC 2022).Abstract

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 rho, sigma (acting on a d dimensional Hilbert space) respectively. Their goal is to estimate Tr(rho sigma) up to additive error eps, 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/eps^2, sqrt{d}/eps}) copies suffice. This achieves a savings compared to full tomography which takes Omega(d^3) copies with single-copy measurements. Surprisingly, we also show that the sample complexity must be at least Omega(max{1/eps^2, sqrt{d}/eps}), 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 demonstrates exponential separations in sample complexity with single and multi-copy measurements.

  • QIP 2022 (contributed talk)
Anurag Anshu and Chinmay Nirkhe. 1/25/2022. “Circuit lower bounds for low-energy states of quantum code Hamiltonians.” In ITCS 1/25/2022. Vol. 215. Publisher's VersionAbstract
The No Low-energy Trivial States (NLTS) conjecture of Freedman and Hastings, 2014 -- which posits the existence of a local Hamiltonian with a super-constant quantum circuit lower bound on the complexity of all low-energy states -- identifies a fundamental obstacle to the resolution of the quantum PCP conjecture. In this work, we provide new techniques, based on entropic and local indistinguishability arguments, that prove circuit lower bounds for all the low-energy states of local Hamiltonians arising from quantum error-correcting codes. For local Hamiltonians arising from nearly linear-rate or nearly linear-distance LDPC stabilizer codes, we prove super-constant circuit lower bounds for the complexity of all states of energy o(n). Such codes are known to exist and are not necessarily locally testable, a property previously suspected to be essential for the NLTS conjecture. Curiously, such codes can also be constructed on a two-dimensional lattice, showing that low-depth states cannot accurately approximate the ground-energy even in physically relevant systems.
  • QIP 2021 (contributed talk)
Anurag Anshu, Shalev Ben-David, and Srijita Kundu. 2021. “On Query-To-Communication Lifting for Adversary Bounds.” 36th Computational Complexity Conference (CCC 2021) 200, Pp. 30:1--30:39. Publisher's VersionAbstract
We 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.
  • QIP 2021 (contributed talk) 
Anurag Anshu, Naresh Goud Boddu, and Dave Touchette. 11/9/2019. “Quantum Log-Approximate-Rank Conjecture is also False.” 2019 IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS). Publisher's VersionAbstract

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.

  • QIP 2020 (contributed talk)
Anurag Anshu, Ankit Garg, Aram W. Harrow, and Penghui Yao. 6/18/2018. “Expected Communication Cost of Distributed Quantum Tasks.” IEEE Transactions on Information Theory, 64, 11, Pp. 7395-7423. Publisher's VersionAbstract
A central question in the classical information theory is that of source compression, which is the task where Alice receives a sample from a known probability distribution and needs to transmit it to the receiver Bob with small error. This problem has a one-shot solution due to Huffman, in which the messages are of variable length and the expected length of the messages matches the asymptotic and independent identically distributed (i.i.d.) compression rate of the Shannon entropy of the source. In this paper, we consider a quantum extension of above task, where Alice receives a sample from a known probability distribution and needs to transmit a part of a pure quantum state (that is associated with the sample) to Bob. We allow entanglement assistance in the protocol, so that the communication is possible through classical messages, for example using quantum teleportation. The classical messages can have a variable length, and the goal is to minimize their expected length. We provide a characterization of the expected communication cost of this task, by giving a lower bound that is near optimal up to some additive factors. A special case of above task, and the quantum analogue of the source compression problem, is when Alice needs to transmit the whole of her pure quantum state. Here, we show that there is no one-shot interactive scheme which matches the asymptotic and i.i.d. compression rate of the von Neumann entropy of the average quantum state. This is a relatively rare case in the quantum information theory where the cost of a quantum task is significantly different from its classical analogue. Furthermore, we also exhibit similar results for the fully quantum task of quantum state redistribution, employing some different techniques. We show implications for the one-shot version of the problem of quantum channel simulation.
Anurag Anshu, Dave Touchette, Penghui Yao, and Nengkun Yu. 6/19/2017. “Exponential Separation of Quantum Communication and Classical Information.” 49th ACM Symposium on Theory of Computing (STOC) 2017 , Pp. 277–288. Publisher's VersionAbstract
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. As classical information complexity is an upper bound on quantum information complexity, which in turn is equal to amortized quantum communication complexity, our work implies that a tight direct sum result for distributional quantum communication complexity cannot hold. The function we use to present such a separation is the Symmetric k-ary Pointer Jumping function introduced by Rao and Sinha [ECCC TR15-057], whose classical communication complexity is exponentially larger than its classical information complexity. In this paper, we show that the quantum communication complexity of this function is polynomially equivalent to its classical communication complexity. The high-level idea behind our proof is arguably the simplest so far for such an exponential separation between information and communication, driven by a sequence of round-elimination arguments, allowing us to simplify further the approach of Rao and Sinha.As another application of the techniques that we develop, a simple proof for an optimal trade-off between Alice's and Bob's communication is given, even when allowing pre-shared entanglement, while computing the related Greater-Than function on n bits: say Bob communicates at most b bits, then Alice must send n/2O (b) bits to Bob. We also present a classical protocol achieving this bound.
  • QIP 2017 (plenary talk)
Anurag Anshu, Dmitry Gavinsky, Rahul Jain, Srijita Kundu, Troy Lee, Priyanka Mukhopadhyay, Miklos Santha, and Swagato Sanyal. 6/14/2017. “A Composition Theorem for Randomized Query Complexity.” Foundations of Software Technology and Theoretical Computer Science. Publisher's VersionAbstract
Let 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.
Anurag Anshu, Shalev Ben-David, Ankit Garg, Rahul Jain, Robin Kothari, and Troy Lee. 1/1/2017. “Separating quantum communication and approximate rank.” Computational Complexity Conference (CCC) 2017, 79, Pp. 1868-8969. Publisher's VersionAbstract
One 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.
  • QIP 2018 (contributed talk)
Anurag Anshu, Rahul Jain, Priyanka Mukhopadhyay, Ala Shayeghi, and Penghui Yao. 10/10/2016. “New One Shot Quantum Protocols With Application to Communication Complexity.” IEEE Transactions on Information Theory, 62, 2, Pp. 7566 - 7577. Publisher's VersionAbstract
In this paper, we present the following quantum compression protocol `P': Let ρ,σ be quantum states, such that S (ρ∥σ) def = Tr(ρ log ρ - ρ log σ), the relative entropy between ρ and σ, is finite. Alice gets to know the eigendecomposition of ρ. Bob gets to know the eigendecomposition of σ. Both Alice and Bob know S(ρ∥σ) and an error parameter ε. Alice and Bob use shared entanglement and after communication of O((S(ρ∥σ) + 1)/ε 4 ) bits from Alice to Bob, Bob ends up with a quantum state ̃ρ̃, such that F(ρ, ρ̃) ≥ 1-5ε, where F(·) represents fidelity. This result can be considered as a non-commutative generalization of a result due to Braverman and Rao where they considered the special case when ρ and σ are classical probability distributions (or commute with each other) and use shared randomness instead of shared entanglement. We use? to obtain an alternate proof of a direct-sum result for entanglement assisted quantum one-way communication complexity for all relations, which was first shown by Jain et al.. We also present a variant of protocol? in which Bob has some side information about the state with Alice. We show that in such a case, the amount of communication can be further reduced, based on the side information that Bob has. Our second result provides a quantum analog of the widely used classical correlated-sampling protocol. For example, Holenstein used the classical correlated-sampling protocol in his proof of a parallel-repetition theorem for two-player one-round games.
Anurag Anshu, Aleksandrs Belovs, Shalev Ben-David, Mika Goos, Rahul Jain, Robin Kothari, Troy Lee, and Miklos Santha. 10/9/2016. “Separations in communication complexity using cheat sheets and information complexity.” 57th Annual IEEE Symposium on Foundations of Computer Science (FOCS) 2016 , Pp. 555-564. Publisher's VersionAbstract
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.
  • QIP 2017 (contributed talk)

Quantum Shannon theory

Anurag Anshu, Debbie Leung, and Dave Touchette. 11/23/2021. “Incompressibility of Classical Distributions.” IEEE Transactions on Information Theory . Publisher's VersionAbstract
In blind compression of quantum states, a sender Alice is given a specimen of a quantum state rho drawn from a known ensemble (but without knowing what rho is), and she transmits sufficient quantum data to a receiver Bob so that he can decode a near perfect specimen of rho. For many such states drawn iid from the ensemble, the asymptotically achievable rate is the number of qubits required to be transmitted per state. The Holevo information is a lower bound for the achievable rate, and is attained for pure state ensembles, or in the related scenario of entanglement-assisted visible compression of mixed states wherein Alice knows what state is drawn. In this paper, we prove a general and robust lower bound on the achievable rate for ensembles of classical states, which holds even in the least demanding setting when Alice and Bob share free entanglement and a constant per-copy error is allowed. We apply the bound to a specific ensemble of only two states and prove a near-maximal separation (saturating the dimension bound in leading order) between the best achievable rate and the Holevo information for constant error. This also implies that the ensemble is incompressible - compression does not reduce the communication cost by much. Since the states are classical, the observed incompressibility is not fundamentally quantum mechanical. We lower bound the difference between the achievable rate and the Holevo information in terms of quantitative limitations to clone the specimen or to distinguish the two classical states.
Anurag Anshu, Shima Bab Hadiashar, Rahul Jain, Ashwin Nayak, and Dave Touchette. 4/18/2021. “One-shot quantum state redistribution and quantum Markov chains.” IEEE Transactions on Information Theory . Publisher's VersionAbstract
We revisit the task of quantum state redistribution in the one-shot setting, and design a protocol for this task with communication cost in terms of a measure of distance from quantum Markov chains. More precisely, the distance is defined in terms of quantum max-relative entropy and quantum hypothesis testing entropy.Our result is the first to operationally connect quantum state redistribution and quantum Markov chains, and can be interpreted as an operational interpretation for a possible one-shot analogue of quantum conditional mutual information. The communication cost of our protocol is lower than all previously known ones and asymptotically achieves the well-known rate of quantum conditional mutual information. Thus, our work takes a step towards the important open question of near-optimal characterization of the one-shot quantum state redistribution.
  • TQC 2021 and ISIT 2021
Anurag Anshu, Min-Hsiu Hsieh, and Rahul Jain. 12/1/2020. “Noisy quantum state redistribution with promise and the Alpha-bit.” IEEE Transactions on Information Theory, 66, 12, Pp. 7772-7786. Publisher's VersionAbstract
We consider a variation of the well-studied quantum state redistribution task, in which the starting state is known only to the receiver Bob and not to the sender Alice. We refer to this as quantum state redistribution with a one-sided promise. In addition, we consider communication from Alice to Bob over a noisy channel N, instead of the noiseless channel, as is usually considered in state redistribution. We take a natural approach towards the solution of this problem where we “embed” the promise as part of the state and then invoke known protocols for quantum state redistribution composed with known protocols for transfer of quantum information over noisy channels. Using our approach, we are able to reproduce the Alpha-bit capacities with or without entanglement assistance in Hayden and Penington, using known protocols for quantum state redistribution and quantum communication over noisy channels. Furthermore, we generalize the entanglement assisted classical Alpha-bit capacity, showing that any quantum state redistribution protocol can be used as a black box to simulate classical communication.
Anurag Anshu, Masahito Hayashi, and Naqueeb Ahmad Warsi. 11/1/2020. “Secure communication over fully quantum Gel'fand-Pinsker wiretap channel.” IEEE Transactions on Information Theory, 66, 9, Pp. 5548-5566. Publisher's VersionAbstract
In this work we study the problem of secure communication over a fully quantum Gel’fand-Pinsker channel. The best known achievability rate for this channel model in the classical case was proven by Goldfeld, Cuff and Permuter, and here we generalize their result. One key feature of the results obtained in this work is that all the bounds are based on error exponents. We obtain our achievability result via the technique of simultaneous pinching. This in turn allows us to show the existence of a simultaneous decoder. Further, to obtain our encoding technique and to prove the security feature of our coding scheme we prove a bivariate classical-quantum channel resolvability lemma and a conditional classical-quantum channel resolvability lemma. As a byproduct of the achievability result obtained in this work, we also obtain an achievable rate for a fully quantum Gel’fand-Pinsker channel in the absence of Eve. The form of this achievable rate matches with its classical counterpart. The Gel’fand-Pinsker channel model had earlier only been studied for the classical-quantum case and in the case where Alice (the sender) and Bob (the receiver) have shared entanglement between them.
Anurag Anshu, Mario Berta, Rahul Jain, and Marco Tomamichel. 8/1/2020. “Partially smoothed information measures.” IEEE Transactions on Information Theory, 66, 8, Pp. 5022-5036. Publisher's VersionAbstract
Smooth 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.
Farzin Salek, Anurag Anshu, Min-Hsiu Hsieh, Rahul Jain, and Javier Rodríguez Fonollosa. 4/1/2020. “One-shot Capacity bounds on the Simultaneous Transmission of Classical and Quantum Information.” IEEE Transactions on Information Theory, 66, 4, Pp. 2141-2164. Publisher's VersionAbstract
We study the communication capabilities of a quantum channel under the most general channel model known as the one-shot model. Unlike classical channels that can only be used to transmit classical information (bits), a quantum channel can be used for transmission of classical information, quantum information (qubits) and simultaneous transmission of classical and quantum information. In this work, we investigate the one-shot capabilities of a quantum channel for simultaneously transmitting bits and qubits. This problem was studied in the asymptotic regime for a memoryless channel where a regularized characterization of the capacity region was reported. It is known that the transmission of private classical information is closely related to the problem of quantum information transmission. We resort to this idea and find achievable and converse bounds on the simultaneous transmission of the public and private classical information. Then shifting the classical private rate to the quantum information rate leads to a rate region for simultaneous transmission of classical and quantum information. In the case of asymptotic i.i.d. setting, our one-shot result is evaluated to the known results in the literature. Our main tools used in the achievability proofs are position-based decoding and convex-split lemma.
Anurag Anshu and Penghui Yao. 4/1/2020. “On the compression of messages in the multi-party setting.” IEEE Transactions on Information Theory, 66, 4, Pp. 2091-2114. Publisher's VersionAbstract
We consider the following communication task in the multi-party setting, which involves joint random variables X Y Z M N with the property that M is independent of Y Z N conditioned on X, and N is independent of X Z M conditioned on Y . Three parties Alice, Bob and Charlie, respectively, observe samples x, y and z from X Y Z. Alice and Bob communicate messages to Charlie with the goal that Charlie can output a sample (m, n) such that the distribution of (x, y, z, m, n) is close to X Y Z M N. This task reflects the simultaneous message passing communication complexity. Furthermore, it is a generalization of some well studied problems in information theory, such as distributed source coding, source coding with a helper and one sender and one receiver message compression. It is also closely related to the lossy distributed source coding task. Our main result is an achievable communication region for this task in the one-shot setting, through which we obtain a nearly optimal characterization using auxiliary random variables of bounded size. We employ our achievability result to provide a nearly optimal one-shot communication region for the task of lossy distributed source coding, in terms of auxiliary random variables of bounded size. Finally, we show that interactions are necessary to achieve the optimal expected communication cost.
Anurag Anshu, Mario Berta, Rahul Jain, and Marco Tomamichel. 3/18/2020. “Partially smoothed information measures.” IEEE Transactions on Information Theory, 66, 8, Pp. 5022 - 5036. Publisher's VersionAbstract

Smooth 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.

Anurag Anshu, Mario Berta, Rahul Jain, and Marco Tomamichel. 12/4/2019. “A minimax approach to one-shot entropy inequalities.” Journal of Mathematical Physics 60, 60, 12, Pp. 122201. Publisher's VersionAbstract
One-shot information theory entertains a plethora of entropic quantities, such as the smooth max-divergence, hypothesis testing divergence, and information spectrum divergence, that characterize various operational tasks in quantum information theory and are used to analyze their asymptotic behavior. Tight inequalities between these quantities are thus of immediate interest. In this note, we use a minimax approach (appearing previously, for example, in the proofs of the quantum substate theorem), to simplify the quantum problem to a commutative one, which allows us to derive such inequalities. Our derivations are conceptually different from previous arguments and in some cases lead to tighter relations. We hope that the approach discussed here can lead to progress in open problems in quantum Shannon theory and exemplify this by applying it to a simple case of the joint smoothing problem.
Anurag Anshu, Rahul Jain, and Naqueeb Ahmad Warsi. 10/1/2019. “On the near-optimality of one-shot classical communication over quantum channels.” Journal of Mathematical Physics 60, 60, 1, Pp. 012204. Publisher's VersionAbstract
We study the problem of transmission of classical messages through a quantum channel in several network scenarios in the one-shot setting. We consider both the entanglement assisted and unassisted cases for the point to point quantum channel, the quantum multiple-access channel, the quantum channel with a state, and the quantum broadcast channel. We show that it is possible to near-optimally characterize the amount of communication that can be transmitted in these scenarios, using the position-based decoding strategy introduced in a prior study (A. Anshu, R. Jain, and N. Warsi, https://ieee.org/document/8399830). In the process, we provide a short and elementary proof of the converse for entanglement-assisted quantum channel coding in terms of the quantum hypothesis testing divergence [obtained earlier in the work of W. Matthews and S. Wehner, IEEE Trans. Inf. Theory 60, 7317–7329 (2014)]. Our proof has the additional utility that it naturally extends to various network scenarios mentioned above. Furthermore, none of our achievability results require a simultaneous decoding strategy, existence of which is an important open question in quantum Shannon theory.
Anurag Anshu, Rahul Jain, and Naqueeb Ahmad Warsi. 9/1/2019. “Convex-split and hypothesis testing approach to one-shot quantum measurement compression and randomness extraction.” IEEE Transactions on Information Theory, 66, 9, Pp. 5905-5924. Publisher's VersionAbstract
This paper concerns the problem of quantum measurement compression with side information in the one-shot setting with shared-randomness. In this problem, Alice shares a pure quantum state with Bob and the reference system. She performs a measurement on her registers and wishes to communicate the outcome to Bob using shared-randomness and classical communication. The outcome that Bob receives must be correctly correlated with the reference system and his own registers. Our goal is to concurrently minimize the classical communication and shared-randomness cost. The suggested protocol presented in this paper is based on convex-split and position based decoding. The communication is upper bounded in terms of smooth max and hypothesis testing relative entropies. A second protocol addresses the task of strong randomness extraction in the presence of quantum side information. The protocol provides an error guarantee in terms of relative entropy (as opposed to trace distance) and extracts close to the optimal number of uniform bits. As an application, we provide a new achievability result for the task of quantum measurement compression without feedback, in which Alice does not need to know the outcome of the measurement. The result achieves the optimal number of bits communicated and the required number of bits of shared-randomness, for the same task in the asymptotic and i.i.d. setting.
Anurag Anshu, Rahul Jain, and Naqueeb Ahmad Warsi. 4/1/2019. “A hypothesis testing approach for communication over entanglement assisted compound quantum channel.” IEEE Transactions on Information Theory, 65, 4, Pp. 2623-2636. Publisher's VersionAbstract
We study the problem of communication over a compound quantum channel in the presence of entanglement. Classically, such a channel is modeled as a collection of conditional probability distributions wherein neither the sender nor the receiver is aware of the channel being used for transmission, except for the fact that it belongs to this collection. We provide near optimal achievability and converse bounds for this problem in the one-shot quantum setting in terms of the quantum hypothesis testing divergence. We also consider the case of informed sender, showing a one-shot achievability result that converges appropriately in the asymptotic and independent and identically distributed setting. Our achievability proof is similar in spirit to its classical counterpart. To arrive at our result, we use the technique of position-based decoding along with a new approach for constructing a union of two projectors, which might be of independent interest. We give another application of the union of projectors to the problem of testing composite quantum hypotheses.
Anurag Anshu, Rahul Jain, and Naqueeb Ahmad Warsi. 2/1/2019. “Building blocks for communication over noisy quantum networks.” IEEE Transactions on Information Theory 2019, 65, 2, Pp. 1287-1306. Publisher's VersionAbstract
A capacity of a quantum channel characterizes the limits of reliable communication through a noisy quantum channel. This fundamental information-theoretic question is very well studied specially in the setting of many independent uses of the channel. An important scenario, both from practical and conceptual point of view, is when the channel can be used only once. This is known as the one-shot channel coding problem. We provide a tight characterization of the one-shot entanglement-assisted classical capacity of a quantum channel. We arrive at our result by introducing a simple decoding technique which we refer to as position-based decoding. We also consider two other important quantum network scenarios: quantum channel with a jammer and quantum broadcast channel. For these problems, we use the recently introduced convex split technique in addition to position-based decoding. Our approach exhibits that the simultaneous use of these two techniques provides a uniform and conceptually simple framework for designing communication protocols for quantum networks.
  • QIP 2018 (contributed merged talk)
  • Beyond IID 2017 (invited talk)
Anurag Anshu and Rahul Jain. 8/20/2022. “Efficient methods for one-shot quantum communication.” NPJ Quantum Information. Publisher's VersionAbstract
We address the question of efficient implementation of quantum protocols, with small communication and entanglement, and short depth circuit for encoding or decoding. We introduce two methods for this; the first constructs a resource-efficient convex-split lemma and the second adapts the technique of classical correlated sampling in computer science literature. These lead to the following consequences in one-shot quantum information theory. First concerns the task of quantum decoupling, achieved in many previous works with the aid of a random or pseudo-random unitary. We show that given any choice of basis such as the computational basis, decoupling can be achieved by a unitary that takes basis vectors to basis vectors. Thus, the circuit acts in a ‘classical’ manner; furthermore our unitary performs addition and multiplication modulo a prime. As the second consequence, we construct near-optimal communication protocol for quantum channel coding that uses exponentially smaller entanglement than the previous near-optimal protocol.
Anurag Anshu, Min-Hsiu Hsieh, and Rahul Jain. 11/9/2018. “Quantifying Resources in General Resource Theory with Catalysts.” Physical Review Letters, 121, 19, Pp. 190504. Publisher's VersionAbstract
A question that is commonly asked in all areas of physics is how a certain property of a physical system can be used to achieve useful tasks and how to quantify the amount of such a property in a meaningful way. We answer this question by showing that, in a general resource-theoretic framework that allows the use of free states as catalysts, the amount of “resources” contained in a given state, in the asymptotic scenario, is equal to the regularized relative entropy of a resource of that state. While we need to place a few assumptions on our resource-theoretical framework, it is still sufficiently general, and its special cases include quantum resource theories of entanglement, coherence, asymmetry, athermality, nonuniformity, and purity. As a by-product, our result also implies that the amount of noise one has to inject locally to erase all the entanglement contained in an entangled state is equal to the regularized relative entropy of entanglement.
  • QIP 2018 (contributed merged talk)
Anurag Anshu, Rahul Jain, and Naqueeb Ahmad Warsi. 3/1/2018. “A one-shot achievability result for quantum state redistribution.” IEEE Transactions on Information Theory 2018 , 64, 3, Pp. 1425-1435. Publisher's VersionAbstract
We study the problem of entanglement-assisted quantum state redistribution in the one-shot setting and provide a new achievability result on the quantum communication required. Our bounds are in terms of the max-relative entropy and the hypothesis testing relative entropy. We use the techniques of convex split and position-based decoding to arrive at our result. We show that our result is upper bounded by the result obtained in Berta et al. (2016).
  • QIP 2018 (contributed merged talk)
Anurag Anshu, Rahul Jain, and Naqueeb Ahmad Warsi. 3/1/2018. “A generalized quantum Slepian-Wolf.” IEEE Transactions on Information Theory, 64, 3, Pp. 1436-1453. Publisher's VersionAbstract
In this paper, we consider a quantum generalization of the task considered by Slepian and Wolf regarding distributed source compression. In our task, Alice, Bob, Charlie, and Reference share a joint pure state. Alice and Bob wish to send a part of their respective systems to Charlie without collaborating with each other. We give achievability bounds for this task in the one-shot setting and provide the asymptotic and independent identically distributed analysis in the case when there is no side information with Charlie. Our result implies the result of Abeyesinghe et al., who studied a special case of this problem. As another special case wherein Bob holds trivial registers, we recover the result of Devetak and Yard regarding quantum state redistribution.
Anurag Anshu, Vamsi Krishna Devabathini, and Rahul Jain. 11/22/2017. “Quantum communication using coherent rejection sampling.” Physical Review Letters, 119, 12, Pp. 120506. Publisher's VersionAbstract
Compression of a message up to the information it carries is key to many tasks involved in classical and quantum information theory. Schumacher [B. Schumacher, Phys. Rev. A 51, 2738 (1995)] provided one of the first quantum compression schemes and several more general schemes have been developed ever since [M. Horodecki, J. Oppenheim, and A. Winter, Commun. Math. Phys. 269, 107 (2007); I. Devetak and J. Yard, Phys. Rev. Lett. 100, 230501 (2008); A. Abeyesinghe, I. Devetak, P. Hayden, and A. Winter, Proc. R. Soc. A 465, 2537 (2009)]. However, the one-shot characterization of these quantum tasks is still under development, and often lacks a direct connection with analogous classical tasks. Here we show a new technique for the compression of quantum messages with the aid of entanglement. We devise a new tool that we call the convex split lemma, which is a coherent quantum analogue of the widely used rejection sampling procedure in classical communication protocols. As a consequence, we exhibit new explicit protocols with tight communication cost for quantum state merging, quantum state splitting, and quantum state redistribution (up to a certain optimization in the latter case). We also present a port-based teleportation scheme which uses a fewer number of ports in the presence of information about input.
  • Beyond IID 2017 (contributed talk)

Some assorted publications

Anurag Anshu, Peter Hoyer, Mehdi Mhalla, and Simon Perdrix. 2/2/2020. “Contextuality in multipartite pseudo-telepathy graph games.” Journal of Computer and System Sciences, 107, Pp. 156-165. Publisher's VersionAbstract
Analyzing pseudo-telepathy graph games, we propose a way to build contextuality scenarios exhibiting the quantum supremacy using graph states. We consider the combinatorial structures generating equivalent scenarios. We introduce a new tool called multipartiteness width to investigate which scenarios are hard to decompose and show that there exist graphs generating scenarios with a linear multipartiteness width.
Anurag Anshu, Rahul Gangopadhyay, Saswata Shannigrahi, and Satyanarayana Vusirikala. 2/1/2017. “On the rectilinear crossing number of complete uniform hypergraphs.” Computational Geometry, 61, Pp. 38-47. Publisher's VersionAbstract
In this paper, we consider a generalized version of the rectilinear crossing number problem of drawing complete graphs on a plane. The minimum number of crossing pairs of hyperedges in the d-dimensional rectilinear drawing of a d-uniform hypergraph is known as the d-dimensional rectilinear crossing number of the hypergraph. The currently best-known lower bound on the d-dimensional rectilinear crossing number of a complete d-uniform hypergraph with n vertices in general position in ℝd is Ω(2dd√logd)(n2d). In this paper, we improve this lower bound to Ω(2d)(n2d). We also consider the special case when all the vertices of a d-uniform hypergraph are placed on the d-dimensional moment curve. For such complete d-uniform hypergraphs with n vertices, we show that the number of pairwise crossing hyperedges is Θ(4dd√)(n2d).
Anurag Anshu and Saswata Shannigrahi. 8/20/2016. “A lower bound on the crossing number of uniform hypergraphs.” Discrete Applied Mathematics, 209, Pp. 11-15. Publisher's VersionAbstract
In this paper, we consider the embedding of a complete d-uniform geometric hypergraph with n vertices in general position in Rd, 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 contain a common point in the relative interiors 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.
Anurag Anshu and Mehdi Mhalla. 1/1/2013. “Pseudo-telepathy games using graph states.” Quantum Information and Computation, 13, 9-10, Pp. 0833-0845. Publisher's VersionAbstract
We define a family of pseudo-telepathy games using graph states that extends the Mermin games. This family also contains a game used to define a quantum probability distribution that cannot be simulated by any number of PR boxes. We extend this result proving that the probability distribution obtained by the Paley graph state on 13 vertices cannot be simulated by any number of 4-partite non local boxes and that the Paley graph states on more than k222k−2 vertices provides a probability distribution that cannot be simulated by k-partite nonlocal boxes