Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:0909.5347 · IEEE Transactions on Information Theory

A Quantum Version of Wielandt's Inequality

Mikel Sanz, David Pérez-García, Michael M. Wolf, J. I. Cirac

Published Aug 19, 2010• 116 citations
arXivHTMLPDF

Abstract

In this paper, Wielandt's inequality for classical channels is extended to quantum channels. That is, an upper bound to the number of times a channel must be applied, so that it maps any density operator to one with full rank, is found. Using this bound, dichotomy theorems for the zero-error capacity of quantum channels and for the Matrix Product State (MPS) dimension of ground states of frustration-free Hamiltonians are derived. The obtained inequalities also imply new bounds on the required interaction-range of Hamiltonians with unique MPS ground state.

DOI
10.1109/tit.2010.2054552

Related papers

A generic quantum Wielandt's inequality

Yifan Jia, Ángela Capel

Quantum Wielandt's inequality gives an optimal upper bound on the minimal length k such that length- k products of elements in a generating system span Mn(C) . It is conjectured that k should be of order O(n2) in general. In this paper, we give an overview of how the question has been studied in the literature so far and its relation to a classical question in linear algebra, namely the length of the algebra Mn(C) . We provide a generic version of quantum Wielandt's inequality, which gives the optimal length with probability one. More specifically, we prove based on [KS16] that k generically is of order Θ(log⁡n) , as opposed to the general case, in which the best bound to date is O(n2log⁡n) . Our result implies a new bound on the primitivity index of a random quantum channel. Furthermore, we shed new light on a long-standing open problem for Projected Entangled Pair State, by concluding that almost any translation-invariant PEPS (in particular, Matrix Product State) with periodic boundary conditions on a grid with side length of order Ω(log⁡n) is the unique ground state of a local Hamiltonian. We observe similar characteristics for matrix Lie algebras and provide numerical results for random Lie-generating systems.

arXiv:2301.08241•Quantum•May 2, 2024•6 citations

A New Bound on Quantum Wielandt Inequality

Mizanur Rahaman

A new bound on quantum version of Wielandt inequality for positive (not necessarily completely positive) maps has been established. Also bounds for entanglement breaking and PPT channels are put forward which are better bound than the previous bounds known. We prove that a primitive positive map E acting on Mdthat satisfies the Schwarz inequality becomes strictly positive after at most 2(d-1)2iterations. This is to say that after 2(d-1)2iterations, such a map sends every positive semidefinite matrix to a positive definite one. This finding does not depend on the number of Kraus operators as the map may not admit any Kraus decomposition. The motivation of this work is to provide an answer to a question raised by Sanz-García-Wolf and Cirac in their work on quantum Wielandt bound.

arXiv:1807.06872•IEEE Transactions on Information Theory•Oct 7, 2019•21 citations

Complexity and Capacity Bounds for Quantum Channels

Rupert H. Levene, Vern I. Paulsen, Ivan G. Todorov

We generalize some well-known graph parameters to operator systems by considering their underlying quantum channels. In particular, we introduce the quantum complexity as the dimension of the smallest co-domain Hilbert space a quantum channel requires to realize a given operator system as its non-commutative confusability graph. We describe quantum complexity as a generalized minimum semidefinite rank and, in the case of a graph operator system, as a quantum intersection number. The quantum complexity and a closely related quantum version of orthogonal rank turn out to be upper bounds for the Shannon zero-error capacity of a quantum channel, and we construct examples for which these bounds beat the best previously known general upper bound for the capacity of quantum channels, given by the quantum Lovász theta number.

arXiv:1710.06456•IEEE Transactions on Information Theory•May 7, 2018•14 citations

Fully Quantum Arbitrarily Varying Channels: Random Coding Capacity and Capacity Dichotomy

Holger Boche, Christian Deppe, Janis Nötzel +1 more

We consider a model of communication via a fully quantum jammer channel with quantum jammer, quantum sender and quantum receiver, which we dub quantum arbitrarily varying channel (QAVC). Restricting to finite dimensional user and jammer systems, we show, using permutation symmetry and a de Finetti reduction, how the random coding capacity (classical and quantum) of the QAVC is reduced to the capacity of a naturally associated compound channel, which is obtained by restricting the jammer to i.i.d. input states. Furthermore, we demonstrate that the shared randomness required is at most logarithmic in the block length, via a quantum version of the “elimination of of correlation” using a random matrix tail bound. This implies a dichotomy theorem: either the classical capacity of the QAVC is zero, and then also the quantum capacity is zero, or each capacity equals its random coding variant.

arXiv:1801.04572•IEEE International Symposium on Information Theory (ISIT)•Jun 1, 2018•21 citations

A Simple and Tighter Derivation of Achievability for Classical-Quantum Channel Coding

Hao–Chung Cheng

In this paper, we propose an elegant and simple one-shot achievability proof for classical-quantum channel coding. The established one-shot bound admits a closed-form expression as in the celebrated Holevo–Helstrom Theorem. Namely, the average error probability of sending M messages through a classical-quantum channel is upper bounded by the minimum error of distinguishing the joint state between channel input and output against (M−1)-many products of its marginals. Our result provides the tightest achievable one-shot capacity for classical-quantum channel coding, and it improves the third-order coding rate in the asymptotic scenario. Moreover, the derived bound directly leads to asymptotic achievability results in the large deviation, small deviation, and moderate deviation regimes in a unified manner.The full version of the manuscript can be found at [arXiv:2208.02132] [1].

