We consider the problem of implementing two-party interactive quantum

communication over noisy channels, a necessary endeavor if we wish to

fully reap quantum advantages for communication.

For an arbitrary protocol with n messages, designed for

noiseless qudit channels, our main result is a simulation method that fails with probability less than

$2^{-\Theta(n\epsilon)}$ and uses a qudit channel $n(1 + \Theta

(\sqrt{\epsilon}))$ times, of which an $\epsilon$ fraction can be

corrupted adversarially.

The simulation is thus capacity achieving to leading order, and

we conjecture that it is optimal up to a constant factor in

the $\sqrt{\epsilon}$ term.

Furthermore, the simulation is in a model that does not require

pre-shared resources such as randomness or entanglement between the

communicating parties.

Surprisingly, this outperforms the best-known overhead of $1 +

O(\sqrt{\epsilon \log \log 1/\epsilon})$ in the corresponding

\emph{classical} model, which is also conjectured to be optimal

[Haeupler, FOCS'14].

Our work also improves over the best previously known quantum result

where the overhead is a non-explicit large constant [Brassard \emph{et

al.}, FOCS'14] for low $\epsilon$.

%B Annual ACM Symposium on the Theory of Computing STOC 2018
%8 2018/01/01
%G eng
%U http://acm-stoc.org/stoc2018/STOC-2018-Accepted.html
%0 Journal Article
%J Physical Review Letters
%D 2017
%T Quantum state tomography via reduced density matrices
%A Tao Xin
%A Dawei Lu
%A Joel Klassen
%A Nengkun Yu
%A Zhengfeng Ji
%A Jianxin Chen
%A Xian Ma
%A Guilu Long
%A Bei Zeng
%A Raymond Laflamme
%X Quantum state tomography via local measurements is an efficient tool for characterizing quantum states. However it requires that the original global state be uniquely determined (UD) by its local reduced density matrices (RDMs). In this work we demonstrate for the first time a class of states that are UD by their RDMs under the assumption that the global state is pure, but fail to be UD in the absence of that assumption. This discovery allows us to classify quantum states according to their UD properties, with the requirement that each class be treated distinctly in the practice of simplifying quantum state tomography. Additionally we experimentally test the feasibility and stability of performing quantum state tomography via the measurement of local RDMs for each class. These theoretical and experimental results advance the project of performing efficient and accurate quantum state tomography in practice.

%B Physical Review Letters %V 118 %P 020401 %8 2017/01/09 %G eng %U http://journals.aps.org/prl/abstract/10.1103/PhysRevLett.118.020401 %R 10.1103/PhysRevLett.118.020401 %0 Journal Article %J Physical Review A %D 2016 %T Detecting Consistency of Overlapping Quantum Marginals by Separability %A Jianxin Chen %A Zhengfeng Ji %A Nengkun Yu %A Bei Zeng %X The quantum marginal problem asks whether a set of given density matrices are consistent, i.e., whether they can be the reduced density matrices of a global quantum state. Not many non-trivial analytic necessary (or sufficient) conditions are known for the problem in general. We propose a method to detect consistency of overlapping quantum marginals by considering the separability of some derived states. Our method works well for the $k$-symmetric extension problem in general, and for the general overlapping marginal problems in some cases. Our work is, in some sense, the converse to the well-known $k$-symmetric extension criterion for separability. %B Physical Review A %V 93 %P 032105 %8 2016/03/03 %G eng %U http://arxiv.org/abs/1509.06591 %N 3 %R 10.1103/PhysRevA.93.032105 %0 Conference Paper %B 20th Annual Conference on Quantum Information Processing (QIP) %D 2016 %T Exponential Separation of Quantum Communication and Classical Information %A Anurag Anshu %A Dave Touchette %A Penghui Yao %A Nengkun Yu %XWe 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, we give a simple proof for an optimal trade-off between Alice's and Bob's communication while computing the related Greater-Than function on n bits: say Bob communicates at most b bits, then Alice must send n/exp(O(b)) bits to Bob. This holds even when allowing pre-shared entanglement. We also present a classical protocol achieving this bound.