Classical-Quantum Channel Resolvability Using Matrix Multiplicative Weight Update Algorithm

Koki Takahashi, Shun Watanabe · 2026

Read Classical-Quantum Channel Resolvability Using Matrix Multiplicative Weight Update Algorithm by Koki Takahashi, Shun Watanabe (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2601-12230.txt.

Introduction

Koki Takahashi and Shun Watanabe prove channel resolvability for classical-quantum channels by a set code method. Resolvability asks how well random noise can mimic a channel output. Past proofs for such channels used random coding alone.

Their past work gave a deterministic proof for classic channels via multiplicative weights. They extend that route with a matrix form of the weights method. A set code is easier to build and audit than a random one. The result adds a firm tool to quantum information theory. A set proof is a step past random code proofs.

Catalog record

CREATORKoki Takahashi, Shun Watanabe
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE28 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2601-12230

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Classical-Quantum Channel Resolvability Using Matrix Multiplicative Weight Update Algorithm Koki Takahashi, Shun Watanabe Abstract We study classical-quantum (C-Q) channel resolvability. C-Q channel resolvability has been proved by only random coding in the literature. In our previous study, we proved channel resolvability by deterministic coding, using multiplicative weight update algorithm. We extend this approach to C-Q channels and prove C-Q channel resolvability by deterministic coding, using the matrix multiplicative weight update algorithm. This is the first approach to C-Q channel resolvability using deterministic coding. I Introduction Shannon introduced random coding to prove channel coding [ 24 ] . Random coding is the most widely used approach in information theory. Feinstein also proved channel coding by maximal code construction [ 15 ] . Feinstein’s deterministic coding approach has intensified our understanding of the channel coding as seen in [ 6 , 8 , 12 , 17 , 23 , 29 ] . Han and Verdu introduced channel resolvability [ 18 ] , which plays a key role in proving the strong converse for identification via channels [ 2 ] . Ahlswede also presented an alternative proof of its strong converse later [ 1 ] . Ahlswede and Winter proved strong converse for identification via classical-quantum (C-Q) channels [ 3 ] by implicitly proving the achievability of C-Q channel resolvability. The result in [ 3 ] has been used to prove the wiretap capacity of quantum channels [ 14 , 9 ] and the quantum capacity of quantum channels [ 14 ] . Thus, C-Q channel resolvability can play an important role in studying quantum information theory. To the best of our knowledge, C-Q channel resolvability has been constructed by only random coding. Our previous study showed that, for channel resolvability of classical channels, deterministic coding constructed by the multiplicative weight update (MWU) algorithm achieves the channel capacity [ 26 ] . In this paper, we extend the result in [ 26 ] to C-Q channels. More specifically, we show that, for C-Q channel resolvability, deterministic coding constructed by the matrix MWU (MMWU) algorithm achieves the Holevo capacity. The MMWU algorithm is a widely used algorithm for game theory and learning theory in quantum computing, and it approximately finds a certain minmax value of a two-player game [ 5 ] . By interpreting C-Q channel resolvability as a two-player game, we apply the MMWU algorithm. The key point is that Ahlswede and Winter used quantum hypergraph soft covering to prove C-Q channel resolvability. Instead of the quantum Chernoff bound used in [ 3 ] , we apply the MMWU algorithm to solve quantum hypergraph soft covering. Our proof is inspired by Kale’s thesis that the MMWU algorithm solves quantum hypergraph covering [ 21 ] ; however, there are technical difficulties inherent in soft covering. In recent study, refined analysis of C-Q channel resolvability and soft covering for random coding has been studied in [ 25 , 10 , 20 , 19 , 4 , 11 , 7 , 22 ] . In addition, universal C-Q channel resolvability has been proposed in [ 22 ] ; however the expander code used in [ 22 ] is constructed by random coding. Notation: Throughout the paper, e is Napier’s constant and the base of the natural logarithm is e . Finite alphabet sets (e.g. \mathcal{X} ), Hilbert space (e.g. \mathcal{H} ) and set of density matrices of given Hilbert space (e.g. \mathcal{S(H)} ) are denoted by calligraphic letters. The cardinality and dimension are denoted by \mathcal{|X|},\dim\mathcal{H} respectively. The set of all distributions on \mathcal{X} is denoted by \mathcal{P(X)} . For a Hermitian matrix A , the generalize inverse A^{-1} is defined such that the eigenvalues are inverse of nonzero eigenvalues of A ; see also [ 28 , Definition 3.3.1] . II Problem formulation of C-Q channel resolvability Let W:\mathcal{X}\rightarrow\mathcal{S(H)} be a C-Q channel that maps each input x to a quantum state W_{x} on the output Hilbert space \mathcal{H} . Given an input distribution p\in{\cal P(X)}, the goal is to simulate the output quantum state W_{p}:=\sum_{{x}\in{\cal X}}p(x)W_{x}. Let {\cal C}=\{{x}_{1},{x}_{2},...,x_{L}\} be a codebook of size L . Define W_{{\cal C}} as the output mixed state induced by selecting a codeword uniformly at random from codebook {\cal C} and passing the codeword through the C-Q channel, i.e., W_{{\cal C}}:=\frac{1}{L}\sum_{l=1}^{L}W_{x_{l}}. The problem is how to construct a codebook {\cal C} such that the output state W_{\mathcal{C}} simulates the output state W_{p} . A simulation error is measured by the trace distance: d_{\mathrm{tr}}(W_{p},W_{{\cal C}}):=\frac{1}{2}\|W_{p}-W_{{\cal C}}\|_{1}, where \|A\|_{1} is trace norm of matrix A . We shall make a codebook {\cal C} such that, for an arbitrary small \xi , the trace distance d_{\mathrm{tr}}(W_{p},W_{{\cal C}}) is less than \xi, with codebook size L as small as possible. For the asymptotic setting of discrete memoryless C-Q channel W and the worst input distribution, the optimal rate for C-Q channel resolvability is given by the Holevo capacity C(W) . Our paper achieves this result using deterministic coding in Theorem 12 . III Matrix multiplicative weight algorithm In this section, we review the MMWU algorithm in notations that are compatible with C-Q channel resolvability. We consider an L rounds game between {\cal X} -player and {\cal H} -player with a quantum system; {\cal X} -player determines the measurement "cost matrix" 0\preceq M(x)\preceq I indexed by x\in{\cal X} and {\cal H} -player inputs state \ket{\psi}\in{\cal H} into the measuring system (mixed state is also possible). After their action, the cost \bra{\psi}M(x)\ket{\psi} is incurred. Consider {\cal X} -player seeks to maximize the cost while {\cal H} -player seeks to minimize the cost. In each round 1\leq l\leq L , {\cal H} -player inputs a (mixed) state, i.e., a density matrix F(l) on \mathcal{S(H)} ; then {\cal X} -player responds cost matrix M(x_{l}) with pure strategy x_{l}\in{\cal X} . Our goal is to construct a sequence of mixed states F(1),F(2),\ldots,F(L) such that the total cost \sum_{l=1}^{L}\Big(\mathrm{Tr}\Big(F(l)M(x_{l})\Big)\Big) is not too much more than the cost of {\cal H} -player’s best pure state \ket{\psi}\in\mathcal{H} in hindsight, i.e., \min_{\ket{\psi}\in{\cal H}}\bra{\psi}\sum_{l=1}^{L}M(x_{l})\ket{\psi}. The MMWU algorithm is an iterative algorithm that approximately obtains each player’s best mixed strategies. The MMWU algorithm has a few variations, and we use so-called Hedge algorithm [ 5 ] . The MMWU algorithm reviewed in Algorithm 1 is presented in [ 21 ] , and its performance is evaluated in the following lemma. For readers’ convenience, we provide a proof of the lemma in Appendix -A ; see also [ 5 , Theorem 3.2] Algorithm 1 Matrix Multiplicative Weights Update algorithm Fix \varepsilon\in(0,\frac{1}{2}), and initialize the weight matrix G(1)=I . For each step l=1,2,...,L : 1. {\cal H} -player selects mixed state as follows: F(l)=\frac{G(l)}{\mathrm{Tr}(G(l))} 2. {\cal X} -player selects pure strategy x_{l}\in{\cal X} . 3. For the cost matrix M(x_{l}) , update the weight matrix: \displaystyle G(l+1)=\exp\bigg(-\varepsilon\sum_{l^{\prime}=1}^{l}M(x_{l^{\prime}})\bigg) Lemma 1 . (MMWU algorithm performance) Fix an arbitrary \varepsilon\in(0,\frac{1}{2}) . The mixed states F(1),F(2),\ldots,F(L) which {\cal H} -player obtains by Algorithm 1 satisfies that for every state \ket{\psi}\in\mathcal{H} , \displaystyle(1-\varepsilon)\sum_{l=1}^{L}\bigg(\mathrm{Tr}\Big(F(l)M(x_{l})\Big)\bigg) \displaystyle\quad\leq\sum_{l=1}^{L}\bra{\psi}M(x_{l})\ket{\psi}+\frac{\ln{\dim(\mathcal{H})}}{\varepsilon}. IV Quantum hypergraph soft covering In this section, as a tool to analyze C-Q channel resolvability, we consider the quantum hypergraph soft covering [ 3 ] . A quantum hypergraph soft covering (\mathcal{V,E}) consists of a

Read the complete text