2
$\begingroup$

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.

$\endgroup$

2 Answers 2

1
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ Actually, the second reference you mentioned shows in Section II.D that we can also block encode rectangular matrices. $\endgroup$
    – Jose Brox
    Commented Feb 8 at 22:09
1
$\begingroup$

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.

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.