I'm using the algorithm shown below to build specific matrices to apply code doping in a quantum error correction scenario. The matrices are binary and must abide by a specific set of construction laws:
There must be p rows with a single unit entry. The rest of the entries of that row will be null, as befits the binary nature of the matrices. Moreover, these unit entries must be placed in different columns for each row. In other words, the unit entries in these p rows can't be placed in the same column, they can't overlap.
The rest of the rows must contain a specific number of unit entries, sb_degree. As I will explain shortly, herein lies the issue.
For a matrix to be suitable for the required purposes (doping of a quantum LDPC code) every row and column must have at least one unit entry. Essentially, the matrix can't have an all zero row or column.
My code works reasonably well for specific combinations of the input algorithm parameters: p (number of rows with a single unit entry), m1 (number of rows of M), N (number of columns of M), and sb_degree (number of ones in the rows that have more than a single unit entry). For instance, it has no trouble finding matrices provided that the values of p and sb_degree aren't too large or small, respectively. However, due to the nature of the problem these matrices aim to solve, I require matrices with a large value of p (about 65% of the value of m1) and a small value of sb_degree. This becomes an issue for my algorithm, as small values of sb_degree make finding a matrix that satisfies the second and third construction requirements an ardous task.
Ideally, I'd like to be able to speed up this search so that I can get my hands on the type of matrices that I need to help in my quantum error correction research. I have included my Matlab code to provide context on how I am constructing the matrices. I'd be grateful if any of you can think of a way to make my code faster or come up with a different way to perform the construction of these matrices.
The algorithm is called as
M = Create_Doping_Matrix(m1,N,p,sb_degree) and is implemented as follows
M = zeros(m1,N);
p_indexes = randperm(m1,p);
all_indexes = 1:m1;
idx = ~ismember(all_indexes,p_indexes);
loc = find(idx~=0);
c_indexes = randperm(N,p);
% Create the rows with a single unit entry
for ii=1:p
M(p_indexes(ii),c_indexes(ii)) = 1;
end
M_orig = M;
% Create the rows with more than a single unit entry
for jj = 1:length(loc)
M(loc(jj), randperm(N,sb_degree))=1;
end
while nnz(sum(M,1)) ~= N % Check that there are no all-zero rows
M = M_orig;
for jj = 1:length(loc)
M(loc(jj), randperm(N,sb_degree))=1;
end
end
Rather than place values randomly until all columns have an entry, I would assign a row to all of the columns, and then fill in the m1-p rows until they each have sb_degree nonzero entries.
M = zeros(m1,N);
p_indexes = randperm(m1,p);
all_indexes = 1:m1;
idx = ~ismember(all_indexes,p_indexes);
loc = find(idx~=0);
c_indexes = randperm(N,p);
% Create the rows with a single unit entry
for ii=1:p
M(p_indexes(ii),c_indexes(ii)) = 1;
end
Code is the same up to here. Now, ensure that every column has exactly one nonzero entry. Note that the loc rows can be assigned more than one 1 value by this process, up to sb_degree.
% Add one entry to each unfilled column of M on an unfilled row of M(loc,:)
missing = find(sum(M,1) == 0);
for fillcol = missing
addtoidx = randi(numel(loc)); % select random row from loc
fillrow = loc(addtoidx); % row number in M
M(fillrow, fillcol) = 1;
if (sum(M(fillrow,:)) >= sb_degree) % this row is now full
loc(addtoidx) = []; % remove it from loc
end
end
And finally, fill up the loc rows with sb_degree ones.
% Fill the rows that need more than a single unit entry
% but still contain less than sb_degree
for jj = 1:length(loc)
thisrow = M(loc(jj),:); % unfilled row from M
emptycols = find(thisrow == 0); % indices of columns of thisrow not yet filled
fillidx = randperm(numel(emptycols), sb_degree - sum(thisrow));
M(loc(jj), emptycols(fillidx))=1;
end