167 citations · 877 across the 14 of their papers we have counts for
14 papers
Quantum enhancement of randomness distribution
Raul Garcia-Patron, William Matthews, Andreas Winter
The capability of a given channel to communicate information is, a priori, distinct from its capability to distribute shared randomness. In this article we define randomness distri…
Unbounded number of channel uses are required to see quantum capacity
Toby Cubitt, David Elkouss, William Matthews +3
Transmitting data reliably over noisy communication channels is one of the most important applications of information theory, and well understood when the channel is accurately mod…
On the power of PPT-preserving and non-signalling codes
Debbie Leung, William Matthews
We derive one-shot upper bounds for quantum noisy channel codes. We do so by regarding a channel code as a bipartite operation with an encoder belonging to the sender and a decoder…
Finite blocklength converse bounds for quantum channels
William Matthews, Stephanie Wehner
We derive upper bounds on the rate of transmission of classical information over quantum channels by block codes with a given blocklength and error probability, for both entangleme…
A linear program for the finite block length converse of Polyanskiy-Poor-Verdú via non-signalling codes
William Matthews
Motivated by recent work on entanglement-assisted codes for sending messages over classical channels, the larger, easily characterised class of non-signalling codes is defined. Ana…
A Satisfiability Algorithm for AC
Russell Impagliazzo, William Matthews, Ramamohan Paturi
We consider the problem of efficiently enumerating the satisfying assignments to $\AC^0$ circuits. We give a zero-error randomized algorithm which takes an $\AC^0$ circuit as input…