arXiv:2208.11286

Resolving Matrix Spencer Conjecture Up to Poly-logarithmic Rank

Nikhil Bansal, Haotian Jiang, Raghu Meka

Published Aug 24, 2022• 0 citations

Abstract

We give a simple proof of the matrix Spencer conjecture up to poly-logarithmic rank: given symmetric $d \times d$ matrices $A_1,\ldots,A_n$ each with $\|A_i\|_{\mathsf{op}} \leq 1$ and rank at most $n/\log^3 n$, one can efficiently find $\pm 1$ signs $x_1,\ldots,x_n$ such that their signed sum has spectral norm $\|\sum_{i=1}^n x_i A_i\|_{\mathsf{op}} = O(\sqrt{n})$. This result also implies a $\log n - Ω( \log \log n)$ qubit lower bound for quantum random access codes encoding $n$ classical bits with advantage $\gg 1/\sqrt{n}$. Our proof uses the recent refinement of the non-commutative Khintchine inequality in [Bandeira, Boedihardjo, van Handel, 2022] for random matrices with correlated Gaussian entries.

DOI: 10.48550/arxiv.2208.11286

Related papers

Improved bounds on stabilizer extent and Clifford rank

Pulkit Sinha, Benjamin Lovitz

quant-pharXiv:2610.06819Oct 6, 20260 citations

Resolving Matrix Spencer Conjecture Up to Poly-logarithmic Rank

Nikhil Bansal, Haotian Jiang, Raghu Meka

We give a simple proof of the matrix Spencer conjecture up to poly-logarithmic rank: given symmetric d × d matrices A1,…,An each with ||Ai||op ≤ 1 and rank at most n/log3 n, one can efficiently find ± 1 signs x1,…,xn such that their signed sum has spectral norm ||∑i=1n xi Ai||op = O(√n). This result also implies a logn − Ω( loglogn) qubit lower bound for quantum random access codes encoding n classical bits with advantage ≫ 1/√n.

ACM Symposium on Theory of Computing (STOC)May 16, 20237 citations

Communication Complexity of Integer Matrix Singularity

Chengu Wang

cs.CCCross-listedarXiv:2610.33521Oct 27, 20260 citations

Quantum algorithms for spectral sums

Alessandro Luongo, Changpeng Shao

arXiv:2011.06475Nov 12, 20202 citations

Quantum Algorithms for Spectral Sums

Alessandro Luongo, Changpeng Shao

Proceedings of the AAAI Conference on Artificial IntelligenceMar 14, 20260 citations

Randomized simulation of quantum channels using small ancilla

Marcin Kotowski, Michał Kotowski

quant-pharXiv:2606.08784Jun 9, 20260 citations

arXiv:2208.11286

Resolving Matrix Spencer Conjecture Up to Poly-logarithmic Rank

Nikhil Bansal, Haotian Jiang, Raghu Meka

Published Aug 24, 2022• 0 citations

arXiv HTML PDF

Abstract

We give a simple proof of the matrix Spencer conjecture up to poly-logarithmic rank: given symmetric

d \times d

matrices

A_1,\ldots,A_n

each with

\|A_i\|_{\mathsf{op}} \leq 1

and rank at most

n/\log^3 n

, one can efficiently find

\pm 1

signs

x_1,\ldots,x_n

such that their signed sum has spectral norm

\|\sum_{i=1}^n x_i A_i\|_{\mathsf{op}} = O(\sqrt{n})

. This result also implies a

\log n - Ω( \log \log n)

qubit lower bound for quantum random access codes encoding

n

classical bits with advantage

\gg 1/\sqrt{n}

. Our proof uses the recent refinement of the non-commutative Khintchine inequality in [Bandeira, Boedihardjo, van Handel, 2022] for random matrices with correlated Gaussian entries.

DOI: 10.48550/arxiv.2208.11286

Related papers

Improved bounds on stabilizer extent and Clifford rank

Pulkit Sinha, Benjamin Lovitz

