Efficient methods for one-shot quantum communication

Abstract

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 new methods to achieve this, the first method involving two new versions of convex-split lemma that use small amount of additional resource (in comparison to prior version) and the second method being inspired by the technique of classical correlated sampling in computer science. These lead to a series of new consequences, as follows. First, we consider the task of quantum decoupling, where the aim is to apply an operation on a n-qubit register so as to make it independent of an inaccessible quantum system. Many previous works achieve decoupling with the aid of a random unitary. It is known that random unitaries can be replaced by random circuits of size O(n\log n) and depth poly(\log n), or unitary 2-designs based on Clifford circuits of similar size and depth. We show that given any choice of basis such as the computational basis, decoupling can be achieved by a unitary that takes basis vectors to basis vectors. Thus, the circuit acts in a `classical' manner and additionally uses O(n) catalytic qubits in maximally mixed quantum state. Our unitary performs addition and multiplication modulo a prime and hence achieves a circuit size of O(n\log n) and logarithmic depth. This shows that the circuit complexity of integer multiplication (modulo a prime) is lower bounded by the optimal circuit complexity of decoupling. Next, we construct a new one-shot entanglement-assisted protocol for quantum channel coding that achieves near-optimal communication through a given channel. The number of qubits of pre-shared entanglement is exponentially smaller than that in the previous protocol near-optimal in communication. We also achieve similar results for one-shot quantum state redistribution.

arXiv commentversion 2, 46 pages, 3 Figures. Title changed and material reorganized. Highlighted connection with integer multiplication

References in corpus (53)

• Quantum cryptography: Public key distribution and coin tossing
• Quantum state transfer and entanglement distribution among distant nodes in a quantum network
• Satellite-to-ground quantum key distribution
• Quantum Coherence as a Resource
• Average Entropy of a Subsystem
• Black holes as mirrors: quantum information in random subsystems
• The capacity of the noisy quantum channel
• Large Scale Modular Quantum Computer Architecture with Atomic Memory and Photonic Interconnects
• Exact and Approximate Unitary 2-Designs: Constructions and Applications
• Quantum mechanical evolution towards thermal equilibrium
• On the quantum, classical and total amount of correlations in a quantum state
• All photonic quantum repeaters
• Quantum information can be negative
• Min- and Max- Relative Entropies and a New Entanglement Monotone
• The thermodynamic meaning of negative entropy
• Towards the fast scrambling conjecture
• Quantum Data Hiding
• Quantum state merging and negative information
• The mother of all protocols: Restructuring quantum information's family tree
• Quantum Reverse Shannon Theorem
• The Quantum Reverse Shannon Theorem based on One-Shot Information Theory
• A decoupling approach to the quantum capacity
• Trevisan's extractor in the presence of quantum side information
• Embezzling Entangled Quantum States
• Optimal quantum source coding with quantum information at the encoder and decoder
• Finite blocklength converse bounds for quantum channels
• Decoupling with random quantum circuits
• One shot entanglement assisted classical and quantum communication over noisy quantum channels: A hypothesis testing and convex split approach
• Quantum message compression with applications
• A father protocol for quantum broadcast channels
• Unconditionally Secure Key Distribution In Higher Dimensions By Depolarization
• Quantifying resource in catalytic resource theory
• Decoupling with unitary approximate two-designs
• On the Second-Order Asymptotics for Entanglement-Assisted Communication
• One-shot entanglement-assisted quantum and classical communication
• Quantum wiretap channel with non-uniform random number and its exponent and equivocation rate of leaked information
• Security of quantum key distribution with intensity correlations
• Catalytic Decoupling of Quantum Information
• Smooth Entropy Bounds on One-Shot Quantum State Redistribution
• Quantum to Classical Randomness Extractors
• Disentanglement Cost of Quantum States
• An upper bound on the second order asymptotic expansion for the quantum communication cost of state redistribution
• Convex-split and hypothesis testing approach to one-shot quantum measurement compression and randomness extraction
• Quantum entropic security and approximate quantum encryption
• A one-shot achievability result for quantum state redistribution
• A decoupling approach to classical data transmission over quantum channels
• On the near-optimality of one-shot classical communication over quantum channels
• Quantum Side Information: Uncertainty Relations, Extractors, Channel Simulations
• Near-linear constructions of exact unitary 2-designs
• Decoupling with random diagonal unitaries
• New one shot quantum protocols with application to communication complexity
• Small Pseudo-Random Families of Matrices: Derandomizing Approximate Quantum Encryption
• Expected communication cost of distributed quantum tasks

Cited by in corpus (7)

• One-shot quantum state redistribution and quantum Markov chains
• Teleportation with Embezzling Catalysts
• One-Shot Triple-Resource Trade-Off in Quantum Channel Coding
• Communication with Quantum Catalysts
• The coherent measurement cost of coherence distillation
• Intersection and union of subspaces with applications to communication over authenticated classical-quantum channels and composite hypothesis testing
• On the Entanglement Cost of One-Shot Compression