Time complexity of block-encoded matrices

Question

A lot of modern quantum computation has this idea of "block-encoding" matrices; loosely, this is encoding a non-unitary matrix into the top left corner of a larger unitary matrix. This technique is referenced a lot, but I don't see how it can be implemented with quantum circuits.

Suppose we were given an arbitrary matrix, $C$. This matrix can be non-unitary and non-square. As a result, it cannot be represented by a quantum circuit. How is it possible that we can "block-encode" this into a quantum circuit (a universal gate set acted on by tensor product operations) in a reasonable amount of steps?

Mathematically, the technique makes sense when the spectral norm is less than $1$. But I don't see how it makes sense in practice and complexity-wise.

Answer 1

The matrix $C$ you block-encode can be non-unitary but must be square. There are many techniques for embedding $C$ into a unitary matrix. Examples of explicit quantum circuits are provided in this very recent paper: https://arxiv.org/abs/2203.10236

Another interesting paper on this subject is: https://arxiv.org/abs/2105.02859

Answer 2

From Lecture Notes on Quantum Algorithms for Scientific Computation by Lin:

Of course, if $A$ is a dense matrix without obvious structures, any input model will be very expensive (e.g. exponential in $n$) to implement. Therefore a commonly assumed input model is $s$-sparse, i.e., there are at most $s$ nonzero entries in each row / column of the matrix. Furthermore, we have an efficient procedure to get access to the location, as well as the value of the nonzero entries. This in general can again be a difficult task given that the number of nonzero entries can still be exponential in $n$ for a sparse matrix. Some dense matrices may also be efficiently block encoded on quantum computers.