Top

Quantum Information Processing

Published in:

01-04-2018

Algorithmic complexity of quantum capacity

Authors: Samad Khabbazi Oskouei, Stefano Mancini

Published in: Quantum Information Processing | Issue 4/2018

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

We analyze the notion of quantum capacity from the perspective of algorithmic (descriptive) complexity. To this end, we resort to the concept of semi-computability in order to describe quantum states and quantum channel maps. We introduce algorithmic entropies (like algorithmic quantum coherent information) and derive relevant properties for them. Then we show that quantum capacity based on semi-computable concept equals the entropy rate of algorithmic coherent information, which in turn equals the standard quantum capacity. Thanks to this, we finally prove that the quantum capacity, for a given semi-computable channel, is limit computable.

previous article Improving quantum state transfer efficiency and entanglement distribution in binary tree spin network through incomplete collapsing measurements

next article Capacity of a quantum memory channel correlated by matrix product states

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Semi-density matrix is a broader notion with respect to the density matrix, in that it conceives positive matrices with trace not necessarily equal to 1, although finite.

Throughout, the paper the \(\log \) is intended on base 2.

Example: Let us consider the subset A of all limit computable numbers between 0 and 1 which are represented as binary numbers. We can enumerate them by a Turing machine as \(\psi _1, \psi _2, \ldots , \psi _k, \ldots \). We denote by \(\epsilon _k=0. \psi _k (1) \psi _k (2) \ldots \psi _k (n) \ldots \) the kth element of A being \(\psi _k(n)\) the nth digit of \(\epsilon _k\). Now, consider a number \(\lambda \in [0,1]\) whose nth digit is equal to \(\psi _n (n)+1\) modulo 2. It is obvious that \(\lambda \) is different of any \(\epsilon _k\), and so \(\lambda \) is non-limit computable. The set of such \(\lambda \)’s is clearly uncountable.

Following [4], the embedding is obtained by turning the last bit of each canonical basis element to 0.

Wilde, M.M.: Quantum Information Theory. Cambridge University Press, Cambridge (2013)CrossRefMATH

Zvonkin, A.K., Levin, L.A.: The complexity of finite objects and the development of the concepts of information and randomness by means of the theory of algorithms. Russ. Math. Surv. 25, 83 (1970)CrossRefMATH

Gacs, P.: Quantum algorithmic entropy. J. Phys. A: Math. Theor. 34, 6859 (2001)ADSMathSciNetCrossRefMATH

Benatti, F., Oskouei, S.K., Deh Abad, A.S.: Gacs quantum algorithmic entropy in infinite dimensional Hilbert spaces. J. Math. Phys. 55, 082205 (2014)ADSMathSciNetCrossRefMATH

Oskouei, S.K.: Gacs algorithmic complexity in infinite Hilbert spaces and its applications. Ph.D. dissertation, University of Tehran (2015)

Solomonoff, R.: A formal theory of inductive inference. Inf. Control 7, 224 (1964)MathSciNetCrossRefMATH

Kolmogorov, A.: Three approaches to the quantitative definition of information. Probl. Inf. Transm. 1, 1 (1965)MATH

Chaitin, J.G.: On the length of programs for computing finite binary sequences. J. ACM 13, 547 (1966)MathSciNetCrossRefMATH

Berthiaume, A., van Dam, W., Laplante, S.: Quantum Kolmogorov complexity. J. Comput. Syst. Sci. 63, 201 (2001)MathSciNetCrossRefMATH

10.

Vitanyi, P.: Quantum Kolmogorov complexity based on classical descriptions. IEEE Trans. Inf. Theory 47, 2464 (2001)MathSciNetCrossRefMATH

11.

Mora, C.E., Briegel, H.J.: Algorithmic complexity and entanglement of quantum states. Phys. Rev. Lett. 95, 200503 (2005)ADSMathSciNetCrossRef

12.

Wolf, M.M., Cubitt, T.S., Perez-Garcia, D.: Are problems in Quantum Information Theory (un)decidable? arxiv.org/abs/1111.5425 (2011)

13.

Cubitt, T., et al.: Unbounded number of channel uses may be required to detect quantum capacity. Nat. Commun. 6, 6739 (2015)CrossRef

14.

Stinespring, W.F.: Positive functions on \(C^*\)-algebras. Proc. Am. Math. Soc. 6, 211 (1955)MathSciNetMATH

15.

Devetak, I.: The private classical capacity and quantum capacity of a quantum channel. IEEE Trans. Inf. Theory 51, 44 (2005)MathSciNetCrossRefMATH

16.

Hayden, P., Horodecki, M., Winter, A., Yard, J.: A decoupling approach to the quantum capacity. Open Syst. Inf. Dyn. 15, 7 (2008)MathSciNetCrossRefMATH

17.

Lindblad, G.: Completely positive maps and entropy inequalities. Commun. Math. Phys. 40, 147 (1975)ADSMathSciNetCrossRefMATH

18.

Davis, M., Sigal, R., Weyuker, E.J.: Computability, Complexity, and Languages: Fundamentals of Theoretical Computer Science. Academic Press, San Diego (1994)

19.

Choi, M.D.: Completely positive linear maps on complex matrices. Linear Algebra Appl. 10, 285 (1975)MathSciNetCrossRefMATH

Title: Algorithmic complexity of quantum capacity
Authors: Samad Khabbazi Oskouei
Stefano Mancini
Publication date: 01-04-2018
Publisher: Springer US
Published in: Quantum Information Processing / Issue 4/2018
Print ISSN: 1570-0755
Electronic ISSN: 1573-1332
DOI: https://doi.org/10.1007/s11128-018-1859-0

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Other articles of this Issue 4/2018

Bipartite non-classical correlations for a lossy two connected qubit–cavity systems: trace distance discord and Bell’s non-locality

Concurrence of three Jaynes–Cummings systems

Simultaneous dense coding affected by fluctuating massless scalar field

Deterministic joint remote preparation of an equatorial hybrid state via high-dimensional Einstein–Podolsky–Rosen pairs: active versus passive receiver

State-independent uncertainty relations and entanglement detection

Entropic uncertainty relations in the Heisenberg XXZ model and its controlling via filtering operations