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

ACM Symposium on Theory of Computing (STOC)

Kronecker products, low-depth circuits, and matrix rigidity

Josh Alman

Published Jun 15, 2021• 11 citations
Publisher

Abstract

For a matrix M and a positive integer r, the rank r rigidity of M is the smallest number of entries of M which one must change to make its rank at most r. There are many known applications of rigidity lower bounds to a variety of areas in complexity theory, but fewer known applications of rigidity upper bounds. In this paper, we use rigidity upper bounds to prove new upper bounds in a few different models of computation. Our results include:

DOI
10.1145/3406325.3451008

Related papers

Lower Bounds on Matrix Rigidity via a Quantum Argument

Ronald de Wolf

The rigidity of a matrix measures how many of its entries need to be changed in order to reduce its rank to some value. Good lower bounds on the rigidity of an explicit matrix would imply good lower bounds for arithmetic circuits as well as for communication complexity. Here we reprove the best known bounds on the rigidity of Hadamard matrices, due to Kashin and Razborov, using tools from quantum computing. Our proofs are somewhat simpler than earlier ones (at least for those familiar with quantum) and give slightly better constants. More importantly, they give a new approach to attack this longstanding open problem.

arXiv:quant-ph/0505188•May 25, 2005•5 citations

Smaller Low-Depth Circuits for Kronecker Powers

Josh Alman, Yunfeng Guan, Ashwin Padaki

A linear circuit for computing an N × N matrix M is a circuit with N inputs corresponding to the entries of a vector x and N outputs corresponding to the entries of the transformed vector Mx, and where each gate computes a linear combination of its inputs. Each gate may have unbounded fan-in, and the size of the circuit is the number of wires. This model captures most known algorithms for computing linear transforms, and (in the constant-depth or 'synchronous' settings) is equivalent to factoring M as the product of sparse matrices. We give new, smaller constructions of constant-depth linear circuits for computing any matrix which is the Kronecker power of a fixed matrix. A standard argument (e.g., the mixed product property of Kronecker products, or a generalization of the Fast Walsh-Hadamard transform) shows that any such N × N matrix has a depth-2 circuit of size O(N1.5). We improve on this for all such matrices, and especially for some such matrices of particular interest: • For any integer q > 1 and any matrix which is the Kronecker power of a fixed q × q matrix, we construct a depth-2 circuit of size O(N1.5-aq), where aq > 0 is a positive constant depending only on q. No bound beating size O(N1.5) was previously known for any q > 2. • For the case q = 2, i.e., for any matrix which is the Kronecker power of a fixed 2 × 2 matrix, we construct a depth-2 circuit of size O(N1.446), improving the prior best size O(N1.493) [Alman, 2021]. • For the Walsh-Hadamard transform, we construct a depth-2 circuit of size O(N1.443), improving the prior best size O(N1.476) [Alman, 2021]. • For the disjointness matrix (the communication matrix of set disjointness, or equivalently, the matrix for the linear transform that evaluates a multilinear polynomial on all 0/1 inputs), we construct a depth-2 circuit of size O(N1.258), improving the prior best size O(N1.272) [Jukna and Sergeev, 2013]. Our constructions also generalize to improving the standard construction for any depth ≤ O (log N). Our main technical tool is an improved way to convert a nontrivial circuit for any matrix into a circuit for its Kronecker powers. Our new bounds provably could not be achieved using the approaches of prior work.

arXiv:2211.05217•Society for Industrial and Applied Mathematics eBooks•Jan 1, 2023•6 citations

Complexity Bounds for Quantum Computation

Steven Thomas Homer

This project focused on upper and lower bounds for quantum computability using constant depth quantum circuits, and on the complexity theory of such circuits. It established significant differences between resource bounded quantum and classical computation models, particularly emphasizing new examples of where quantum circuits are more powerful than their classical counterparts. A second focus and outgrowth of this work was the creation of efficient quantum algorithms for specific problems and central combinatorial functions. Recent finding include upper bounds for the computational power of constant depth circuits composed of single qubit and CNOT gates, and lower bounds for the computational power of constant depth circuits with single qubit, CNOT and fanout gates. These results represent the power and the limits of small, possibly realizable quantum circuits. Also examined were bounds on computations with additional storage qubits (ancillae), and natural simple functions (realized by small depth circuits) which require ancillae for their computation.