We prove that every pure state of stabilizer rank at most $k$ has stabilizer extent at most $2^{O(\sqrt{k\log(k+1)})}$ , and establish the analogous bound for the squared Clifford coefficient norm of Clifford-rank- $k$ operators. This implies stabilizer fidelity at least $2^{-O(\sqrt{k\log(k+1)})}$ , resolving the quantitative conjecture of (Mehraban-Tamasbi, STOC, 2025), and proves an $Ω(n^2/\log n)$ lower bound for the approximate stabilizer rank of tensor powers of any non-stabilizer qubit state. The latter result generalizes the best-known lower bound for tensor powers of $T$ -states (Mehraban-Tamasbi, STOC, 2024) to arbitrary non-stabilizer qubit states, including magic states. As a consequence of the Clifford rank--norm inequality, we obtain an $Ω(n^2/\log n)$ lower bound for exact representations of $n$ -bit AND function by quadratic phases, improving the previous best-known linear bound. Further consequences rule out pseudorandom state and unitary ensembles with approximate stabilizer and Clifford rank $O((\log n)^2/\log\log n)$ , respectively, a $\log n$ improvement over prior work (Kalra-Sinha, Quantum, 2026). We also obtain tomography algorithms for states of stabilizer rank at most $k$ , with $poly(n)2^{O(\sqrt{k\log(k+1)})}$ time and copy complexity, a nearly square-root improvement in the exponent over the best-known algorithm.We prove that every pure state of stabilizer rank at most $k$ has stabilizer extent at most $2^{O(\sqrt{k\log(k+1)})}$, and establish the analogous bound for the squared Clifford coefficient norm of Clifford-rank-$k$ operators. This implies stabilizer fidelity at least $2^{-O(\sqrt{k\log(k+1)})}$, resolving the quantitative conjecture of (Mehraban-Tamasbi, STOC, 2025), and proves an $Ω(n^2/\log n)$ lower bound for the approximate stabilizer rank of tensor powers of any non-stabilizer qubit state. The latter result generalizes the best-known lower bound for tensor powers of $T$-states (Mehraban-Tamasbi, STOC, 2024) to arbitrary non-stabilizer qubit states, including magic states. As a consequence of the Clifford rank--norm inequality, we obtain an $Ω(n^2/\log n)$ lower bound for exact representations of $n$-bit AND function by quadratic phases, improving the previous best-known linear bound. Further consequences rule out pseudorandom state and unitary ensembles with approximate stabilizer and Clifford rank $O((\log n)^2/\log\log n)$, respectively, a $\log n$ improvement over prior work (Kalra-Sinha, Quantum, 2026). We also obtain tomography algorithms for states of stabilizer rank at most $k$, with $poly(n)2^{O(\sqrt{k\log(k+1)})}$ time and copy complexity, a nearly square-root improvement in the exponent over the best-known algorithm.

quant-pharXiv:2610.06819Oct 6, 20260 citations

Resolving Matrix Spencer Conjecture Up to Poly-logarithmic Rank

Nikhil Bansal, Haotian Jiang, Raghu Meka

ACM Symposium on Theory of Computing (STOC)May 16, 20237 citations

Communication Complexity of Integer Matrix Singularity

Chengu Wang

Alice and Bob hold complementary halves of the columns of an $n\times n$ matrix of $k$ -bit integers and decide whether it is singular over $\mathbb Q$ . Up to constant-factor dimension growth, this partitioned problem is equivalent to additive singularity, where Alice and Bob hold $n\times n$ matrices $A,B$ of $k$ -bit integers and test the singularity of $A+B$ over $\mathbb Q$ . We prove a bounded-error quantum lower bound $Ω(\min\{n^{3/2}\sqrt{k\log n},n^2\log(nk)\})$ and a randomized upper bound $O(n^2\min\{k,\log(k+\log n)\})$ . The bounds match at $Θ(n^2\log(nk))$ for $k\ge n\log n$ . The lower bound holds even under the promise of rank $n-1$ versus $n$ . Its proof combines an integer witness with a local digit encoding, while the upper-bound protocol lifts modular kernel relations using short messages. Bitwise sharing changes how the communication complexity depends on the entry bit length $k$ . If Alice and Bob instead hold $n\times n$ matrices $A,B$ of $k$ -bit integers and test whether their entrywise bitwise XOR $A\oplus B$ is singular over $\mathbb Q$ , we prove a quantum lower bound $Ω(n^2k)$ , matching the trivial upper bound. This lower bound holds even under the promise of rank $n-1$ versus $n$ . Our proof uses a dense weighted equation and a signed Fourier witness whose exceptional dyadic frequencies can be removed at small variation cost.Alice and Bob hold complementary halves of the columns of an $n\times n$ matrix of $k$-bit integers and decide whether it is singular over $\mathbb Q$. Up to constant-factor dimension growth, this partitioned problem is equivalent to additive singularity, where Alice and Bob hold $n\times n$ matrices $A,B$ of $k$-bit integers and test the singularity of $A+B$ over $\mathbb Q$. We prove a bounded-error quantum lower bound $Ω(\min\{n^{3/2}\sqrt{k\log n},n^2\log(nk)\})$ and a randomized upper bound $O(n^2\min\{k,\log(k+\log n)\})$. The bounds match at $Θ(n^2\log(nk))$ for $k\ge n\log n$. The lower bound holds even under the promise of rank $n-1$ versus $n$. Its proof combines an integer witness with a local digit encoding, while the upper-bound protocol lifts modular kernel relations using short messages. Bitwise sharing changes how the communication complexity depends on the entry bit length $k$. If Alice and Bob instead hold $n\times n$ matrices $A,B$ of $k$-bit integers and test whether their entrywise bitwise XOR $A\oplus B$ is singular over $\mathbb Q$, we prove a quantum lower bound $Ω(n^2k)$, matching the trivial upper bound. This lower bound holds even under the promise of rank $n-1$ versus $n$. Our proof uses a dense weighted equation and a signed Fourier witness whose exceptional dyadic frequencies can be removed at small variation cost.

