We prove that every traceless real or complex matrix $A$ can be written as $A=BC-CB$, with factors of the same size and over the same field satisfying $\|B\|\,\|C\|\le K\|A\|$, where $K$ is an absolute constant. The proof combines an approximate-rank dichotomy with stable commutator representations obtained from quantum expansion.
We prove that every traceless real or complex matrix A can be written as A=BC−CB, with factors of the same size and over the same field satisfying ∥B∥∥C∥≤K∥A∥, where K is an absolute constant. The proof combines an approximate-rank dichotomy with stable commutator representations obtained from quantum expansion.
We introduce a notion of matrix valued Gram decompositions for correlation matrices whose study is motivated by quantum information theory. We show that for extremal correlations, the matrices in such a factorization generate a Clifford algebra and thus, their size is exponential in terms of the rank of the correlation matrix. Using this we give a self-contained and succinct proof of the existence of completely positive semidefinite matrices with sub-exponential cpsd-rank, recently derived in the literature. This fact also underlies and generalizes Tsirelson's seminal lower bound on the local dimension of a quantum system necessary to generate an extreme quantum correlation.
We exhibit an operator norm bounded, infinite sequence {An} of 4n×4n complex matrices for which the commutator map X↦XAn−AnX is uniformly bounded below as an operator over the space of trace-zero self-adjoint matrices equipped with Hilbert--Schmidt norm. The construction is based on families of quantum expanders. We give several potential applications of these matrices to the study of quantum expanders. We formulate several natural conjectures and problems related to such matrices and provide numerical evidence.
The local Hamiltonian problem is famously complete for the class QMA, the quantum analogue of NP. The complexity of its semi-classical version, in which the terms of the Hamiltonian are required to commute (the CLH problem), has attracted considerable attention recently due to its intriguing nature, as well as in relation to growing interest in the qPCP conjecture. We show here that if the underlying bipartite interaction graph of the CLH instance is a good locally-expanding graph, namely, the expansion of any constant-size set is e-close to optimal, then approximating its ground energy to within additive factor O(e) lies in NP. The proof holds for k- local Hamiltonians for any constant k and any constant dimensionality of particles d. We also show that the approximation problem of CLH on such good local expanders is NP-hard. This implies that too good local expansion of the interaction graph constitutes an obstacle against quantum hardness of the approximation problem, though it retains its classical hardness. The result highlights new difficulties in trying to mimic classical proofs (in particular Dinur's PCP proof) in an attempt to prove the quantum PCP conjecture. A related result was discovered recently independently by Brandao and Harrow, for 2-local general Hamiltonians, bounding the quantum hardness of the approximation problem on good expanders, though no NP-hardness is known in that case.
Alice and Bob hold complementary halves of the columns of an n×n matrix of k-bit integers and decide whether it is singular over Q. Up to constant-factor dimension growth, this partitioned problem is equivalent to additive singularity, where Alice and Bob hold n×n matrices A,B of k-bit integers and test the singularity of A+B over Q. We prove a bounded-error quantum lower bound Ω(min{n3/2klogn,n2log(nk)}) and a randomized upper bound O(n2min{k,log(k+logn)}). The bounds match at Θ(n2log(nk)) for k≥nlogn. 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×n matrices A,B of k-bit integers and test whether their entrywise bitwise XOR A⊕B is singular over Q, we prove a quantum lower bound Ω(n2k), 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 exhibit an operator norm bounded, infinite sequence {An} of 3n×3n complex matrices for which the commutator map X↦XAn−AnX is uniformly bounded below as an operator over the space of trace-zero self-adjoint matrices equipped with Hilbert--Schmidt norm. The construction is based on families of quantum expanders. We give several potential applications of these matrices to the study of quantum expanders. We formulate several natural conjectures and problems related to such matrices and provide numerical evidence.
We fully determine the communication complexity of approximating matrix rank, over any finite field F. We study the most general version of this problem, where0⩽r<R⩽nare given integers and Alice and Bob need to determine whether their respective matricesA,B∈Fn×nsatisfy rk(A+B)=rversus rk(A+B)=R. We show that this problem has commu-nication costΩ(r2log∣F∣), which is optimal. Our lower bound holds even for quantum protocols and even for error probability21(1−∣F∣−r/3), which too is optimal because this problem has a two-bit classical protocol with error21(1−∣F∣−Θ(r)). Prior to our work, lower bounds were known only for constant-error protocols and only for consecutive integersrandR, with no implication for the approximation of matrix rank. We also settle an analogous question for subspaces, where Alice has a subspaceS, Bob has a subspaceT) and they need to approximate the dimension of the subspaceS+Tgenerated bySandT(equivalently, approximate the dimension ofS∩T). As an application, we obtain anΩ(n2log∣F∣)/kmemory lower bound for any streaming algorithm withkpasses that approximates the rank of an input matrixM∈Fn×nwithin a factor of2−δ, for anyδ>0. Our result is an exponential improvement inkover previous work.