Person:

Anshu, Anurag

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.

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

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 in [Goldfeld, Cuff, Permuter, 2016]. We generalize the result of [Goldfeld, Cuff, Permuter, 2016]. One key feature of the results obtained in this work is that all the bounds obtained are in terms of error exponent. 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 by product 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.

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

In 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).

Quantum entanglement and coherence are two fundamental resources for quantum information processing. Recent results clearly demonstrate their relevance in quantum technological tasks, including quantum communication and quantum algorithms. In this Letter we study the role of quantum coherence for quantum state redistribution, a fundamental task where two parties aim to relocate a quantum particle by using a limited amount of quantum communication and shared entanglement. We provide general bounds for the resource rates required for this process, and show that these bounds are tight under additional reasonable constraints, including the situation where the receiving party cannot use local coherence. While entanglement cannot be directly converted into local coherence in our setting, we show that entanglement is still useful for local coherence creation if an additional quantum channel is provided, and the optimal protocol for local coherence creation for any given amount of quantum communication and shared entanglement is presented. We also discuss possible extensions of our methods to other scenarios where the receiving party is limited by local constraints, including theories of thermodynamics and asymmetry.

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.

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.

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 Göös, 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.

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 and are used to prove the asymptotic behavior of various tasks in quantum information theory. 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.