@conference {2129, title = {Capacity Approaching Codes for Low Noise Interactive Quantum Communication}, booktitle = {Annual ACM Symposium on the Theory of Computing STOC 2018}, year = {2018}, month = {2018/01/01}, abstract = {
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\&$\#$39;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\&$\#$39;14] for low $\epsilon$.
}, url = {http://acm-stoc.org/stoc2018/STOC-2018-Accepted.html}, author = {Debbie Leung and Ashwin Nayak and Ala Shayeghi and Dave Touchette and Penghui Yao and Nengkun Yu} } @article {1244, title = {A framework for bounding nonlocality of state discrimination}, journal = {Communications in Mathematical Physics}, volume = {323}, year = {2013}, month = {2013/9/4}, pages = {1121 - 1153}, abstract = { We consider the class of protocols that can be implemented by local quantum operations and classical communication (LOCC) between two parties. In particular, we focus on the task of discriminating a known set of quantum states by LOCC. Building on the work in the paper "Quantum nonlocality without entanglement" [BDF+99], we provide a framework for bounding the amount of nonlocality in a given set of bipartite quantum states in terms of a lower bound on the probability of error in any LOCC discrimination protocol. We apply our framework to an orthonormal product basis known as the domino states and obtain an alternative and simplified proof that quantifies its nonlocality. We generalize this result for similar bases in larger dimensions, as well as the "rotated" domino states, resolving a long-standing open question [BDF+99]. }, doi = {10.1007/s00220-013-1784-0}, url = {http://arxiv.org/abs/1206.5822v1}, author = {Andrew M. Childs and Debbie Leung and Laura Mancinska and Maris Ozols} } @article {1246, title = {Interpolatability distinguishes LOCC from separable von Neumann measurements}, journal = {Journal of Mathematical Physics}, volume = {54}, year = {2013}, month = {2013/06/25}, pages = {112204}, abstract = { Local operations with classical communication (LOCC) and separable operations are two classes of quantum operations that play key roles in the study of quantum entanglement. Separable operations are strictly more powerful than LOCC, but no simple explanation of this phenomenon is known. We show that, in the case of von Neumann measurements, the ability to interpolate measurements is an operational principle that sets apart LOCC and separable operations. }, doi = {10.1063/1.4830335}, url = {http://arxiv.org/abs/1306.5992v1}, author = {Andrew M. Childs and Debbie Leung and Laura Mancinska and Maris Ozols} } @article {1242, title = {Characterization of universal two-qubit Hamiltonians}, year = {2010}, month = {2010/04/09}, abstract = { Suppose we can apply a given 2-qubit Hamiltonian H to any (ordered) pair of qubits. We say H is n-universal if it can be used to approximate any unitary operation on n qubits. While it is well known that almost any 2-qubit Hamiltonian is 2-universal (Deutsch, Barenco, Ekert 1995; Lloyd 1995), an explicit characterization of the set of non-universal 2-qubit Hamiltonians has been elusive. Our main result is a complete characterization of 2-non-universal 2-qubit Hamiltonians. In particular, there are three ways that a 2-qubit Hamiltonian H can fail to be universal: (1) H shares an eigenvector with the gate that swaps two qubits, (2) H acts on the two qubits independently (in any of a certain family of bases), or (3) H has zero trace. A 2-non-universal 2-qubit Hamiltonian can still be n-universal for some n >= 3. We give some partial results on 3-universality. Finally, we also show how our characterization of 2-universal Hamiltonians implies the well-known result that almost any 2-qubit unitary is universal. }, url = {http://arxiv.org/abs/1004.1645v2}, author = {Andrew M. Childs and Debbie Leung and Laura Mancinska and Maris Ozols} }