How to build an algorithm with quantum circuits to calculate the outer product of two states?

Question

I want to directly use quantum circuits or quantum algorithms to obtain the outer product of $U_A|a\rangle$ (it is a column vector) and another column vector $U_B|b\rangle$, what are the reference ideas?

Answer 1

I don't think that quantum computing can provide a speedup here, as long as the representation of the outer product you're looking for is classical.

The outer product of $|a\rangle$ and $|b\rangle$, two column vectors of respective sizes $m$ and $n$ can be simply done in $\mathcal{O}(mn)$, carrying out the product for each term of the outer product. More precisely, assuming $p$-bit number, a multiplication takes around $p^2$ operations, so the final complexity is $\mathcal{O}\left(mnp^2\right)$.

---

Classical representation of the outer product

Now, where is it possible to gain a speedup using quantum computing? No matter what you do, as long as you want a classical representation of the outer product, you will have to perform at least $\mathcal{O}(mnp)$ operations (at least to write down the results). Indeed, measuring a quantum system will only result in a single component of the outer product. You may think that you could have several terms at once by increasing the number of qubits you're dealing with, but that's also true for a classical computer: you can run the computation in parallel.

The only gain you could get is if multiplying two numbers was faster, from a complexity point of view, on a quantum computer. For instance, an algorithm performing a multiplication in $\mathcal{O}\left(p\log(p)\right)$ operations would result in an algorithm to compute the outer product in $\mathcal{O}\left(mnp\log(p)\right)$, which would be better than the classical one.

However:

1. I'm not aware of such an algorithm.
2. The gain would be mostly theoretical, as $p$ is rarely larger than $64$.
3. This assumes that encoding a quantum state from a classical number, performing the quantum algorithm and measuring it is faster than doing the multiplication classically.

Thus, though it may be possible to obtain a better complexity than with using a classical computer, the overall gain seems at best marginal.

---

Quantum representation of the outer product in $\mathcal{O}(1)$ if the second vector is real##

Note that this reasoning holds as long as you're after a classical representation of the outer product. If you're looking for a quantum representation in order to use it as part of a larger quantum algorithm, then a (trivial) quantum speedup is possible. Let us call the two column vectors $|a\rangle$ and $|b\rangle$. Their outer product is: $$|a\rangle\langle b|=\sum_{i=0}^{2^m-1}\sum_{j=0}^{2^n-1}a_i\overline{b_j}|i\rangle\langle j|$$ Now, let us assume that we have a quantum representation of $|a\rangle$ and $|b\rangle$. The state of the resulting quantum system is: $$|a\rangle\otimes|b\rangle=\sum_{i=0}^{2^m-1}\sum_{j=0}^{2^n-1}a_ib_j|i,j\rangle$$ If $b$ only has real coordinates, then $|a\rangle\otimes|b\rangle$ is already a representation of the outer product of $|a\rangle$ and $|b\rangle$. In that case, the complexity is trivially $\mathcal{O}(1)$ (assuming $|a\rangle$ and $|b\rangle$ are given).

Choosing a different representation which would lead to writing down the coordinates of $|a\rangle$ and $|b\rangle$ would be I think equivalent to the classical case, and would thus provide no speedup.