# Can any matrix be translated into a quantum circuit?

Can any matrix be translated into quantum circuit? Is there any limitation to the qubits length or any other constraints to the matrix? Can any matrix be presented by a unique quantum circuit or are there several options to present it?

• Jan 1 at 17:33

It depends on what you mean by "translated". Let's say you're given a matrix $$A$$ and an input state $$|\psi\rangle$$. I imagine that what you'd be seeking is the ability to produce a state $$A|\psi\rangle$$. There are a few possibilities depending on the properties of $$A$$.

• If $$A$$ is unitary, i.e. $$A$$ is square and $$AA^\dagger=I$$, then you can directly convert it into a quantum circuit. This translation is very far from unique, and there are also no guarantees about efficiency (indeed, most $$2^n\times 2^n$$ matrices, while implemented on $$n$$ qubits, would require a number of time steps that is roughly exponential in $$n$$).
• If $$A$$ has singular values bounded below 1, you can always extend the matrix (by no more than doubling the larger of the number of rows and columns, producing a square matrix) such that the extension is unitary. As in the previous step, you can then implement that unitary. It will probably also include some probability of failure (basically, you perform a measurement to detect whether the output is in the extended or non-extended bit of the space). In that case, your output state gets rescaled so that you get $$rA|\psi\rangle$$, with $$r\in\mathcal{C}$$ such that the output has length 1 (but you might choose not to make the measurement, in which case the rescaling doesn't happen).
• If $$A$$ has singular values larger than 1, you will not succeed with the exact task as defined. However, if you already know something about $$A$$, e.g. its largest singular value, or an upper bound on the largest singular value, $$s$$, you can redefine $$\tilde A=A/s$$ and follow the previous step.

The last case, up to a scale factor, lets you use essentially any matrix. This is, more or less, what the HHL algorithm lets you do.

Not all matrices are allowed in the conventional quantum circuit model. That is, quantum circuits composed of gates correspond to unitary matrices that preserve distances, e.g., matrices $$U$$ such that:

$$U^\dagger U= U U^\dagger = I.$$

These matrices certainly are square, and have other interesting properties when restricted to real (or even boolean) entries - when the entries are selected from $$\{0,1\}$$ the matrix is a permutation matrix.

Further even given such a permutation matrix, along with a restricted set of gates (such as CCNOT and/or CSWAP), a simple counting argument shows that there must be multiple circuits realizing said matrix. Even classically, when given a boolean function as a truth-table, we can realize the function with many different classical circuits composed of NAND gates or NOR gates, etc.