The following question arises from the study of quantum error correction, and high-dimensional expanders:

Is there an algorithm that for given numbers $n>0,d≤n,r≤n$ samples uniformly a linear operator $:\partial: F_2^n \to F_2^n$ , such that $\partial^2 = 0$, and each row/column of ∂ has Hamming weight at most d, and rank(∂)=r?

Note, that for d = n, i.e. boundary operators that are not sparse, the question can be solved in a straightforward manner as outlined in a paper of Bravyi and Hastings [Homological Product Codes]: one considers some fixed matrix Q - such that dim(im(Q))=r, and im(Q)⊆ker(Q) - and then the distribution is the set of matrices $A Q A^{-1}$ where A is a random invertible matrix over $F_2^n$.

Hence, the question is, whether the extra sparsity condition makes the problem intractable or not.

The importance of the question relates to the quantum LDPC conjecture: ideally, we would want to find such a procedure for $d=O_n(1)$. A solution to this question would at least imply that there exists some candidate ensemble where we can find good quantum LDPC codes - specifically of a type called CSS codes.



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.