cs.CCCross-listedarXiv:2610.33521Oct 27, 20260 citations

Quantum algorithms for spectral sums

Alessandro Luongo, Changpeng Shao

We propose new quantum algorithms for estimating spectral sums of positive semi-definite (PSD) matrices. The spectral sum of an PSD matrix $A$ , for a function $f$ , is defined as $ \text{Tr}[f(A)] = \sum_j f(λ_j)$, where $λ_j$ are the eigenvalues of $A$ . Typical examples of spectral sums are the von Neumann entropy, the trace of $A^{-1}$ , the log-determinant, and the Schatten $p$ -norm, where the latter does not require the matrix to be PSD. The current best classical randomized algorithms estimating these quantities have a runtime that is at least linearly in the number of nonzero entries of the matrix and quadratic in the estimation error. Assuming access to a block-encoding of a matrix, our algorithms are sub-linear in the matrix size, and depend at most quadratically on other parameters, like the condition number and the approximation error, and thus can compete with most of the randomized and distributed classical algorithms proposed in the literature, and polynomially improve the runtime of other quantum algorithms proposed for the same problems. We show how the algorithms and techniques used in this work can be applied to three problems in spectral graph theory: approximating the number of triangles, the effective resistance, and the number of spanning trees within a graph.We propose new quantum algorithms for estimating spectral sums of positive semi-definite (PSD) matrices. The spectral sum of an PSD matrix $A$, for a function $f$, is defined as $ \text{Tr}[f(A)] = \sum_j f(λ_j)$, where $λ_j$ are the eigenvalues of $A$. Typical examples of spectral sums are the von Neumann entropy, the trace of $A^{-1}$, the log-determinant, and the Schatten $p$-norm, where the latter does not require the matrix to be PSD. The current best classical randomized algorithms estimating these quantities have a runtime that is at least linearly in the number of nonzero entries of the matrix and quadratic in the estimation error. Assuming access to a block-encoding of a matrix, our algorithms are sub-linear in the matrix size, and depend at most quadratically on other parameters, like the condition number and the approximation error, and thus can compete with most of the randomized and distributed classical algorithms proposed in the literature, and polynomially improve the runtime of other quantum algorithms proposed for the same problems. We show how the algorithms and techniques used in this work can be applied to three problems in spectral graph theory: approximating the number of triangles, the effective resistance, and the number of spanning trees within a graph.

arXiv:2011.06475Nov 12, 20202 citations

Quantum Algorithms for Spectral Sums

Alessandro Luongo, Changpeng Shao