•Jun 22, 2007•0 citations

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.

Journal of Physics Conference Series•Feb 1, 2025•0 citations

New lower bounds for CDS and $f$-routing

Atsuya Hasegawa, Ranitha Mataraarachchi

Understanding the entanglement cost of non-local quantum computation (NLQC) is relevant to complexity theory, cryptography, quantum gravity, and other areas. A central special case is $f$-routing, motivated in part by quantum position verification. Proving lower bounds on its entanglement cost in the fully robust setting has been a major open problem in NLQC. Motivated by this problem, we establish two related lower bounds. First, we study the shared-randomness cost of robust conditional disclosure of secrets (CDS). The connection between CDS and $f$-routing established by Allerstorfer et al. (Quantum 2024) makes understanding the randomness complexity of robust CDS a natural step toward lower bounds for the fully robust routing problem. We show that the shared-randomness cost of robust CDS is lower bounded by the logarithm of deterministic SMP communication complexity, even when communication and private randomness are unrestricted. Our lower bound is tight for the equality function. Second, we consider one-sided-perfect $f$-routing, in which the protocol is exact on one input class and has constant error on the other. By exploiting the positivity of the low-rank matrix in the method of Asadi, Culf, and May (ITCS 2025), we derive a lower bound on the entanglement cost in terms of sign rank. In particular, this yields a linear lower bound on the entanglement cost of routing for the inner-product function in both one-sided-perfect settings, matching the known upper bound.

quant-pharXiv:2609.24291•Sep 22, 2026•0 citations

Approximation norms and duality for communication complexity lower bounds

Troy Lee, Adi Shraibman

Abstract: We will discuss a general norm based framework for showing lower bounds on communication complexity. An advantage of this approach is that one can use duality theory to obtain a lower bound quantity phrased as a maximization problem, which can be more convenient to work with in showing lower bounds. We discuss two applications of this approach. 1. The approximation rank of a matrix A is the minimum rank of a matrix close to A in ell_infty norm. The logarithm of approximation rank lower bounds quantum communication complexity and is one of the most powerful techniques available, albeit difficult to compute in practice. We show that an approximation norm known as gamma_2 is polynomially related to approximation rank. This results in a polynomial time algorithm to approximate approximation rank, and also shows that the logarithm of approximation rank lower bounds quantum communication complexity even with entanglement which was previously not known. 2. By means of an approximation norm which lower bounds multiparty number-on-the-forehead complexity, we show non-trivial lower bounds on the complexity of the disjointness function for up to c log log n players, c <1.

