We study classical string commitment over quantum channels with limited preshared entanglement. For noninteractive protocols, we determine the commitment capacity of a class of channels with input dimension $d$ that, at each use, sample a pair of classical random variables $(F,Z)$, apply one of the $d^2$ Heisenberg--Weyl operators indexed by $Z$ to the input, and deliver the transformed quantum system together with $F$ to the receiver. If $E$ is the available entanglement rate in bits per channel use, then the capacity is $\min\{H(Z|F),\log_2d+E\}$. This class of channels encompasses quantum erasure and depolarizing channels, as well as families of Pauli channels. Additionally, for interactive protocols, we show that the commitment rate cannot exceed $\log_2d+E$ bits per channel use, so that when $H(Z|F)\geq\log_2d+E$, interactive communication does not increase the capacity. As a consequence, for interactive protocols, we determine the capacity of the quantum erasure channel.
We study the complexity of quantum decomposable randomized encodings (QDRE). We establish a bi-directional connection between the QDRE model and the communication complexity model of quantum private simultaneous message protocols (QPSM), where classical communication is free, and quantum communication is the primary complexity measure. We show the following upper and lower bounds. (1) For every quantum channel mapping $n$ to $m$ qubits, we give a QPSM protocol with quantum communication $m$, using exponential pre-shared entanglement. In particular, constant-output channels have $O(1)$ quantum communication, and classical-output channels require no quantum communication. (2) With $O(n)$ pre-shared entanglement, every one-qubit-output channel has an $O(n)$-quantum-communication QPSM protocol. Conversely, there exists a channel and a constant $c>0$ for which any protocol with at most $cn$ pre-shared entanglement requires $\Omega(n)$ quantum communication. (3) In contrast, we identify a structured class of quantum channels, Clifford-induced channels, for which there exist QPSM protocols with $O(n)$ pre-shared entangled qubits and only $O(1)$ quantum communication complexity. Through our connection, we obtain analogous upper and lower bounds on the quantum encoding size of QDRE. Our results show that the amount of pre-shared entanglement plays a central role in quantum encoding size and quantum communication complexity.
Quantum channels can be characterized by their action on an orthogonal operator basis, where these operators are related to observable properties of the quantum system. For qudit and multimode bosonic systems, this is encoded respectively in the Heisenberg--Weyl transfer matrix estimated from the Choi-state, and in the characteristic-function transfer map estimated from a two-mode squeezed vacuum based Choi-state. We derive sample-complexity bounds for estimating entries of the transfer matrix/map to additive accuracy $\epsilon$ with success probability $\ge1-\delta$, under different resources: access to the complex-conjugate channel $\mathcal{E}^*$ and/or parallel access to $c$ copies. In all settings, the learner uses parallel channel calls with adaptively chosen, ancilla-assisted input states and measurements. Absolute values of transfer-matrix entries can be learned efficiently with simultaneous access to $\mathcal{E}$ and $\mathcal{E}^*$, with tight scaling $\epsilon^{-4}$. Without conjugate access, any $c<d$ copies are insufficient for efficient learning, requiring sample complexity exponential in the number of ($d$-level) qudits $n$ (for prime $d$). Efficiency is recovered at $c=d$, with tight scaling $\epsilon^{-2d}$. For bosonic systems, exponential sample complexity holds in terms of an effective dimension induced by an energy constraint for all $c=O(1/\epsilon)$. Although the task is learning a particular state, these bounds carry stronger implications than standard state-learning bounds since the learner controls the inputs and has ancillary assistance. This establishes a hierarchy of channel-learning resources: self-complex-conjugate channels require two-copy ancilla-assisted access for efficient learning, while for every square-free $d$, some channels require $d$-copy access. As a corollary, we derive tighter lower bounds for state learning with limited multi-copy access.
M. Subramanian, Hyukgun Kwon, Liang Jiang· 0 citations
The Simultaneous Message Passing (SMP) model provides a fundamental framework for comparing classical and quantum communication. For two players, Gavinsky et al. (STOC 2006) established a separation underlying the incomparability of shared randomness and quantum communication: \textsc{Index Coordination} needs $O(\log n)$ public-coin bits but $\Omega(n^{1/3})$ bounded-error qubits. In this work, we establish a multiparty exponential separation through $\operatorname{IC}_{k,n}$, a natural $k$-party generalization of \textsc{Index Coordination}. Public-coin protocols solve it unambiguously with maximum message length $O(\log n)$ bits. In contrast, quantum SMP protocols without shared entanglement or public coins require maximum message length $\Omega(n^{1-1/k})$ qubits in the unambiguous regime and $\Omega(n^{(k-1)/(k+1)})$ qubits in the bounded-error regime. A classical private-coin protocol matches the unambiguous bound, so quantum communication provides no asymptotic advantage over private randomness in this regime. For fixed error parameters, all constants are independent of $k$, establishing the exponential separation for every integer-valued function $k=k(n)\ge2$, without restricting its growth. Both quantum lower bounds become $\Omega(n)$ when $k\ge c\log n$ for any fixed $c>0$, matching the full-input protocol and yielding tight linear complexity in both regimes. Our results demonstrate that quantum superposition cannot efficiently simulate the coordination afforded by public randomness, extending this separation to arbitrary $k$. To bound success probabilities for multiparty product states, we prove an exact factorization theorem for unambiguous quantum state identification, which may be of independent mathematical interest.
Pedro Montealegre, I. Rapaport, Jorge Valenzuela· 0 citations
We introduce a framework for distributed quantum inference under communication constraints. In our model, $m$ distributed nodes each receive one copy of an unknown $d$-dimensional quantum state $\rho$, before communicating via a constrained one-way communication channel with a central node, which aims to infer some property of $\rho$. This framework generalizes the classical distributed inference framework introduced by Acharya, Canonne, and Tyagi [COLT 2019], by allowing quantum resources such as quantum communication and shared entanglement. Within this setting, we focus on the fundamental problem of quantum state certification: Given a complete description of some state $\sigma$, decide whether $\rho=\sigma$ or $\|\rho-\sigma\|_1\geq \epsilon$. Additionally, we focus on the case of limited communication between distributed nodes and the central node: we assume each communication channel is limited to only $n_c$ bits and $n_q$ qubits with $n_c + n_q \leq \log d$. When all nodes can make use of a shared source of randomness, we show that the copy complexity of distributed state certification is $\Theta(\frac{d^2}{2^{n_q} 2^{n_c/2}\epsilon^2})$. We further demonstrate that shared randomness is necessary to achieve the above complexity, by proving an $\Omega(\frac{d^3}{4^{n_q} 2^{n_c} \epsilon^2})$ lower bound in the $\textit{private-coin}$ setting. Moreover, we develop a private-coin algorithm that matches this bound up to a $\sqrt{\log d}$ factor, showing this complexity is near-optimal. Together, our work establishes a general framework for distributed quantum inference with communication constraints and characterizes the complexity of distributed state certification with limited communication.
Kenny Chen, Mina Doosti, R. Sweke et al.· 0 citations
We introduce a measure of information loss for any quantum process that may be modeled by a prepare-evolve-measure scenario: Alice prepares an ensemble of states that gets sent via a quantum channel to Bob, who then measures the output. As a quantum channel models open system dynamics, our measure of information loss quantifies Bob's inability to retrodict with certainty which state Alice sent through the channel. By minimizing this measure over all possible pure state ensemble decompositions of a fixed state $\rho$, and over all POVMs on the output of a channel $\mathcal{E}$, we arrive at an intrinsic notion of information loss for any state-channel pair $(\rho,\mathcal{E})$. We show that the vanishing of information loss with respect to all states supported on a fixed codespace $\mathcal{H}_{\text{code}}$ is equivalent to a condition we term \emph{universal pristineness}, which ensures that orthogonal pure states in $\mathcal{H}_{\text{code}}$ get sent via the channel $\mathcal{E}$ to possibly mixed states whose supports are orthogonal. Moreover, we prove universal pristineness is equivalent to the Knill-Laflamme conditions in quantum error correction, which are necessary and sufficient for the existence of a perfect recovery channel for all states supported on $\mathcal{H}_{\text{code}}$. As an application, we apply our framework to the Hayden-Preskill model of black hole evaporation, demonstrating that the evaporation channel becomes asymptotically universally pristine, thereby providing a purely channel-theoretic formulation of Page-time information retrieval.
James Fullwood, Wu-Zhong Guo, Boyu Yang· 0 citations
In this work, we define entanglement-assisted quantum locally recoverable codes with availability, in which any set of up to $\delta-1$ erased qudits can be recovered from any one of $t$ local recovery sets, each of size at most $r+\delta-1$, with the recovery sets intersecting exactly in the erased coordinates, where $r$ is a (small) positive integer. We show that shared entanglement permits $t>1$, meaning that multiple local recovery sets can be available for the same set of up to $\delta-1$ erasures. We establish a Singleton-like bound for this family of codes and present random constructions based on classical linear codes with Vandermonde parity-check matrices. We also provide explicit constructions of entanglement-assisted quantum locally recoverable codes with availability from several classical code families and their folded versions, including Tamo-Barg codes, fiber-product codes, and algebraic-geometry codes such as one-point Hermitian and Suzuki codes.
Rutuja Kshirsagar, Gretchen L. Matthews, Julia Shapiro· 1 citation· ⚡1
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.