We propose new quantum algorithms for estimating spectral sums of positive semi-definite (PSD) matrices. For a matrix A and a function f, the spectral sum is the trace of f(A), equivalently the sum over eigenvalues of A of f applied to each eigenvalue. Typical examples of spectral sums are the von Neumann entropy, the trace of the inverse of A, the log-determinant, and the Schatten p-norm, where the latter does not require the matrix to be PSD. The current best classical randomized algorithms estimating these quantities have a runtime that is at least linearly in the number of nonzero entries of the matrix and quadratic in the estimation error. Assuming access to a block-encoding of a matrix, our algorithms are sub-linear in the matrix size, and depend at most quadratically on other parameters, like the condition number and the approximation error, and thus can compete with most of the randomized and distributed classical algorithms proposed in the literature, and polynomially improve the runtime of other quantum algorithms proposed for the same problems. We show how the algorithms and techniques used in this work can be applied to three problems in spectral graph theory: approximating the number of triangles, the effective resistance, and the number of spanning trees in a graph.We propose new quantum algorithms for estimating spectral sums of positive semi-definite (PSD) matrices. For a matrix A and a function f, the spectral sum is the trace of f(A), equivalently the sum over eigenvalues of A of f applied to each eigenvalue. Typical examples of spectral sums are the von Neumann entropy, the trace of the inverse of A, the log-determinant, and the Schatten p-norm, where the latter does not require the matrix to be PSD. The current best classical randomized algorithms estimating these quantities have a runtime that is at least linearly in the number of nonzero entries of the matrix and quadratic in the estimation error. Assuming access to a block-encoding of a matrix, our algorithms are sub-linear in the matrix size, and depend at most quadratically on other parameters, like the condition number and the approximation error, and thus can compete with most of the randomized and distributed classical algorithms proposed in the literature, and polynomially improve the runtime of other quantum algorithms proposed for the same problems. We show how the algorithms and techniques used in this work can be applied to three problems in spectral graph theory: approximating the number of triangles, the effective resistance, and the number of spanning trees in a graph.

Proceedings of the AAAI Conference on Artificial IntelligenceMar 14, 20260 citations

Randomized simulation of quantum channels using small ancilla

Marcin Kotowski, Michał Kotowski

We study the problem of implementing a quantum channel using a small ancilla with classical randomization and postselection on an output failure flag. The simulation is probabilistic, but exact conditioned on success. We prove that any unital channel on a $d$ -dimensional system can be simulated with ancilla dimension $k$ and success probability $Ω(\frac{k}{\log d})$ . Equivalently, every unital channel on $n$ qubits can be simulated with constant success probability using only $O(\log n)$ ancillary qubits. We show that this tradeoff is best possible by constructing a family of channels which cannot be simulated with success probability better than $O(\frac{k}{\log d})$ . We also show that the class of \textit{highly noncommutative} channels, which includes random channels, admits constant-success simulation with just a single ancillary qubit. We further show that this model of simulation necessarily fails for strongly non-unital channels and discuss possible extensions involving adaptivity. On the technical side we rely on a partition-based protocol and matrix concentration inequalities, including the recent refinement of noncommutative Khintchine inequalities due to Bandeira, Boedihardjo and van Handel.We study the problem of implementing a quantum channel using a small ancilla with classical randomization and postselection on an output failure flag. The simulation is probabilistic, but exact conditioned on success. We prove that any unital channel on a $d$-dimensional system can be simulated with ancilla dimension $k$ and success probability $Ω(\frac{k}{\log d})$. Equivalently, every unital channel on $n$ qubits can be simulated with constant success probability using only $O(\log n)$ ancillary qubits. We show that this tradeoff is best possible by constructing a family of channels which cannot be simulated with success probability better than $O(\frac{k}{\log d})$. We also show that the class of \textit{highly noncommutative} channels, which includes random channels, admits constant-success simulation with just a single ancillary qubit. We further show that this model of simulation necessarily fails for strongly non-unital channels and discuss possible extensions involving adaptivity. On the technical side we rely on a partition-based protocol and matrix concentration inequalities, including the recent refinement of noncommutative Khintchine inequalities due to Bandeira, Boedihardjo and van Handel.

quant-pharXiv:2606.08784Jun 9, 20260 citations

We give a simple proof of the matrix Spencer conjecture up to poly-logarithmic rank: given symmetric

d \times d

matrices

A_1,\ldots,A_n

each with

\|A_i\|_{\mathsf{op}} \leq 1

and rank at most

n/\log^3 n

, one can efficiently find

\pm 1

signs

x_1,\ldots,x_n

such that their signed sum has spectral norm

\|\sum_{i=1}^n x_i A_i\|_{\mathsf{op}} = O(\sqrt{n})

. This result also implies a

\log n - Ω( \log \log n)

qubit lower bound for quantum random access codes encoding

n

classical bits with advantage

\gg 1/\sqrt{n}

. Our proof uses the recent refinement of the non-commutative Khintchine inequality in [Bandeira, Boedihardjo, van Handel, 2022] for random matrices with correlated Gaussian entries.

We prove that every pure state of stabilizer rank at most

k

has stabilizer extent at most

2^{O(\sqrt{k\log(k+1)})}

, and establish the analogous bound for the squared Clifford coefficient norm of Clifford-rank-