Dagstuhl Seminar Proceedings•Jan 1, 2008•0 citations
For a matrix M and a positive integer r, the rank r rigidity of M is the smallest number of entries of M which one must change to make its rank at most r. There are many known applications of rigidity lower bounds to a variety of areas in complexity theory, but fewer known applications of rigidity upper bounds. In this paper, we use rigidity upper bounds to prove new upper bounds in a few different models of computation. Our results include:
The rigidity of a matrix measures how many of its entries need to be changed in order to reduce its rank to some value. Good lower bounds on the rigidity of an explicit matrix would imply good lower bounds for arithmetic circuits as well as for communication complexity. Here we reprove the best known bounds on the rigidity of Hadamard matrices, due to Kashin and Razborov, using tools from quantum computing. Our proofs are somewhat simpler than earlier ones (at least for those familiar with quantum) and give slightly better constants. More importantly, they give a new approach to attack this longstanding open problem.
A linear circuit for computing an N × N matrix M is a circuit with N inputs corresponding to the entries of a vector x and N outputs corresponding to the entries of the transformed vector Mx, and where each gate computes a linear combination of its inputs. Each gate may have unbounded fan-in, and the size of the circuit is the number of wires. This model captures most known algorithms for computing linear transforms, and (in the constant-depth or 'synchronous' settings) is equivalent to factoring M as the product of sparse matrices. We give new, smaller constructions of constant-depth linear circuits for computing any matrix which is the Kronecker power of a fixed matrix. A standard argument (e.g., the mixed product property of Kronecker products, or a generalization of the Fast Walsh-Hadamard transform) shows that any such N × N matrix has a depth-2 circuit of size O(N1.5). We improve on this for all such matrices, and especially for some such matrices of particular interest: • For any integer q > 1 and any matrix which is the Kronecker power of a fixed q × q matrix, we construct a depth-2 circuit of size O(N1.5-aq), where aq > 0 is a positive constant depending only on q. No bound beating size O(N1.5) was previously known for any q > 2. • For the case q = 2, i.e., for any matrix which is the Kronecker power of a fixed 2 × 2 matrix, we construct a depth-2 circuit of size O(N1.446), improving the prior best size O(N1.493) [Alman, 2021]. • For the Walsh-Hadamard transform, we construct a depth-2 circuit of size O(N1.443), improving the prior best size O(N1.476) [Alman, 2021]. • For the disjointness matrix (the communication matrix of set disjointness, or equivalently, the matrix for the linear transform that evaluates a multilinear polynomial on all 0/1 inputs), we construct a depth-2 circuit of size O(N1.258), improving the prior best size O(N1.272) [Jukna and Sergeev, 2013]. Our constructions also generalize to improving the standard construction for any depth ≤ O (log N). Our main technical tool is an improved way to convert a nontrivial circuit for any matrix into a circuit for its Kronecker powers. Our new bounds provably could not be achieved using the approaches of prior work.
This project focused on upper and lower bounds for quantum computability using constant depth quantum circuits, and on the complexity theory of such circuits. It established significant differences between resource bounded quantum and classical computation models, particularly emphasizing new examples of where quantum circuits are more powerful than their classical counterparts. A second focus and outgrowth of this work was the creation of efficient quantum algorithms for specific problems and central combinatorial functions. Recent finding include upper bounds for the computational power of constant depth circuits composed of single qubit and CNOT gates, and lower bounds for the computational power of constant depth circuits with single qubit, CNOT and fanout gates. These results represent the power and the limits of small, possibly realizable quantum circuits. Also examined were bounds on computations with additional storage qubits (ancillae), and natural simple functions (realized by small depth circuits) which require ancillae for their computation.
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.
New lower bounds for CDS and fff-routing
Understanding the entanglement cost of non-local quantum computation (NLQC) is relevant to complexity theory, cryptography, quantum gravity, and other areas. A central special case is fff-routing, motivated in part by quantum position verification. Proving lower bounds on its entanglement cost in the fully robust setting has been a major open problem in NLQC. Motivated by this problem, we establish two related lower bounds. First, we study the shared-randomness cost of robust conditional disclosure of secrets (CDS). The connection between CDS and fff-routing established by Allerstorfer et al. (Quantum 2024) makes understanding the randomness complexity of robust CDS a natural step toward lower bounds for the fully robust routing problem. We show that the shared-randomness cost of robust CDS is lower bounded by the logarithm of deterministic SMP communication complexity, even when communication and private randomness are unrestricted. Our lower bound is tight for the equality function. Second, we consider one-sided-perfect fff-routing, in which the protocol is exact on one input class and has constant error on the other. By exploiting the positivity of the low-rank matrix in the method of Asadi, Culf, and May (ITCS 2025), we derive a lower bound on the entanglement cost in terms of sign rank. In particular, this yields a linear lower bound on the entanglement cost of routing for the inner-product function in both one-sided-perfect settings, matching the known upper bound.
Abstract: We will discuss a general norm based framework for showing lower bounds on communication complexity. An advantage of this approach is that one can use duality theory to obtain a lower bound quantity phrased as a maximization problem, which can be more convenient to work with in showing lower bounds. We discuss two applications of this approach. 1. The approximation rank of a matrix A is the minimum rank of a matrix close to A in ell_infty norm. The logarithm of approximation rank lower bounds quantum communication complexity and is one of the most powerful techniques available, albeit difficult to compute in practice. We show that an approximation norm known as gamma_2 is polynomially related to approximation rank. This results in a polynomial time algorithm to approximate approximation rank, and also shows that the logarithm of approximation rank lower bounds quantum communication complexity even with entanglement which was previously not known. 2. By means of an approximation norm which lower bounds multiparty number-on-the-forehead complexity, we show non-trivial lower bounds on the complexity of the disjointness function for up to c log log n players, c <1.