publication . Article . Preprint . 2017

Tensor rank is not multiplicative under the tensor product

Christandl, Matthias; Jensen, Asger Kjærulff; Zuiddam, Jeroen;
Open Access English
  • Published: 25 May 2017
  • Country: Netherlands
Abstract
Abstract The tensor rank of a tensor t is the smallest number r such that t can be decomposed as a sum of r simple tensors. Let s be a k -tensor and let t be an l -tensor. The tensor product of s and t is a ( k + l ) -tensor. Tensor rank is sub-multiplicative under the tensor product. We revisit the connection between restrictions and degenerations. A result of our study is that tensor rank is not in general multiplicative under the tensor product. This answers a question of Draisma and Saptharishi. Specifically, if a tensor t has border rank strictly smaller than its rank, then the tensor rank of t is not multiplicative under taking a sufficiently hight tensor ...
Subjects
free text keywords: Algebraic complexity theory, Border rank, Degeneration, Quantum information theory, Tensor rank, Young flattening, Mathematics - Commutative Algebra, Computer Science - Computational Complexity, Quantum Physics, 15A69, Geometry and Topology, Algebra and Number Theory, Numerical Analysis, Discrete Mathematics and Combinatorics
Related Organizations
Funded by
EC| QMULT
Project
QMULT
Multipartite Quantum Information Theory
  • Funder: European Commission (EC)
  • Project Code: 337603
  • Funding stream: FP7 | SP2 | ERC
,
NWO| Quantum Position-Based Cryptography
Project
  • Funder: Netherlands Organisation for Scientific Research (NWO) (NWO)
  • Project Code: 2300171798

Alexander Alder. Grenzrang und Grenzkomplexität aus algebraischer und topologischer Sicht. PhD thesis, Zürich University, 1984.

[Sch81] [Str69] [Str83] [Str87] [Str88] [Str91] [Win71] Ramprasad Saptharishi. A survey of lower bounds in arithmetic circuit complexity 3.0.2, 2016. Online survey, https://github.com/dasarpmar/lowerbounds-survey.

SIAM J. Comput., 10(3):434-455, 1981.

Math., 13(4):354-356, 1969.

Volker Strassen. Rank and optimal computation of generic tensors. Linear Algebra Appl., 52/53:645-685, 1983. [OpenAIRE]

Volker Strassen. Relative bilinear complexity and matrix multiplication. J. Reine Angew. Math., 375/376:406-443, 1987.

Volker Strassen. The asymptotic spectrum of tensors. J. Reine Angew. Math., 384:102-152, 1988.

Volker Strassen. Degeneration and complexity of bilinear maps: some asymptotic spectra. J. Reine Angew. Math., 413:127-180, 1991.

Shmuel Winograd. On multiplication of 2 2 matrices. Linear Algebra Appl., 4(4):381-388, 1971. [OpenAIRE]

[YCGD10] Nengkun Yu, Eric Chitambar, Cheng Guo, and Runyao Duan.

Tensor rank of the tripartite state W tensor n. Phys. Rev. A, 81(1):014301, 2010.

[Zui17] Jeroen Zuiddam. A note on the gap between rank and border rank. Linear Algebra Appl., 525:33-44, 2017. [OpenAIRE]

Abstract
Abstract The tensor rank of a tensor t is the smallest number r such that t can be decomposed as a sum of r simple tensors. Let s be a k -tensor and let t be an l -tensor. The tensor product of s and t is a ( k + l ) -tensor. Tensor rank is sub-multiplicative under the tensor product. We revisit the connection between restrictions and degenerations. A result of our study is that tensor rank is not in general multiplicative under the tensor product. This answers a question of Draisma and Saptharishi. Specifically, if a tensor t has border rank strictly smaller than its rank, then the tensor rank of t is not multiplicative under taking a sufficiently hight tensor ...
Subjects
free text keywords: Algebraic complexity theory, Border rank, Degeneration, Quantum information theory, Tensor rank, Young flattening, Mathematics - Commutative Algebra, Computer Science - Computational Complexity, Quantum Physics, 15A69, Geometry and Topology, Algebra and Number Theory, Numerical Analysis, Discrete Mathematics and Combinatorics
Related Organizations
Funded by
EC| QMULT
Project
QMULT
Multipartite Quantum Information Theory
  • Funder: European Commission (EC)
  • Project Code: 337603
  • Funding stream: FP7 | SP2 | ERC
,
NWO| Quantum Position-Based Cryptography
Project
  • Funder: Netherlands Organisation for Scientific Research (NWO) (NWO)
  • Project Code: 2300171798

Alexander Alder. Grenzrang und Grenzkomplexität aus algebraischer und topologischer Sicht. PhD thesis, Zürich University, 1984.

[Sch81] [Str69] [Str83] [Str87] [Str88] [Str91] [Win71] Ramprasad Saptharishi. A survey of lower bounds in arithmetic circuit complexity 3.0.2, 2016. Online survey, https://github.com/dasarpmar/lowerbounds-survey.

SIAM J. Comput., 10(3):434-455, 1981.

Math., 13(4):354-356, 1969.

Volker Strassen. Rank and optimal computation of generic tensors. Linear Algebra Appl., 52/53:645-685, 1983. [OpenAIRE]

Volker Strassen. Relative bilinear complexity and matrix multiplication. J. Reine Angew. Math., 375/376:406-443, 1987.

Volker Strassen. The asymptotic spectrum of tensors. J. Reine Angew. Math., 384:102-152, 1988.

Volker Strassen. Degeneration and complexity of bilinear maps: some asymptotic spectra. J. Reine Angew. Math., 413:127-180, 1991.

Shmuel Winograd. On multiplication of 2 2 matrices. Linear Algebra Appl., 4(4):381-388, 1971. [OpenAIRE]

[YCGD10] Nengkun Yu, Eric Chitambar, Cheng Guo, and Runyao Duan.

Tensor rank of the tripartite state W tensor n. Phys. Rev. A, 81(1):014301, 2010.

[Zui17] Jeroen Zuiddam. A note on the gap between rank and border rank. Linear Algebra Appl., 525:33-44, 2017. [OpenAIRE]

Powered by OpenAIRE Research Graph
Any information missing or wrong?Report an Issue