k

operators. This implies stabilizer fidelity at least

2^{-O(\sqrt{k\log(k+1)})}

, resolving the quantitative conjecture of (Mehraban-Tamasbi, STOC, 2025), and proves an

Ω(n^2/\log n)

lower bound for the approximate stabilizer rank of tensor powers of any non-stabilizer qubit state. The latter result generalizes the best-known lower bound for tensor powers of

T

-states (Mehraban-Tamasbi, STOC, 2024) to arbitrary non-stabilizer qubit states, including magic states. As a consequence of the Clifford rank--norm inequality, we obtain an

Ω(n^2/\log n)

lower bound for exact representations of

n

-bit AND function by quadratic phases, improving the previous best-known linear bound. Further consequences rule out pseudorandom state and unitary ensembles with approximate stabilizer and Clifford rank

O((\log n)^2/\log\log n)

, respectively, a

\log n

improvement over prior work (Kalra-Sinha, Quantum, 2026). We also obtain tomography algorithms for states of stabilizer rank at most

k

, with

poly(n)2^{O(\sqrt{k\log(k+1)})}

time and copy complexity, a nearly square-root improvement in the exponent over the best-known algorithm.

Alice and Bob hold complementary halves of the columns of an

n\times n

matrix of

k

-bit integers and decide whether it is singular over

\mathbb Q

. Up to constant-factor dimension growth, this partitioned problem is equivalent to additive singularity, where Alice and Bob hold

n\times n

matrices

A,B

k

-bit integers and test the singularity of

A+B

over

\mathbb Q

. We prove a bounded-error quantum lower bound

Ω(\min\{n^{3/2}\sqrt{k\log n},n^2\log(nk)\})

and a randomized upper bound

O(n^2\min\{k,\log(k+\log n)\})

. The bounds match at

Θ(n^2\log(nk))

for

k\ge n\log n

. The lower bound holds even under the promise of rank

n-1

versus

n

. Its proof combines an integer witness with a local digit encoding, while the upper-bound protocol lifts modular kernel relations using short messages. Bitwise sharing changes how the communication complexity depends on the entry bit length

k

. If Alice and Bob instead hold

n\times n

matrices

A,B

k

-bit integers and test whether their entrywise bitwise XOR

A\oplus B

is singular over

\mathbb Q

, we prove a quantum lower bound

Ω(n^2k)

, matching the trivial upper bound. This lower bound holds even under the promise of rank

n-1

versus

n

. Our proof uses a dense weighted equation and a signed Fourier witness whose exceptional dyadic frequencies can be removed at small variation cost.

We propose new quantum algorithms for estimating spectral sums of positive semi-definite (PSD) matrices. The spectral sum of an PSD matrix

A

, for a function

f

, is defined as $ \text{Tr}[f(A)] = \sum_j f(λ_j)$, where

λ_j

are the eigenvalues of

A

. Typical examples of spectral sums are the von Neumann entropy, the trace of

A^{-1}

, the log-determinant, and the Schatten

p

-norm, where the latter does not require the matrix to be PSD. The current best classical randomized algorithms estimating these quantities have a runtime that is at least linearly in the number of nonzero entries of the matrix and quadratic in the estimation error. Assuming access to a block-encoding of a matrix, our algorithms are sub-linear in the matrix size, and depend at most quadratically on other parameters, like the condition number and the approximation error, and thus can compete with most of the randomized and distributed classical algorithms proposed in the literature, and polynomially improve the runtime of other quantum algorithms proposed for the same problems. We show how the algorithms and techniques used in this work can be applied to three problems in spectral graph theory: approximating the number of triangles, the effective resistance, and the number of spanning trees within a graph.

d

-dimensional system can be simulated with ancilla dimension

k

and success probability

Ω(\frac{k}{\log d})

. Equivalently, every unital channel on

n

qubits can be simulated with constant success probability using only

O(\log n)

ancillary qubits. We show that this tradeoff is best possible by constructing a family of channels which cannot be simulated with success probability better than

O(\frac{k}{\log d})

. We also show that the class of \textit{highly noncommutative} channels, which includes random channels, admits constant-success simulation with just a single ancillary qubit. We further show that this model of simulation necessarily fails for strongly non-unital channels and discuss possible extensions involving adaptivity. On the technical side we rely on a partition-based protocol and matrix concentration inequalities, including the recent refinement of noncommutative Khintchine inequalities due to Bandeira, Boedihardjo and van Handel.