Assume one is given two oracle circuits providing access to matrices $$A_{ij}$$ and $$B_{ij}$$ as follows (see eq. (6.2) here): $$$$O_A |0\rangle|i\rangle|j\rangle=\left(A_{ij}|0\rangle+\sqrt{1-|A_{ij}|^2}|1\rangle\right)|i\rangle|j\rangle \, ,\\ O_B |0\rangle|i\rangle|j\rangle=\left(B_{ij}|0\rangle+\sqrt{1-|B_{ij}|^2}|1\rangle\right)|i\rangle|j\rangle \, ,$$$$ where indices $$i$$ and $$j$$ are encoded with qubits in a the binary form. The said representation will be referred to as block encoding.

I am wondering if one could construct a circuit $$O_{A+B}$$ implementing $$$$O_{A+B} |0\rangle|i\rangle|j\rangle=\Bigl((A_{ij}+B_{ij})|0\rangle+\ldots|1\rangle\Bigr)|i\rangle|j\rangle \, .$$$$

I placed $$\ldots$$ instead of $$\sqrt{1-|A_{ij}+B_{ij}|^2}$$ just to indicate that using ancillas and measurements would be OK.

UPDATE: A BRUTE-FORCE SOLUTION

For completeness I add a straightforward implementation based on the conversion to query oracles.

1. Use the controlled rotation circuit (see Proposition 4.7 here) to convert the block-encoded oracles to query-encoded oracles $$\widetilde{O}_A$$ and $$\widetilde{O}_B$$: $$\widetilde{O}_A |0\rangle|i\rangle|j\rangle = |\widetilde{A}_{ij}\rangle|i\rangle|j\rangle \, ,\\ \widetilde{O}_B |0\rangle|i\rangle|j\rangle = |\widetilde{B}_{ij}\rangle|i\rangle|j\rangle \, .$$

2. The consecutive application of oracles renders then $$\widetilde{O}_A \widetilde{O}_B |0\rangle|i\rangle|j\rangle = \widetilde{O}_A |\widetilde{B}_{ij}\rangle|i\rangle|j\rangle = |\widetilde{A}_{ij} + \widetilde{B}_{ij}\rangle|i\rangle|j\rangle \, .$$

Would be nice to avoid converting to query oracles.

• Given that $A_{ij}+B_{ij}$ is not necessarily in the unit ball anymore, what other restrictions are you envisioning for $A$ and $B$? Should they be normalized? And since generally $A$ and $B$ would be known classically, why not add them classically and then query the result? Feb 14, 2023 at 9:45

You can do this using linear combination of unitaries (LCU) technique. It is described in the paper you mentioned (section 7.3). More specifically, see example 7.12

• Seems like an overkill. I added some edits to the question. May 19, 2022 at 1:57