Linear combination of unitaries (LCU) block encoding allows for the simulation of a Hermitian operator $H$ on a quantum computer. Specifically, it leverages the representation of the Hermitian matrix as a weighted sum of unitaries in order to embed $H$ into a larger unitary matrix. The exact implementation of this protocol has been discussed in a variety of articles. In this work, we consider a set of possible implementations of an LCU consisting of $L$ terms, detailing the concrete constructions for the required $PREP$ and $SELECT$ operators. The complexity of these is given in terms of T-gate count and we refrain from the use of black box oracle calls. We discuss a protocol allowing for the implementation of $SELECT$ with complexity $\mathcal{O}(L)$. The presented $PREP$ operator circuit requires a T-gate count scaling with $\mathcal{O}(L+\log(L/\epsilon))$, for $\epsilon$ the largest absolute error tolerated in the prepared coefficients. We find that by leveraging a tunable number of up to $\sim (\gamma\log (L/\epsilon))$ dirty qubits, the T-gate complexity of $PREP$ may be reduced to $\mathcal{O}(L/\gamma + \gamma \log (L/\epsilon))$. For the optimal value $\gamma=\mathcal{O}\left(\sqrt{L/\log (L/\epsilon)}\right)$, this leads to a complexity of $\mathcal{O}(\sqrt{L\log (L/\epsilon)})$.     «

Linear combination of unitaries (LCU) block encoding allows for the simulation of a Hermitian operator $H$ on a quantum computer. Specifically, it leverages the representation of the Hermitian matrix as a weighted sum of unitaries in order to embed $H$ into a larger unitary matrix. The exact implementation of this protocol has been discussed in a variety of articles. In this work, we consider a set of possible implementations of an LCU consisting of $L$ terms, detailing the concrete construction...     »