Publications

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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