The famous superdense coding protocol of Bennett and Wiesner demonstrates that it is possible to communicate two bits of classical information by sending only one qubit and using a shared EPR pair. Our first result is that an arbitrary protocol for a
chieving this task (where there are no assumptions on the senders encoding operations or the dimension of the shared entangled state) are locally equivalent to the canonical Bennett-Wiesner protocol. In other words, the superdense coding task is rigid. In particular, we show that the sender and receiver only use additional entanglement (beyond the EPR pair) as a source of classical randomness. We then explore whether higher-dimensional superdense coding, where the goal is to communicate one of $d^2$ possible messages by sending a $d$-dimensional quantum state, is rigid for all $d geq 2$. We conjecture that $d$-dimensional superdense coding is rigid up to the choice of orthogonal unitary bases, and present concrete constructions of inequivalent unitary bases for all $d > 2$. Finally, we analyze the performance of superdense coding protocols where the encoding operators are independently sampled from the Haar measure on the unitary group. Our analysis involves bounding the distinguishability of random maximally entangled states, which may be of independent interest.
We present a garbling scheme for quantum circuits, thus achieving a decomposable randomized encoding scheme for quantum computation. Specifically, we show how to compute an encoding of a given quantum circuit and quantum input, from which it is possi
ble to derive the output of the computation and nothing else. In the classical setting, garbled circuits (and randomized encodings in general) are a versatile cryptographic tool with many applications such as secure multiparty computation, delegated computation, depth-reduction of cryptographic primitives, complexity lower-bounds, and more. However, a quantum analogue for garbling general circuits was not known prior to this work. We hope that our quantum randomized encoding scheme can similarly be useful for applications in quantum computing and cryptography. To illustrate the usefulness of quantum randomized encoding, we use it to design a conceptually-simple zero-knowledge (ZK) proof system for the complexity class $mathbf{QMA}$. Our protocol has the so-called $Sigma$ format with a single-bit challenge, and allows the inputs to be delayed to the last round. The only previously-known ZK $Sigma$-protocol for $mathbf{QMA}$ is due to Broadbent and Grilo (FOCS 2020), which does not have the aforementioned properties.
We propose a learning model called the quantum statistical learning QSQ model, which extends the SQ learning model introduced by Kearns to the quantum setting. Our model can be also seen as a restriction of the quantum PAC learning model: here, the l
earner does not have direct access to quantum examples, but can only obtain estimates of measurement statistics on them. Theoretically, this model provides a simple yet expressive setting to explore the power of quantum examples in machine learning. From a practical perspective, since simpler operations are required, learning algorithms in the QSQ model are more feasible for implementation on near-term quantum devices. We prove a number of results about the QSQ learning model. We first show that parity functions, (log n)-juntas and polynomial-sized DNF formulas are efficiently learnable in the QSQ model, in contrast to the classical setting where these problems are provably hard. This implies that many of the advantages of quantum PAC learning can be realized even in the more restricted quantum SQ learning model. It is well-known that weak statistical query dimension, denoted by WSQDIM(C), characterizes the complexity of learning a concept class C in the classical SQ model. We show that log(WSQDIM(C)) is a lower bound on the complexity of QSQ learning, and furthermore it is tight for certain concept classes C. Additionally, we show that this quantity provides strong lower bounds for the small-bias quantum communication model under product distributions. Finally, we introduce the notion of private quantum PAC learning, in which a quantum PAC learner is required to be differentially private. We show that learnability in the QSQ model implies learnability in the quantum private PAC model. Additionally, we show that in the private PAC learning setting, the classical and quantum sample complexities are equal, up to constant factors.
We give a simple proof of the exponential de Finetti theorem due to Renner. Like Renners proof, ours combines the post-selection de Finetti theorem, the Gentle Measurement lemma, and the Chernoff bound, but avoids virtually all calculations, including any use of the theory of types.
The behavior of games repeated in parallel, when played with quantumly entangled players, has received much attention in recent years. Quantum analogues of Razs classical parallel repetition theorem have been proved for many special classes of games.
However, for general entangled games no parallel repetition theorem was known. We prove that the entangled value of a two-player game $G$ repeated $n$ times in parallel is at most $c_G n^{-1/4} log n$ for a constant $c_G$ depending on $G$, provided that the entangled value of $G$ is less than 1. In particular, this gives the first proof that the entangled value of a parallel repeated game must converge to 0 for all games whose entangled value is less than 1. Central to our proof is a combination of both classical and quantum correlated sampling.
We introduce a simple transformation on two-player nonlocal games, called anchoring, and prove an exponential-decay parallel repetition theorem for all anchored games in the setting of quantum entangled players. This transformation is inspired in par
t by the Feige-Kilian transformation (SICOMP 2000), and has the property that if the quantum value of the original game $G$ is $v$ then the quantum value of the anchored game $G_bot$ is $1 - (1 - alpha)^2 cdot (1 - v)$ where $alpha$ is a parameter of the transformation. In particular the anchored game has quantum value $1$ if and only if the original game $G$ has quantum value $1$. This provides the first gap amplification technique for general two-player nonlocal games that achieves exponential decay of the quantum value.
The problem of distinguishing between a random function and a random permutation on a domain of size $N$ is important in theoretical cryptography, where the security of many primitives depend on the problems hardness. We study the quantum query compl
exity of this problem, and show that any quantum algorithm that solves this problem with bounded error must make $Omega(N^{1/5}/log N)$ queries to the input function. Our lower bound proof uses a combination of the Collision Problem lower bound and Ambainiss adversary theorem.
A recent sequence of works, initially motivated by the study of the nonlocal properties of entanglement, demonstrate that a source of information-theoretically certified randomness can be constructed based only on two simple assumptions: the prior ex
istence of a short random seed and the ability to ensure that two black-box devices do not communicate (i.e. are non-signaling). We call protocols achieving such certified amplification of a short random seed randomness amplifiers. We introduce a simple framework in which we initiate the systematic study of the possibilities and limitations of randomness amplifiers. Our main results include a new, improved analysis of a robust randomness amplifier with exponential expansion, as well as the first upper bounds on the maximum expansion achievable by a broad class of randomness amplifiers. In particular, we show that non-adaptive randomness amplifiers that are robust to noise cannot achieve more than doubly exponential expansion. Finally, we show that a wide class of protocols based on the use of the CHSH game can only lead to (singly) exponential expansion if adversarial devices are allowed the full power of non-signaling strategies. Our upper bound results apply to all known non-adaptive randomness amplifier constructions to date.