IEEE International Symposium on Information Theory (ISIT)•Jun 25, 2023•1 citation

Quantum states characterization for the zero-error capacity

Rex A. C. Medeiros, Romain Alléaume, Gérard Cohen +1 more

The zero-error capacity of quantum channels was defined as the least upper bound of rates at which classical information can be transmitted through a quantum channel with probability of error equal to zero. This paper investigates some properties of input states and measurements used to attain the quantum zero-error capacity. We start by reformulating the problem of finding the zero-error capacity in the language of graph theory. This alternative definition is used to prove that the zero-error capacity of any quantum channel can be reached by using tensor products of pure states as channel inputs, and projective measurements in the channel output. We conclude by presenting an example that illustrates our results.

arXiv:quant-ph/0611042•Nov 3, 2006•21 citations
In this paper, Wielandt's inequality for classical channels is extended to quantum channels. That is, an upper bound to the number of times a channel must be applied, so that it maps any density operator to one with full rank, is found. Using this bound, dichotomy theorems for the zero-error capacity of quantum channels and for the Matrix Product State (MPS) dimension of ground states of frustration-free Hamiltonians are derived. The obtained inequalities also imply new bounds on the required interaction-range of Hamiltonians with unique MPS ground state.
Quantum Wielandt's inequality gives an optimal upper bound on the minimal length k such that length- k products of elements in a generating system span Mn(C) . It is conjectured that k should be of order O(n2) in general. In this paper, we give an overview of how the question has been studied in the literature so far and its relation to a classical question in linear algebra, namely the length of the algebra Mn(C) . We provide a generic version of quantum Wielandt's inequality, which gives the optimal length with probability one. More specifically, we prove based on [KS16] that k generically is of order Θ(log⁡n) , as opposed to the general case, in which the best bound to date is O(n2log⁡n) . Our result implies a new bound on the primitivity index of a random quantum channel. Furthermore, we shed new light on a long-standing open problem for Projected Entangled Pair State, by concluding that almost any translation-invariant PEPS (in particular, Matrix Product State) with periodic boundary conditions on a grid with side length of order Ω(log⁡n) is the unique ground state of a local Hamiltonian. We observe similar characteristics for matrix Lie algebras and provide numerical results for random Lie-generating systems.
A new bound on quantum version of Wielandt inequality for positive (not necessarily completely positive) maps has been established. Also bounds for entanglement breaking and PPT channels are put forward which are better bound than the previous bounds known. We prove that a primitive positive map E acting on Mdthat satisfies the Schwarz inequality becomes strictly positive after at most 2(d-1)2iterations. This is to say that after 2(d-1)2iterations, such a map sends every positive semidefinite matrix to a positive definite one. This finding does not depend on the number of Kraus operators as the map may not admit any Kraus decomposition. The motivation of this work is to provide an answer to a question raised by Sanz-García-Wolf and Cirac in their work on quantum Wielandt bound.
We generalize some well-known graph parameters to operator systems by considering their underlying quantum channels. In particular, we introduce the quantum complexity as the dimension of the smallest co-domain Hilbert space a quantum channel requires to realize a given operator system as its non-commutative confusability graph. We describe quantum complexity as a generalized minimum semidefinite rank and, in the case of a graph operator system, as a quantum intersection number. The quantum complexity and a closely related quantum version of orthogonal rank turn out to be upper bounds for the Shannon zero-error capacity of a quantum channel, and we construct examples for which these bounds beat the best previously known general upper bound for the capacity of quantum channels, given by the quantum Lovász theta number.
We consider a model of communication via a fully quantum jammer channel with quantum jammer, quantum sender and quantum receiver, which we dub quantum arbitrarily varying channel (QAVC). Restricting to finite dimensional user and jammer systems, we show, using permutation symmetry and a de Finetti reduction, how the random coding capacity (classical and quantum) of the QAVC is reduced to the capacity of a naturally associated compound channel, which is obtained by restricting the jammer to i.i.d. input states. Furthermore, we demonstrate that the shared randomness required is at most logarithmic in the block length, via a quantum version of the “elimination of of correlation” using a random matrix tail bound. This implies a dichotomy theorem: either the classical capacity of the QAVC is zero, and then also the quantum capacity is zero, or each capacity equals its random coding variant.
In this paper, we propose an elegant and simple one-shot achievability proof for classical-quantum channel coding. The established one-shot bound admits a closed-form expression as in the celebrated Holevo–Helstrom Theorem. Namely, the average error probability of sending M messages through a classical-quantum channel is upper bounded by the minimum error of distinguishing the joint state between channel input and output against (M−1)-many products of its marginals. Our result provides the tightest achievable one-shot capacity for classical-quantum channel coding, and it improves the third-order coding rate in the asymptotic scenario. Moreover, the derived bound directly leads to asymptotic achievability results in the large deviation, small deviation, and moderate deviation regimes in a unified manner.The full version of the manuscript can be found at [arXiv:2208.02132] [1].
The zero-error capacity of quantum channels was defined as the least upper bound of rates at which classical information can be transmitted through a quantum channel with probability of error equal to zero. This paper investigates some properties of input states and measurements used to attain the quantum zero-error capacity. We start by reformulating the problem of finding the zero-error capacity in the language of graph theory. This alternative definition is used to prove that the zero-error capacity of any quantum channel can be reached by using tensor products of pure states as channel inputs, and projective measurements in the channel output. We conclude by presenting an example that illustrates our results.