  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.
