Quantum complexity theory

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

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

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

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

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

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

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