International Journal of Quantum Information

Equality condition for a matrix inequality with Kronecker product

Ziyue Tan

Published Jan 10, 2025• 1 citation

Abstract

Quantum information theory has been greatly developed in the past decades, and many theoretical problems are related to matrix theory. We study the equality condition for a matrix inequality, [Formula: see text] rank([Formula: see text] ⊗[Formula: see text]) [Formula: see text] rank([Formula: see text] ⊗[Formula: see text] where [Formula: see text]’s are linearly independent matrices of the same size, and [Formula: see text]’s are linearly independent matrices of the same size. The inequality used to be a conjecture since 2013 and has recently been proven in the paper [Z. Song, L. Chen, Y. Sun and M. Hu, IEEE Trans. Inform. Theory 69 (2023) 2385]. We study several cases such as that [Formula: see text]’s are column vectors and [Formula: see text]’s are of various sizes. It turns out that some cases never satisfy the equality condition.

DOI: 10.1142/s0219749925500017

Related papers

Kronecker product and a related useful conjecture

Xiling Wang

Journal of Physics Conference SeriesFeb 1, 20250 citations

Linear inequalities related to quantum entanglement theory

Everett Patterson

In this thesis, we will consider various linear inequalities relating the entries and eigenvalues of certain types of matrices. Our approach will consist of constructing inequalities which set bounds on the eigenvalues of entanglement witnesses, a type of matrix of interest to quantum information theory. We will then consider what these can tell us about the relation between the off-diagonal entries and eigenvalues of positive semidefinite matrices.

Jan 1, 20200 citations

Quantum Time-Space Tradeoffs for Matrix Problems

Paul W. Beame, Niels Kornerup, Michael Whitmeyer

arXiv:2401.05321SIAM Journal on ComputingMay 20, 20261 citation

Proof of a Conjectured 0-Rényi Entropy Inequality With Applications to Multipartite Entanglement

Zhiwei Song, Lin Chen, Yize Sun +1 more

arXiv:2105.07679IEEE Transactions on Information TheoryDec 9, 20227 citations

Quantum Query Complexity with Matrix-Vector Products

Andrew M. Childs, Shih-Han Hung, Tongyang Li

arXiv:2102.11349Leibniz international proceedings in informaticsJan 1, 20212 citations

Understanding the Kronecker Matrix-Vector Complexity of Linear Algebra

Raphael A. Meyer, William Swartworth, David Paul Woodruff

arXiv:2502.08029Feb 12, 20250 citations

International Journal of Quantum Information

Equality condition for a matrix inequality with Kronecker product

Ziyue Tan

Published Jan 10, 2025• 1 citation

Publisher

Abstract

DOI: 10.1142/s0219749925500017

Related papers

Kronecker product and a related useful conjecture

Xiling Wang

Abstract This paper not only explores in detail the basic properties of the Kronecker product, such as the application of the union law, the distributive law, the transpose and the conjugate transpose, as well as the trace and the rank of the Kronecker product, but also rigorously proves these properties by means of mathematical induction or direct proofs. In addition, this paper extends these properties to Kronecker n-matrices and explores the applicability of inverse matrices and determinants to Kronecker products. More importantly, we introduce a conjecture related to the long-standing problem of distillability, which is partially solved when the number of nonzero elements is restricted. By showing the framework of the proof of the conjecture and a special case, we provide new perspectives for further research in this area.Abstract This paper not only explores in detail the basic properties of the Kronecker product, such as the application of the union law, the distributive law, the transpose and the conjugate transpose, as well as the trace and the rank of the Kronecker product, but also rigorously proves these properties by means of mathematical induction or direct proofs. In addition, this paper extends these properties to Kronecker n-matrices and explores the applicability of inverse matrices and determinants to Kronecker products. More importantly, we introduce a conjecture related to the long-standing problem of distillability, which is partially solved when the number of nonzero elements is restricted. By showing the framework of the proof of the conjecture and a special case, we provide new perspectives for further research in this area.

Journal of Physics Conference SeriesFeb 1, 20250 citations

Linear inequalities related to quantum entanglement theory

Everett Patterson

Jan 1, 20200 citations

Quantum Time-Space Tradeoffs for Matrix Problems

Paul W. Beame, Niels Kornerup, Michael Whitmeyer

Abstract. We consider the time and space required for quantum computers to solve a wide variety of problems involving matrices, many of which have only been analyzed classically in prior work. Our main results show that for a range of linear algebra problems—including matrix-vector product, matrix inversion, matrix multiplication and powering—existing classical time-space tradeoffs, several of which are tight for every space bound, also apply to quantum algorithms with at most a constant factor loss. For example, for almost all fixed matrices [Formula: see text], including the discrete Fourier transform matrix, we prove that quantum circuits with at most [Formula: see text] input queries and [Formula: see text] qubits of memory require [Formula: see text] to compute matrix-vector product [Formula: see text] for [Formula: see text]. We similarly prove that matrix multiplication for [Formula: see text] binary matrices requires [Formula: see text]. Because many of our lower bounds are matched by deterministic algorithms with the same time and space complexity, our results show that quantum computers cannot provide any asymptotic advantage for these problems with any space bound. We obtain matching lower bounds for the stronger notion of quantum cumulative memory complexity—the sum of the space per layer of a circuit. We also consider Boolean (i.e., AND-OR) matrix multiplication and matrix-vector products, improving the previous quantum time-space tradeoff lower bounds for [Formula: see text] Boolean matrix multiplication to [Formula: see text] from [Formula: see text]. Our improved lower bound for Boolean matrix multiplication is based on a new coloring argument that extracts more from the strong direct product theorem that was the basis for prior work. To obtain our tight lower bounds for linear algebra problems, we require much stronger bounds than strong direct product theorems. We obtain these bounds by adding a new bucketing method to the quantum recording-query technique of Zhandry that lets us apply classical arguments to upper bound the success probability of quantum circuits.Abstract. We consider the time and space required for quantum computers to solve a wide variety of problems involving matrices, many of which have only been analyzed classically in prior work. Our main results show that for a range of linear algebra problems—including matrix-vector product, matrix inversion, matrix multiplication and powering—existing classical time-space tradeoffs, several of which are tight for every space bound, also apply to quantum algorithms with at most a constant factor loss. For example, for almost all fixed matrices [Formula: see text], including the discrete Fourier transform matrix, we prove that quantum circuits with at most [Formula: see text] input queries and [Formula: see text] qubits of memory require [Formula: see text] to compute matrix-vector product [Formula: see text] for [Formula: see text]. We similarly prove that matrix multiplication for [Formula: see text] binary matrices requires [Formula: see text]. Because many of our lower bounds are matched by deterministic algorithms with the same time and space complexity, our results show that quantum computers cannot provide any asymptotic advantage for these problems with any space bound. We obtain matching lower bounds for the stronger notion of quantum cumulative memory complexity—the sum of the space per layer of a circuit. We also consider Boolean (i.e., AND-OR) matrix multiplication and matrix-vector products, improving the previous quantum time-space tradeoff lower bounds for [Formula: see text] Boolean matrix multiplication to [Formula: see text] from [Formula: see text]. Our improved lower bound for Boolean matrix multiplication is based on a new coloring argument that extracts more from the strong direct product theorem that was the basis for prior work. To obtain our tight lower bounds for linear algebra problems, we require much stronger bounds than strong direct product theorems. We obtain these bounds by adding a new bucketing method to the quantum recording-query technique of Zhandry that lets us apply classical arguments to upper bound the success probability of quantum circuits.

arXiv:2401.05321SIAM Journal on ComputingMay 20, 20261 citation

Proof of a Conjectured 0-Rényi Entropy Inequality With Applications to Multipartite Entanglement

Zhiwei Song, Lin Chen, Yize Sun +1 more

Characterizing the relations among the three bipartite reduced density operators$ \rho _{AB} $,$ \rho _{AC} $and$ \rho _{BC} $of a tripartite mixed state$ \rho _{ABC} $has been an open problem in quantum information. One of such relations has been reduced by [Cadney et al, LAA. 452, 153, 2014] to a conjectured inequality in terms of matrix rank, namely$ r(\rho _{AB}) \cdot r( \rho _{AC})\ge r( \rho _{BC}) $for any$ \rho _{ABC}$. It is denoted as open problem 41 in the website “Open quantum problems-IQOQI Vienna”. We prove the inequality, and thus establish a complete picture of the four-party linear inequalities in terms of the 0-entropy. Our proof is based on the construction of a novel canonical form of bipartite matrices under local equivalence. We extend our result to inequalities in multipartite systems, as well as the condition when the inequality is saturated.Characterizing the relations among the three bipartite reduced density operators$ \rho _{AB}$,$ \rho _{AC}$and$ \rho _{BC}$of a tripartite mixed state$ \rho _{ABC}$has been an open problem in quantum information. One of such relations has been reduced by [Cadney et al, LAA. 452, 153, 2014] to a conjectured inequality in terms of matrix rank, namely$r(\rho _{AB}) \cdot r( \rho _{AC})\ge r( \rho _{BC})$for any$ \rho _{ABC}$. It is denoted as open problem 41 in the website “Open quantum problems-IQOQI Vienna”. We prove the inequality, and thus establish a complete picture of the four-party linear inequalities in terms of the 0-entropy. Our proof is based on the construction of a novel canonical form of bipartite matrices under local equivalence. We extend our result to inequalities in multipartite systems, as well as the condition when the inequality is saturated.

arXiv:2105.07679IEEE Transactions on Information TheoryDec 9, 20227 citations

Quantum Query Complexity with Matrix-Vector Products

Andrew M. Childs, Shih-Han Hung, Tongyang Li

We study quantum algorithms that learn properties of a matrix using queries that return its action on an input vector. We show that for various problems, including computing the trace, determinant, or rank of a matrix or solving a linear system that it specifies, quantum computers do not provide an asymptotic speedup over classical computation. On the other hand, we show that for some problems, such as computing the parities of rows or columns or deciding if there are two identical rows or columns, quantum computers provide exponential speedup. We demonstrate this by showing equivalence between models that provide matrix-vector products, vector-matrix products, and vector-matrix-vector products, whereas the power of these models can vary significantly for classical computation.We study quantum algorithms that learn properties of a matrix using queries that return its action on an input vector. We show that for various problems, including computing the trace, determinant, or rank of a matrix or solving a linear system that it specifies, quantum computers do not provide an asymptotic speedup over classical computation. On the other hand, we show that for some problems, such as computing the parities of rows or columns or deciding if there are two identical rows or columns, quantum computers provide exponential speedup. We demonstrate this by showing equivalence between models that provide matrix-vector products, vector-matrix products, and vector-matrix-vector products, whereas the power of these models can vary significantly for classical computation.

arXiv:2102.11349Leibniz international proceedings in informaticsJan 1, 20212 citations

Understanding the Kronecker Matrix-Vector Complexity of Linear Algebra

Raphael A. Meyer, William Swartworth, David Paul Woodruff

We study the computational model where we can access a matrix $\mathbf{A}$ only by computing matrix-vector products $\mathbf{A}\mathrm{x}$ for vectors of the form $\mathrm{x} = \mathrm{x}_1 \otimes \cdots \otimes \mathrm{x}_q$ . We prove exponential lower bounds on the number of queries needed to estimate various properties, including the trace and the top eigenvalue of $\mathbf{A}$ . Our proofs hold for all adaptive algorithms, modulo a mild conditioning assumption on the algorithm's queries. We further prove that algorithms whose queries come from a small alphabet (e.g., $\mathrm{x}_i \in \{\pm1\}^n$ ) cannot test if $\mathbf{A}$ is identically zero with polynomial complexity, despite the fact that a single query using Gaussian vectors solves the problem with probability 1. In steep contrast to the non-Kronecker case, this shows that sketching $\mathbf{A}$ with different distributions of the same subguassian norm can yield exponentially different query complexities. Our proofs follow from the observation that random vectors with Kronecker structure have exponentially smaller inner products than their non-Kronecker counterparts.We study the computational model where we can access a matrix $\mathbf{A}$ only by computing matrix-vector products $\mathbf{A}\mathrm{x}$ for vectors of the form $\mathrm{x} = \mathrm{x}_1 \otimes \cdots \otimes \mathrm{x}_q$. We prove exponential lower bounds on the number of queries needed to estimate various properties, including the trace and the top eigenvalue of $\mathbf{A}$. Our proofs hold for all adaptive algorithms, modulo a mild conditioning assumption on the algorithm's queries. We further prove that algorithms whose queries come from a small alphabet (e.g., $\mathrm{x}_i \in \{\pm1\}^n$) cannot test if $\mathbf{A}$ is identically zero with polynomial complexity, despite the fact that a single query using Gaussian vectors solves the problem with probability 1. In steep contrast to the non-Kronecker case, this shows that sketching $\mathbf{A}$ with different distributions of the same subguassian norm can yield exponentially different query complexities. Our proofs follow from the observation that random vectors with Kronecker structure have exponentially smaller inner products than their non-Kronecker counterparts.

arXiv:2502.08029Feb 12, 20250 citations

Characterizing the relations among the three bipartite reduced density operators$ \rho _{AB}

,

\rho _{AC}

and

\rho _{BC}

of a tripartite mixed state

\rho _{ABC}

has been an open problem in quantum information. One of such relations has been reduced by [Cadney et al, LAA. 452, 153, 2014] to a conjectured inequality in terms of matrix rank, namely

r(\rho _{AB}) \cdot r( \rho _{AC})\ge r( \rho _{BC})

for any

\rho _{ABC}$. It is denoted as open problem 41 in the website “Open quantum problems-IQOQI Vienna”. We prove the inequality, and thus establish a complete picture of the four-party linear inequalities in terms of the 0-entropy. Our proof is based on the construction of a novel canonical form of bipartite matrices under local equivalence. We extend our result to inequalities in multipartite systems, as well as the condition when the inequality is saturated.

We study the computational model where we can access a matrix

\mathbf{A}

only by computing matrix-vector products

\mathbf{A}\mathrm{x}

for vectors of the form

\mathrm{x} = \mathrm{x}_1 \otimes \cdots \otimes \mathrm{x}_q

. We prove exponential lower bounds on the number of queries needed to estimate various properties, including the trace and the top eigenvalue of

\mathbf{A}

. Our proofs hold for all adaptive algorithms, modulo a mild conditioning assumption on the algorithm's queries. We further prove that algorithms whose queries come from a small alphabet (e.g.,

\mathrm{x}_i \in \{\pm1\}^n

) cannot test if

\mathbf{A}

is identically zero with polynomial complexity, despite the fact that a single query using Gaussian vectors solves the problem with probability 1. In steep contrast to the non-Kronecker case, this shows that sketching

\mathbf{A}

with different distributions of the same subguassian norm can yield exponentially different query complexities. Our proofs follow from the observation that random vectors with Kronecker structure have exponentially smaller inner products than their non-Kronecker counterparts.