Problem with the mathematical formulation of "qubitization"

Question

In this research paper, the authors introduce a new algorithm to perform Hamiltonian simulation.

The beginning of their abstract is

Given a Hermitian operator $\hat{H} = \langle G\vert \hat{U} \vert G\rangle$ that is the projection of an oracle $\hat{U}$ by state $\vert G\rangle$ created with oracle $\hat{G}$, the problem of Hamiltonian simulation is approximating the time evolution operator $e^{-i\hat{H}t}$ at time $t$ with error $\epsilon$.

In the article:

• $\hat{G}$ and $\hat{U}$ are called "oracles".
• $\hat{H}$ is an Hermitian operator in $\mathbb{C}^{2^n} \times \mathbb{C}^{2^n}$.
• $\vert G \rangle \in \mathbb{C}^d$ (legend of Table 1).

My question is the following: what means $\hat{H} = \langle G\vert \hat{U} \vert G\rangle$? More precisely, I do not understand what $\langle G\vert \hat{U} \vert G\rangle$ represents when $\hat{U}$ is an oracle and $\vert G \rangle$ a quantum state.

Answer 1

You want to start by being careful with the sizes of the operators. $\hat U$ acts on $q$ qubits, and $\hat H$ acts on $n<q$ qubits. I believe that $|G\rangle$ is a state of $q-n$ qubits. So, what we really need to talk about is two distinct sets of qubits. Let me call them sets $A$ and $B$. $A$ contains $n$ qubits, and $B$ contains $q-n$ qubits. I'll use subscripts to denote which qubits the different operators and states act upon:

$$ \hat H_A=(\langle G|_B\otimes\mathbb{I}_A)\hat U_{AB}(|G\rangle_B\otimes\mathbb{I}_A) $$