From this we see that the result is robust in the sense that the value of $\omega$ required shrinks at most polynomially with the number of terms in the Hamiltonian.  However, as the number of terms increases polynomially with the number of qubits for many systems of interest, this means that in the worst case scenario a very accurate preparation of the pseudo-Choi state will be needed in order to achieve the requisite accuracy for the entire Hamiltonian.

§ CONCLUSION AND OUTLOOK

In this work we have provided a new approach to Hamiltonian learning that draws inspiration from the state to channel isomorphism to yield a state from which the Hamiltonian can be directly learned and can be prepared using a simple quantum circuit.  We further are able to show for this work that such approaches can easily learn $k$-local Hamiltonians, which is a broader class of Hamiltonians than the low-intersection case considered in most other Hamiltonian learning works.  We further consider the learning problem in the case where amplitude estimation is used and also further accelerate it using mean-value estimation algorithms to achieve optimal, $1/\epsilon$, scaling with the error tolerance.

There are a number of interesting problems revealed by this work.  While our approach extends the scope of recent work on Hamiltonian learning (<cit.>) to include the more general class of $k$-local Hamiltonians, the major caveat is that we require backwards time evolution to generate the pseudo-Choi state. One area of interest for future work would be to find methods of generating pseudo-Choi-like states efficiently without the need for backwards time evolution.

The recent work by Huang et al. <cit.> introduced an interesting method for reshaping Hamiltonians into non-interacting patches, allowing different parts of the Hamiltonian to be learned in parallel. If these methods could be applied to our approach, it may be possible to create pseudo-Choi states for separate parts of the Hamiltonian instead of the entire Hamiltonian, potentially allowing for longer evolution times.

More broadly, however, this form of a block-encoding of the Hamiltonian within a quantum state allows much more flexible learning than existing approaches permit.  This opens up a host of different learning problems that could be considered including Lindbladian learning for open systems, time-dependent Hamiltonian learning and even applications of Hamiltonian learning methods to learn the structure of quantum walks.  It is our belief that these results represent a first step towards a broader understanding of learning dynamical models for quantum systems and in turn a characterization of the physical models that can or cannot be efficiently learned from experiment.

§.§ Acknowledgements

JC acknowledges funding from NSERC and CIFAR.  NW would like to acknowledge funding for this work from Google Inc. This material is based upon work supported by the U.S. Department of Energy, Office of Science, National Quantum Information Science Research Centers, Co-design Center for Quantum Advantage (C2QA) under contract number DE-SC0012704 (PNNL FWP 76274).

Missing 'biblatex' package
The bibliography requires the 'biblatex' package.

Springer Science
Business Media LLC

journaltitleNature Reviews Physics
titleQuantum certification and benchmarking

American Physical Society

journaltitlePhys. Rev. A
titleRandomized benchmarking of quantum gates

American Physical Society

journaltitlePhys. Rev. Lett.
titleWhat Randomized Benchmarking Actually Measures

American Physical Society

journaltitlePRX Quantum
titleGeneral Framework for Randomized Benchmarking

journaltitlePhysical Review Letters
titlePractical characterization of quantum devices without tomography

IOP Publishing

journaltitleNew Journal of Physics
titleRobust online Hamiltonian learning

American Physical Society

journaltitlePhys. Rev. Lett.
titleHamiltonian Learning and Certification Using Quantum Resources

journaltitleNature Physics
titleExperimental quantum Hamiltonian learning

titleScalable Bayesian Hamiltonian learning

booktitle2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS)
titleSample-efficient learning of quantum many-body systems

titleOptimal learning of quantum Hamiltonians from high-temperature Gibbs states

journaltitlearXiv preprint arXiv:2201.00190
titlePractical and Efficient Hamiltonian Learning

titlePractical Black Box Hamiltonian Learning

American Physical Society

journaltitlePhys. Rev. Lett.
titleLearning Many-Body Hamiltonians with Heisenberg-Limited Scaling

Springer Science
Business Media LLC

journaltitleNature Physics
titlePredicting many properties of a quantum system from very few measurements

titleNearly Optimal Quantum Algorithm for Estimating Multiple Expectation Values
Quantum Physics (quant-ph),FOS: Physical sciences,FOS: Physical sciences

journaltitleSIAM Journal on Computing
titleEquivalences and separations between quantum and classical learnability

American Physical Society (APS)

journaltitlePhysical Review A
titleImproved simulation of stabilizer circuits

ACM New York, NY, USA

journaltitleACM Sigact News
titleGuest column: A survey of quantum learning theory

titleShadow Tomography of Quantum States

Institute of Electrical
Electronics Engineers (IEEE)

journaltitleIEEE Transactions on Information Theory
titleHadamard-Free Circuits Expose the Structure of the Clifford Group

titleA simple method for sampling random Clifford operators
Quantum Physics (quant-ph),FOS: Physical sciences,FOS: Physical sciences

journaltitleProceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing
titleQuantum singular value transformation and beyond: exponential improvements for quantum matrix arithmetics

Rinton Press, Incorporated Paramus, NJ

journaltitleQuantum Information & Computation
titleHamiltonian simulation using linear combinations of unitary operations

Verein zur Förderung des Open Access Publizierens in den Quantenwissenschaften

titleQuantum SDP-solvers: Better upper and lower bounds

booktitleProceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms
titleOptimizing quantum optimization algorithms via faster quantum gradient computation

journaltitlePhysical review letters
titleFixed-point quantum search with an optimal number of queries

Springer Science
Business Media LLC

journaltitleJournal of Statistical Physics
titleRelations for Certain Symmetric Norms and Anti-norms Before and After Partial Trace

American Physical Society

journaltitlePhys. Rev. Lett.
titleQuantum Algorithm for Linear Systems of Equations

journaltitleSIAM Journal on Computing
titleQuantum Algorithm for Systems of Linear Equations with Exponentially Improved Dependence on Precision

American Mathematical Society

titleClassical and Quantum Computation

Dagstuhl, Germany

Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik

annotationKeywords: quantum algorithms, semidefinite program, convex optimization
booktitle46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)
seriesLeibniz International Proceedings in Informatics (LIPIcs)
titleQuantum SDP Solvers: Large Speed-Ups, Optimality, and Applications to Quantum Learning

Verein zur Förderung des Open Access Publizierens in den Quantenwissenschaften

titleHigh-precision quantum algorithms for partial differential equations

titleExponential quantum speedup in simulating coupled classical oscillators

American Physical Society

journaltitlePhys. Rev. Lett.
titleSolvable Model of a Spin-Glass

titlePhysics and Complexity: a brief spin glass perspective

Interscience Publishers

titleThe Probabilistic Method (Second edition.)

§ ESTIMATING THE HAMILTONIAN COEFFICIENTS (PAULI SHADOWS)

Previously we considered the use of Clifford-based shadows procedure for estimating the Hamiltonian coefficients, but it is also possible to use the Pauli version of classical shadows. Since the operators involved in the analysis of the Pauli-based shadows are all single-qubit operators, we introduce some notation to indicate the specific 2 dimensional subspace an operator acts on, as well as the qubit that a measurement result corresponds to. First, since the subscript $i$ already denotes the round of measurement each bit string $\ket{b_i}$ came from, we use the notation $\ket{b_i[j]}$ to refer to specific bits of $\ket{b_i}$. More specifically,

\begin{align}
\ket{b_i} &= \bigotimes_{j=0}^{\eta-1} \ket{b_i[j]}
\end{align}

Once again, recall that $\ket{b_i}$ is a classical bit string, and Dirac notation is only used for presentation purposes. Second, the random unitaries, $U_i$, applied during each round of measurement are tensor products of single-qubit Clifford operators. Therefore, we write them as

\begin{align}
U_i = \bigotimes_{j=0}^{\eta-1} U_{(i,j)},
\end{align}

where $U_{(i,j)}$ is a single-qubit operator acting on the $j^{th}$ qubit. Similarly, we can write the Hamiltonian terms $H_l$ as

\begin{align}
H_l &= \bigotimes_{j=0}^{\eta-1} H_{(l,j)}
\end{align}

We again consider the process (viewed as a channel) of taking the expectation value over all measurement outcomes and unitaries in the group $\text{Cl}(2)^{\otimes \eta}$. Rather than a single depolarizing channel (as in the case where Clifford operations from $\text{Cl}(2^\eta)$ were randomly sampled), this can be viewed as $\eta$ depolarizing channels, each acting on a single qubit <cit.>. Inverting these channels as before gives the classical shadow specified in Definition <ref>.

Given $N$ copies of an $\eta$-qubit quantum state $\rho$, the classical shadows procedure based on random Pauli measurements returns a classical shadow of $\rho$ which is of the form

\begin{align}
\hat{\rho} &= \{\hat{\rho}_i | i \in \mathbb{Z}_N\},
\end{align}

\begin{align}
\hat{\rho}_i = \bigotimes^{\eta-1}_{j=0} \Big(3U_{(i,j)}^\dagger \ket{b_i[j]}\bra{b_i[j]} U_{(i,j)} -\Id \Big)
\end{align}

Recall that $i$ denotes the round of measurement and $j$ denotes the qubit; the unitary applied to $\rho$ during the $i^{th}$ round of the classical shadows is $U_i = \bigotimes_{j=0}^{\eta-1} U_{(i,j)}$, and $\ket{b_i[j]}$ refers to the outcome of measuring the $j^{th}$ qubit in the computational basis during the $i^{th}$ round of the classical shadows procedure.

Just as in the case where the Clifford flavour of classical shadows was used, the goal of this section is to extract the Hamiltonian coefficients from the pseudo-Choi state - that is, to solve the Pseudo-Choi Hamiltonian Learning problem (PC HLP). However, instead of generating a classical shadow of the pseudo-Choi state, we begin by performing a partial trace over the ancillary system $A$ to simplify the learning process. This results in the following state which will serve as our learning resource:

\begin{align}
\rho = & \frac{1}{d\alpha^2}\Big(H^2 \otimes \ket{0}_C\bra{0}_C  + H \otimes \ket{0}_C\bra{1}_C   +  H \otimes \ket{1}_C\bra{0}_C +  \Id \otimes \ket{1}_C\bra{1}_C \Big)\label{eq:PartialChoiDensityOp},
\end{align}

where $d=2^n$ is the dimension of the Hilbert space the Hamiltonian acts on, and $\alpha = \sqrt{\norm{\mathbf{c}}_2^2 + 1}$. The set of decoding operators whose expectation values correspond to the Hamiltonian coefficients is also modified as per Definition <ref>:

Let the set of decoding operators be defined as

\begin{align}
\boldsymbol{O} & \equiv \{ O_l | l \in \mathbb{Z}_{M} \}
\end{align}

\begin{align}
O_l &= \frac{H_l  \otimes X_C}{2}
\end{align}

and $H_l$ is one of the $M$ Hamiltonian terms.

Furthermore, we define

\begin{align}
O_{\alpha} & \equiv \Id \otimes \ket{1}_C\bra{1}_C
\end{align}

By Proposition <ref>, we have that

\begin{align}
{\rm Tr}(\rho O_{l}) = \frac{c_l}{\alpha^2},
\end{align}

where $c_l$ is the $l^{th}$ Hamiltonian coefficient, and $\alpha$ is the normalization constant of the pseudo-Choi state (<ref>). Furthermore,

\begin{align}
{\rm Tr}(\rho O_{\alpha}) = \frac{1}{\alpha^2}
\end{align}

Now that we have a set of operators whose expectation values correspond to the Hamiltonian coefficients when acting on the resource state $\rho$ (<ref>), we seek to approximate these expectation values using a classical shadow of $\rho$. Recall that to obtain $\rho$ we traced out the ancillary system $A$ from the pseudo-Choi state (<ref>). To generate a classical shadow of $\rho$, starting from the pseudo-Choi state, we must therefore ignore the ancilla system $A$ during the classical shadows procedure, meaning that all random (single-qubit) Clifford operations and measurements are only on $n + 1$ qubits ($n$ qubits for the system on Hilbert space $\mathcal{H}_S$ and one qubit for ancilla on Hilbert space $\mathcal{H}_C$). In terms of the definition of the classical shadow, we let $\eta = n+1$ so that a classical shadow is made up of $N$ components of the form

\begin{align}
\hat{\rho}_i & = \bigotimes_{j=0}^{n} \Big( 3U_{(i,j)}^\dagger \ket{b_i[j]}\bra{b_i[j]}U_{(i,j)} - \Id\Big)
\end{align}

With this, and the definition of the decoding operators given in Definition <ref>, we can write the expectation values of interest in the explicit forms given in Claim <ref>.

Let $X_C$ denote the single-qubit Pauli X operation acting on $\mathcal{H}_C$, and let $H_{l,j}$ be the single qubit Pauli operator from $H_l$ that acts on the $j^{th}$ qubit (recall that each $H_l$ is an $n$-qubit Pauli operator on $\mathcal{H}_S$).

\begin{align}
{\rm Tr}(\hat{\rho}_i O_{l}) &= \frac{3}{2} \bra{b_i[n]} U_{(i,n)} X_C U_{(i,n)}^\dagger \ket{b_i[n]}\prod_{j=0}^{n-1} \Big(3 \bra{b_i[j]} U_{(i,j)} H_{(l,j)} U_{(i,j)}^\dagger \ket{b_i[j]} - {\rm Tr}(H_{(l,j)}) \Big)  \label{eq:EfficientTrace4},
\end{align}

\begin{align}
{\rm Tr}(\hat{\rho}_i O_\alpha) & = 3 \abs{\bra{b_i[n]} U_{(i,n)}\ket{1}_C }^2 - 1 \label{eq:EfficientTrace5}
\end{align}

Recall that $\hat{\rho}_i$ is on $n+1$ qubits, $H_l$ is on $n$ qubits, and $X_C$ is the single qubit Pauli X operator. Then,

\begin{align}
\begin{split}
{\rm Tr}[\hat{\rho}_i O_{l}] =& {\rm Tr}\left[ \left(\bigotimes_{j=0}^{n} \Big( 3U_{(i,j)}^\dagger \ket{b_i[j]}\bra{b_i[j]}U_{(i,j)} - \Id\Big)\right) \left(\frac{H_l\otimes X_C}{2}\right)   \right]\\
=& \frac{1}{2}{\rm Tr}\left[ \left(\bigotimes_{j=0}^{n} \Big( 3U_{(i,j)}^\dagger \ket{b_i[j]}\bra{b_i[j]}U_{(i,j)} - \Id\Big)\right) \left(\left(\bigotimes_{j=0}^{n-1} H_{(l,j)}\right)\otimes X_C \right)  \right]\\
= & \frac{1}{2}{\rm Tr}\Bigg[ \Bigg(\bigotimes_{j=0}^{n-1} \Big( 3U_{(i,j)}^\dagger \ket{b_i[j]}\bra{b_i[j]}U_{(i,j)} H_{(l,j)} - H_{(l,j)} \Big)\Bigg) \\
& \otimes \Bigg(3U_{(i,n)}^\dagger\ket{b_i[n]}\bra{b_i[n]}U_{(i,n)} X_C - X_C\Bigg) \Bigg]\\
=& \frac{3}{2}{\rm Tr}\Bigg[ U_{(i,n)}^\dagger\ket{b_i[n]}\bra{b_i[n]}U_{(i,n)} X_C  \Bigg] \prod_{j=0}^{n-1} {\rm Tr}\Bigg[ 3U_{(i,j)}^\dagger \ket{b_i[j]}\bra{b_i[j]}U_{(i,j)} H_{(l,j)} - H_{(l,j)} \Bigg]\\
=& \frac{3}{2} \bra{b_i[n]}U_{(i,n)} X_C U_{(i,n)}^\dagger\ket{b_i[n]}  \prod_{j=0}^{n-1}  \left(3 \bra{b_i[j]}U_{(i,j)} H_{(l,j)}U_{(i,j)}^\dagger \ket{b_i[j]} - {\rm Tr}\left[H_{(l,j)} \right]\right),
\end{split}
\end{align}

which gives the result of equation (<ref>).

\begin{align}
\begin{split}
{\rm Tr}[\hat{\rho}_i O_\alpha]  =& {\rm Tr}\left[ \Bigg( \bigotimes_{j=0}^{n} \Big( 3U_{(i,j)}^\dagger \ket{b_i[j]}\bra{b_i[j]}U_{(i,j)} - \Id\Big)\Bigg)   \Bigg( \Id_S \otimes \ket{1}_C \bra{1}_C\Bigg) \right]\\
=& {\rm Tr}\Bigg[ \Bigg( \bigotimes_{j=0}^{n-1} \Big( 3U_{(i,j)}^\dagger \ket{b_i[j]}\bra{b_i[j]}U_{(i,j)} - \Id\Big)\Bigg)   \\
& \otimes\Bigg( \Big( 3U_{(i,n)}^\dagger \ket{b_i[n]}\bra{b_i[n]}U_{(i,n)} - \Id\Big) \ket{1}_C \bra{1}_C\Bigg) \Bigg]\\
= &  \prod_{j=0}^{n-1} \Bigg({\rm Tr}\left[  3U_{(i,j)}^\dagger \ket{b_i[j]}\bra{b_i[j]}U_{(i,j)}\right] - {\rm Tr}\left[ \Id\right]\Bigg)   \\
& \Bigg(  3\bra{b_i[n]}U_{(i,n)}\ket{1}_C \bra{1}_C U_{(i,n)}^\dagger \ket{b_i[n]} - 1 \Bigg)\\
=&   3\bra{b_i[n]}U_{(i,n)}\ket{1}_C \bra{1}_C U_{(i,n)}^\dagger \ket{b_i[n]} - 1,
\end{split}
\end{align}

which gives the result of equation (<ref>), completing the proof.

Since only single qubit operations are required, computing each trace takes $\mathcal{O}(n)$ time, and requires $\mathcal{O}(n)$ memory to store all intermediate values. In fact, if we focus on $k$-local Hamiltonians, each Hamiltonian term $H_l$ only contains at most $k$ non-identity Paulis, so only $\mathcal{O}(k)$ operations are required to compute each value.

As was the case with the random Clifford measurements, it is unnecessary to store the entire classical shadow:

If the random Pauli measurement version of the classical shadows procedure is performed, the resulting classical shadow of size $N$ can be stored in the following way:

\begin{align}
\ket{\hat{\rho}} &= \{\ket{\hat{\rho}_{i}} | i \in \mathbb{Z}_N \},
\end{align}

\begin{align}
\ket{\hat{\rho}_{i}} &= \bigotimes_{j=1}^{n+1} U_{(i,j)}^\dagger \ket{b[j]}_{i}
\end{align}

Here we use Dirac notation to describe the resultant bit-strings, however note that as $\ket{b[j]}_{i}$ is a classical bit, so $\ket{\hat{\rho}_i}$ is a computational basis vector which corresponds to a one-hot unary representation of a bit string.

Algorithm <ref> describes the full procedure for estimating the Hamiltonian coefficients. Note that it uses the “compressed” Pauli shadows given by Definition <ref>. Also, there is no need to use the Tableau or SIP Algorithms of <cit.> to store intermediary values or compute the expectation values since all the operations involved are on single qubits.

$\mathtt{FindCoeffPauli}(\rho_c^{\otimes N}, \boldsymbol{H}, n, N)$: Determine the Vector of Hamiltonian Coefficients from $\rho_c$

$\rho_c^{\otimes N} $: Collection of $N$ pseudo-Choi states on $n$ qubits, each on Hilbert space $\mathcal{H}_S \otimes \mathcal{H}_A \otimes \mathcal{H}_C$

$\boldsymbol{H}$: Set of M k-local Hamiltonian terms $H_l$ whose coefficients $c_m$ are desired

$\rho_c^{\otimes N} $ is a quantum state, whereas $\boldsymbol{H}$ is a classical set of operators

* Initialize the array of Hamiltonian coefficients

Let $\hat{\textbf{c}} \gets \begin{bmatrix} 0, 0, ..., 0 \end{bmatrix}_{1\times M}$ and let $\hat{\textbf{c}}_l$ denote the $l^{th}$ element of $\hat{\textbf{c}}$

* Generate and store the classical shadow

Use copies of $\rho_c$ to generate $\hat{\rho}$, a classical shadow of size $N$ of ${\rm Tr}_A(\rho_c)$, by limiting the random Pauli measurement based classical shadows procedure to the space $\mathcal{H}_S \otimes \mathcal{H}_C$ to effectively perform the partial trace over $\mathcal{H}_A$.

Store $\hat{\rho}$ in classical memory (ie. store each vector $\ket{\hat{\rho}_i

See Definition <ref> of a classical shadow

* Generate an estimate of ${\rm Tr}(\rho O_{l}) = \frac{c_l}{\alpha^2}$ for each corresponding Hamiltonian term

Let $\hat{\textbf{o}} \gets \begin{bmatrix} 0, 0, ..., 0 \end{bmatrix}_{1\times N}$ and let $\hat{\textbf{o}}_i$ denote the $i^{th}$ element of $\hat{\textbf{o}}$

$\mathtt{For}$ $l$ $\mathtt{from}$ $0$ $\mathtt{to}$ $M-1$:

$\mathtt{For}$ $i$ $\mathtt{from}$ $0$ to $N-1$:

$\hat{o}_i \gets \frac{3}{2} \bra{b_i[n]} U_{(i,n)} X_C U_{(i,n)}^\dagger \ket{b_i[n]}\prod_{j=0}^{n-1} \Big(3 \bra{b_i[j]} U_{(i,j)} H_{(l,j)} U_{(i,j)}^\dagger \ket{b_i[j]} - {\rm Tr}(H_{(l,j)}) \Big)$

Equal to ${\rm Tr}\left(\hat{\rho_i} O_l\right)$ as per Equation (<ref>)

$\hat{\textbf{c}}_l \gets \mathtt{MedianOfMeans}(\hat{\textbf{o}})$

* Generate an estimate of ${\rm Tr}(\rho O_{\alpha}) = \frac{1}{\alpha^2}$

$\mathtt{For}$ $i$ $\mathtt{from}$ $0$ to $N-1$:

$\hat{o}_i \gets 3 \abs{\bra{b_i[n]} U_{(i,n)}\ket{1}_C }^2 - 1$
Equal to ${\rm Tr}(\hat{\rho}_i O_\alpha)$ as per Equation (<ref>)

$\hat{o}_{\alpha} \gets \mathtt{MedianOfMeans}(\hat{\textbf{o}})$

* Remove the factor of $\frac{1}{\alpha^2}$ from the Hamiltonian coefficients

Let $\hat{\textbf{c}} \gets \frac{\hat{\textbf{c}}}{\hat{o}_{\alpha}}$

* Output the vector of Hamiltonian coefficients

Return $\hat{\textbf{c}} =
\begin{bmatrix} \hat{c}_0, \hat{c}_1, ..., \hat{c}_{M-1} \end{bmatrix}$

Since all the operations involved in this process are single-qubit operations, computing the required inner products is more efficient than in the case of Clifford-based shadows. In particular, the number of computations required to do so is at most $\mathcal{O}(MN)$ where a sufficient value of $N$ is given in equation (<ref>). Note that this value of $N$ includes a factor of $4^k$, where $k$ is the locality of the Hamiltonian. Meanwhile, the Clifford-based procedure requires $\mathcal{O}(MNn^3)$ computations to calculate the necessary inner products, where the sufficient value of $N$ is given in Theorem <ref> and does not contain the factor of $4^k$. Therefore, unless the value of $k$ is large, the Pauli-based procedure will have the better post-processing performance, at the expense of having a slightly higher sample complexity. Furthermore, as in the Clifford case, these operations can be done in parallel, greatly reducing the computation time.

§.§ Sample Complexity Upper Bound

The sample complexity of this method is very similar to that of the case where Clifford based classical shadows was used to learn the pseudo-Choi state. The key difference is that when the random Pauli measurement version of classical shadows is used, the upper bound on the shadow norm in Lemma <ref> no longer applies. Instead, we have the following result:

Let the set {$O_{\alpha}$} $\cup$  $\{O_l \mid l \in \mathbb{Z}_{M}\}$ be denoted by $\textbf{O} \equiv \{O_i \mid i \in \mathbb{Z}_{2M}\}$. Note that these operators act non-trivially on at most $k+1$ qubits. If using the random Pauli measurement version of the classical shadows procedure to predict the expectation values of the operators in the set, the shadow norm of each operator is at most

\begin{align}
\norm{O_{i}}^2_{shadow} \leq 3^{k+1}
\end{align}

This results directly from <cit.>, where Huang et al. showed that for classical shadows based on random Pauli measurements

\begin{align}
\norm{O}^2_{shadow} \leq 3^{k}
\end{align}

where $O$ is a single $k$-local Pauli operator.

By the same argument as in the case of Clifford based classical shadows, this upper bound on the shadow norm leads to a sample complexity of

\begin{align}\label{eq:NbdPauli}
N \in \mathcal{O}\left( \frac{3^k \alpha^4 (c_{\rm max} + 1) M\log\left(M/\delta\right) }{\epsilon^2}  \right)
\end{align}

§ PROOFS AND TECHNICAL RESULTS

§.§ Proof of Equation (<ref>)

\begin{align}
\bra{\Phi_d}_{SA}(H^2\otimes \Id_A) \ket{\Phi_d}_{SA}
& = \frac{\sum_{i=0}^{d-1}\bra{i}_S \bra{i}_A (H^2\otimes \Id_A) \sum_{j=0}^{d-1}\ket{j}_S \ket{j}_A}{d} \nonumber \\
& = \frac{\sum_{i=0}^{d-1}\sum_{j=0}^{d-1}\bra{i}_S H^2 \ket{j}_S \bra{i}_A\ket{j}_A}{d} \nonumber \\
& = \frac{\sum_{i=0}^{d-1} \bra{i}_S H^2\ket{i}_S}{d} \nonumber \\
& = \frac{\text{Tr}\left(H^2\right)}{d} \nonumber \\
& = \frac{1}{d}\text{Tr}\left(\sum_{l=0}^{M-1}c_l  H_l \sum_{m=0}^{M-1} c_m H_m \right) \nonumber \\
& = \frac{1}{d} \sum_{l=0}^{M-1}\sum_{m=0}^{M-1}c_l c_m\text{Tr}( H_l H_m) \nonumber \\
& =  \sum_{m=0}^{M-1}c_m^2 \nonumber \\
&= \norm{\textbf{c}}_2^2
\end{align}

\begin{align}
\alpha & := \sqrt{\bra{\Phi_d}_{SA}(H^2\otimes \Id_A) \ket{\Phi_d}_{SA} + 1} \nonumber \\
& = \sqrt{\norm{\textbf{c}}_2^2 + 1}
\end{align}

§.§ Proof of Proposition <ref>

Proposition <ref> contains equations showing how to explicitly compute three expectation values of interest using a classical shadow. This section outlines the derivation of each of these three expressions.

Recall that classical shadows generated by the random Clifford measurement version of the classical shadows procedure are of the form $\hat{\rho}_i = \left( 2^{2n+1} + 1\right) U^\dagger_i \ket{b_i}\bra{b_i} U_i - \Id$, and recall the definitions of the following operators:

\begin{align*}
O_l^{+} & = O_l + \left(O_l\right)^\dagger\\
O_l^{-} & = iO_l - i\left(O_l\right)^\dagger
\end{align*}

where $O_l = \left(H_l \otimes \Id\right) \ket{\Phi_d}_{SA} \bra{\Phi_d}_{SA} \otimes \ket{0}_C\bra{1}_C$ is a decoding operator as in Definition <ref>.

Also, note that $U_i^\dagger \ket{b_i}$ is on the Hilbert space $\mathcal{H}_S \otimes\mathcal{H}_A \otimes\mathcal{H}_C$, and $H_l$ acts on the Hilbert space $\mathcal{H}_S$.

\begin{align}
\begin{split}
{\rm Tr}\left(\hat{\rho_i} O_l^+\right)=& {\rm Tr}\Big(\left[ \left( 2^{2n+1} + 1 \right)U_i^\dagger \ket{b_i}\bra{b_i} U_i - \Id \right]   \Big[ \left(H_l \otimes \Id_A \right) \ket{\Phi_d}_{SA} \bra{\Phi_d}_{SA} \otimes \ket{0}_C\bra{1}_C  \\
&+ \ket{\Phi_d}_{SA} \bra{\Phi_d}_{SA}\left(H_l \otimes \Id_A \right)  \otimes \ket{1}_C\bra{0}_C \Big] \Big)\\
=&  \left( 2^{2n+1} + 1 \right){\rm Tr}\left( \left[U_i^\dagger \ket{b_i}\bra{b_i} U_i \right] \Big[\left(H_l \otimes \Id_A \right) \ket{\Phi_d}_{SA} \bra{\Phi_d}_{SA} \otimes \ket{0}_C\bra{1}_C \Big]    \right) \\
&- {\rm Tr}\Big(\left(H_l \otimes \Id_A \right) \ket{\Phi_d}_{SA} \bra{\Phi_d}_{SA} \otimes \ket{0}_C\bra{1}_C\Big)\\
&+  \left( 2^{2n+1} + 1 \right){\rm Tr}\left( \left[U_i^\dagger \ket{b_i}\bra{b_i} U_i\right] \Big[\ket{\Phi_d}_{SA} \bra{\Phi_d}_{SA}\left(H_l \otimes \Id_A \right)  \otimes \ket{1}_C\bra{0}_C \Big]   \right) \\
&- {\rm Tr}\Big(\ket{\Phi_d}_{SA} \bra{\Phi_d}_{SA}\left(H_l \otimes \Id_A \right)  \otimes \ket{1}_C\bra{0}_C\Big)\\
=&  \left( 2^{2n+1} + 1 \right){\rm Tr}\left( \left[U_i^\dagger \ket{b_i}\bra{b_i} U_i\right] \Big[ \left(H_l \otimes \Id_A \right) \ket{\Phi_d}_{SA} \bra{\Phi_d}_{SA} \otimes \ket{0}_C\bra{1}_C  \Big]  \right) \\
&- {\rm Tr}\Big(\left(H_l \otimes \Id_A \right) \ket{\Phi_d}_{SA} \bra{\Phi_d}_{SA} \Big) {\rm Tr}\left( \ket{0}_C\bra{1}_C\right)\\
&+  \left( 2^{2n+1} + 1 \right){\rm Tr}\left( \left[U_i^\dagger \ket{b_i}\bra{b_i} U_i\right] \Big[ \ket{\Phi_d}_{SA} \bra{\Phi_d}_{SA}\left(H_l \otimes \Id_A \right) \otimes \ket{1}_C\bra{0}_C \Big]   \right) \\
&- {\rm Tr}\Big(\ket{\Phi_d}_{SA} \bra{\Phi_d}_{SA}\left(H_l \otimes \Id_A \right)\Big){\rm Tr}\Big( \ket{1}_C\bra{0}_C\Big)\\
=&  \left( 2^{2n+1} + 1 \right){\rm Tr}\left( \left[U_i^\dagger \ket{b_i}\bra{b_i} U_i \right] \Big[ \left(H_l \otimes \Id_A \right) \ket{\Phi_d}_{SA} \bra{\Phi_d}_{SA} \otimes \ket{0}_C\bra{1}_C  \Big]  \right) \\
&+  \left( 2^{2n+1} + 1 \right){\rm Tr}\left( \left[U_i^\dagger \ket{b_i}\bra{b_i} U_i \right] \Big[ \ket{\Phi_d}_{SA} \bra{\Phi_d}_{SA}\left(H_l \otimes \Id_A \right) \otimes \ket{1}_C\bra{0}_C  \Big]  \right) \\
=&  \left( 2^{2n+1} + 1 \right) \bra{b_i} U_i \Big( \left(H_l \otimes \Id_A \right) \ket{\Phi_d}_{SA} \bra{\Phi_d}_{SA} \otimes \ket{0}_C\bra{1}_C    \Big)U_i^\dagger \ket{b_i} \\
&+  \left( 2^{2n+1} + 1 \right)\bra{b_i} U_i\Big(  \ket{\Phi_d}_{SA} \bra{\Phi_d}_{SA}\left(H_l \otimes \Id_A \right)  \otimes \ket{1}_C\bra{0}_C    \Big)U_i^\dagger \ket{b_i} \\
=&  \left( 2^{2n+1} + 1 \right) \Big(\bra{b_i} U_i  \left(H_l \otimes \Id_A \right) \ket{\Phi_d}_{SA}\otimes \ket{0}_C\Big) \Big( \bra{\Phi_d}_{SA} \otimes \bra{1}_C  U_i^\dagger \ket{b_i}\Big) \\
&+  \left( 2^{2n+1} + 1 \right)\Big( \bra{b_i} U_i  \ket{\Phi_d}_{SA}\otimes \ket{1}_C\Big) \Big( \bra{\Phi_d}_{SA}\left(H_l \otimes \Id_A \right)  \otimes \bra{0}_C  U_i^\dagger \ket{b_i}\Big)
\end{split}
\end{align}

\begin{align}
\begin{split}
{\rm Tr}\left(\hat{\rho_i} O_l^-\right)=& {\rm Tr}\Big(\left[ \left( 2^{2n+1} + 1 \right)U_i^\dagger \ket{b_i}\bra{b_i} U_i - \Id \right]   \Big[ i \left(H_l \otimes \Id_A \right) \ket{\Phi_d}_{SA} \bra{\Phi_d}_{SA} \otimes \ket{0}_C\bra{1}_C \\
& -i \ket{\Phi_d}_{SA} \bra{\Phi_d}_{SA}\left(H_l \otimes \Id_A \right)  \otimes \ket{1}_C\bra{0}_C \Big] \Big)\\
=&  i\left( 2^{2n+1} + 1 \right){\rm Tr}\left( \Big[ U_i^\dagger \ket{b_i}\bra{b_i} U_i\Big] \Big[ \left(H_l \otimes \Id_A \right) \ket{\Phi_d}_{SA} \bra{\Phi_d}_{SA} \otimes \ket{0}_C\bra{1}_C  \Big]   \right) \\
&- i{\rm Tr}\left(\left(H_l \otimes \Id_A \right) \ket{\Phi_d}_{SA} \bra{\Phi_d}_{SA} \otimes \ket{0}_C\bra{1}_C\right)\\
&-i  \left( 2^{2n+1} + 1 \right){\rm Tr}\left( \Big[ U_i^\dagger \ket{b_i}\bra{b_i} U_i \Big] \Big[ \ket{\Phi_d}_{SA} \bra{\Phi_d}_{SA}\left(H_l \otimes \Id_A \right)  \otimes \ket{1}_C\bra{0}_C  \Big]  \right) \\
&+i {\rm Tr}\left(\ket{\Phi_d}_{SA} \bra{\Phi_d}_{SA}\left(H_l \otimes \Id_A \right)  \otimes \ket{1}_C\bra{0}_C\right)\\
=&  i\left( 2^{2n+1} + 1 \right) \bra{b_i} U_i \Big( \left(H_l \otimes \Id_A \right) \ket{\Phi_d}_{SA} \bra{\Phi_d}_{SA} \otimes \ket{0}_C\bra{1}_C    \Big)U_i^\dagger \ket{b_i} \\
&-i  \left( 2^{2n+1} + 1 \right)\bra{b_i} U_i\Big(  \ket{\Phi_d}_{SA} \bra{\Phi_d}_{SA}\left(H_l \otimes \Id_A \right)  \otimes \ket{1}_C\bra{0}_C    \Big)U_i^\dagger \ket{b_i} \\
=&  i\left( 2^{2n+1} + 1 \right) \Big(\bra{b_i} U_i  \left(H_l \otimes \Id_A \right) \ket{\Phi_d}_{SA}\otimes \ket{0}_C\Big) \Big( \bra{\Phi_d}_{SA} \otimes \bra{1}_C    U_i^\dagger \ket{b_i}\Big) \\
&-i  \left( 2^{2n+1} + 1 \right)\Big( \bra{b_i} U_i  \ket{\Phi_d}_{SA}\otimes \ket{1}_C\Big) \Big( \bra{\Phi_d}_{SA}\left(H_l \otimes \Id_A \right)  \otimes \bra{0}_C    U_i^\dagger \ket{b_i}\Big)
\end{split}
\end{align}

Recall from Definition <ref> that $O_{\alpha} = \ket{\Phi_d}_{SA} \bra{\Phi_d}_{SA} \otimes \ket{1}_C\bra{1}_C$ is the decoding operator corresponding to the normalization constant $\alpha$. From this it follows that

\begin{align}
\begin{split}
{\rm Tr}( \hat{\rho}_i O_\alpha) =&   {\rm Tr}\Big( \left[\left( 2^{2n+1} + 1\right) U^\dagger_i \ket{b_i}\bra{b_i} U_i - \Id\right] \Big[ \ket{\Phi_d}_{SA} \bra{\Phi_d}_{SA} \otimes \ket{1}_C\bra{1}_C \Big]   \Big)\\
=& \left( 2^{2n+1} + 1\right) {\rm Tr}\Big( \left[ U^\dagger_i \ket{b_i}\bra{b_i} U_i\right] \Big[ \ket{\Phi_d}_{SA} \bra{\Phi_d}_{SA} \otimes \ket{1}_C\bra{1}_C \Big]   \Big)\\
&- {\rm Tr}\Big(\ket{\Phi_d}_{SA} \bra{\Phi_d}_{SA} \otimes \ket{1}_C\bra{1}_C \Big)\\
=& \left( 2^{2n+1} + 1\right)  \bra{b_i} U_i \Big(\ket{\Phi_d}_{SA} \bra{\Phi_d}_{SA} \otimes \ket{1}_C\bra{1}_C \Big) U^\dagger_i \ket{b_i}  - 1\\
=& \left( 2^{2n + 1} + 1 \right) \abs{\bra{b_i}U_i \ket{\phi_d}_{SA}\ket{1}_C}^2 - 1
\end{split}
\end{align}

§.§ Proof of Lemma <ref>

Recall the definitions of the Hermitian operators in Lemma <ref>:

\begin{align}
O_{\alpha} &= \ket{\Phi_d}_{SA} \bra{\Phi_d}_{SA} \otimes \ket{1}\bra{1},
\end{align}

\begin{align}
O_l^{+} &= O_l + \left(O_l\right)^\dagger\\
O_l^{-} &= iO_l - i\left(O_l\right)^\dagger
\end{align}

\begin{align}
O_l = \left(H_l \otimes \Id\right) \ket{\Phi_d}_{SA} \bra{\Phi_d}_{SA} \otimes \ket{0}\bra{1}
\end{align}

is defined for all $0 \leq l \leq M-1$.

First consider the square of the Hilbert-Schmidt norm of $O_l^{+}$:

\begin{align}
\text{Tr}\left(\left(O_l^{+}\right)\left(O_l^{+}\right)^\dagger\right) & =\text{Tr}\left(\left(O_l^{+}\right)^2\right) \nonumber \\
& = \text{Tr}\left(O_l^2\right) + \text{Tr}\left(O_l O_l^\dagger \right) + \text{Tr}\left(O_l^\dagger O_l \right) + \text{Tr}\left(\left(O_l^\dagger \right)^2\right) \nonumber \\
& = \text{Tr}\left(O_l^2\right) + 2\text{Tr}\left(O_l O_l^\dagger \right) + \text{Tr}\left(\left(O_l^\dagger \right)^2\right)
\end{align}

Examining each term above individually, we see that:

\begin{align}
\text{Tr}\left(O_l^2\right) & = \text{Tr}\left(\left( \left(H_l \otimes \Id\right) \ket{\Phi_d}_{SA} \bra{\Phi_d}_{SA} \otimes \ket{0}\bra{1}\right)^2 \right) \nonumber \\
& = \text{Tr}\Big(\left( \left(H_l \otimes \Id\right) \ket{\Phi_d}_{SA} \bra{\Phi_d}_{SA} \otimes \ket{0}\bra{1}\right)\left( \left(H_l \otimes \Id\right) \ket{\Phi_d}_{SA} \bra{\Phi_d}_{SA} \otimes \ket{0}\bra{1}\right) \Big) \nonumber \\
& = \text{Tr}\Big(\bra{\Phi_d}_{SA}\left( H_l \otimes \Id\right) \ket{\Phi_d}_{SA} \bra{\Phi_d}_{SA}  \left(H_l \otimes \Id\right) \ket{\Phi_d}_{SA}   \Big)\text{Tr}\Big(  \ket{0}\bra{1}\ket{0}\bra{1}\Big) \nonumber \\
& = 0
\end{align}

\begin{align}
\text{Tr}\left(\left(O_l^\dagger \right)^2\right) &=0
\end{align}

\begin{align}
\text{Tr}\left(O_l O_l^\dagger \right) & = \text{Tr}\left(\Big( \left(H_l \otimes \Id\right) \ket{\Phi_d}_{SA} \bra{\Phi_d}_{SA} \otimes \ket{0}\bra{1}\Big) \Big( \left(H_l \otimes \Id\right) \ket{\Phi_d}_{SA} \bra{\Phi_d}_{SA} \otimes \ket{0}\bra{1}\Big)^\dagger \right) \nonumber \\
& = \text{Tr}\left(\Big( \left(H_l \otimes \Id\right) \ket{\Phi_d}_{SA} \bra{\Phi_d}_{SA} \otimes \ket{0}\bra{1}\Big) \Big(  \ket{\Phi_d}_{SA} \bra{\Phi_d}_{SA} \left(H_l^\dagger \otimes \Id\right) \otimes \ket{1}\bra{0}\Big) \right) \nonumber \\
& = \text{Tr}\left( \left(H_l \otimes \Id\right) \ket{\Phi_d}_{SA}  \bra{\Phi_d}_{SA} \left(H_l^\dagger \otimes \Id\right)  \right)\text{Tr}\left( \ket{0}\bra{1}\ket{1}\bra{0} \right) \nonumber \\
&= \bra{\Phi_d}_{SA} \left(H_l^\dagger \otimes \Id\right)\left(H_l \otimes \Id\right) \ket{\Phi_d}_{SA} \nonumber  \\
&= \bra{\Phi_d}_{SA} \ket{\Phi_d}_{SA} \nonumber  \\
&= 1
\end{align}

where we have used the fact that $H_l$ is part of an orthonormal basis, so $H_l^\dagger H_l = \Id$.

From this we arrive at the following upper bound:

\begin{align}
\text{Tr}\left(\left(O_l^{+}\right)^2\right) &= 2
\end{align}

\begin{align}
\text{Tr}\left(\left(O_l^{-}\right)^2\right) &= 2
\end{align}

Finally, it is obvious from the definition of $O_\alpha$ that

\begin{align}
\text{Tr}\left(O_{\alpha}^2\right) &= 1
\end{align}

Section 5B in <cit.> proves that $\norm{O_{i}}^2_{shadow} \leq 3\text{Tr}\left(\left(O_{i}\right)^2\right)$ for a Hermitian operator $O_i$.

Since Lemma <ref> defines $\textbf{O} \equiv \{O_i \mid i \in \mathbb{Z}_{2M}\}$ as the set {$O_{\alpha}$} $\cup$  $\{O_l^{+}$, $O_l^{-} \mid l \in \mathbb{Z}_{M}\}$, we see that

\begin{align}
\text{Tr}\left(\left(O_{i}\right)^2\right) & \leq 2,
\end{align}

\begin{align}
\norm{O_{i}}^2_{shadow} \leq 6,
\end{align}

completing the proof of Lemma <ref>.

§.§ Choosing a Sufficiently Small Classical Shadows Error

To keep the total error of the Hamiltonian learning problem to at most $\epsilon$, the error of the classical shadows procedure, $\epsilon_s$, cannot be too large. However, decreasing $\epsilon_s$ requires increasing the number of measurements $N$. Therefore, we seek the largest value of $\epsilon_s$ such that the total error is at most $\epsilon$. This value is given by Proposition <ref>, which is proven below.

Using classical shadows in Algorithm <ref>, we compute $\hat{o}_i$ and $\hat{o}_\alpha$, which, with a probability of at least $\delta_s$, are estimates of $\frac{1}{\alpha^2}$ and $\frac{c_i}{\alpha^2}$ to within an error of $\epsilon_s$ . This means that upon success, the uncertainty in $\alpha^2$, which we get by taking the reciprocal of our estimate of $\frac{1}{\alpha^2}$, is at most

\begin{align}
\epsilon_{\alpha} = \alpha^4 \epsilon_s
\end{align}

The next step in Algorithm <ref> is to divide $\hat{o}_i$ by $\hat{o}_\alpha$ to get $\hat{c}_i$, our estimate of $c_i$. The uncertainty in $c_i$ is therefore at most

\begin{align}
\epsilon_i &= c_i \sqrt{\left(\frac{\epsilon_{\alpha}}{\alpha^2}\right)^2 + \left(\frac{\epsilon_s}{\frac{c_i}{\alpha^2}}\right)^2} \nonumber \\
&= \epsilon_s \alpha^2 \sqrt{c_i^2 +1}
\end{align}

The total $l_2$ error in the vector of Hamiltonian coefficients is then

\begin{align}
\norm{\hat{\textbf{c}} - \textbf{c}}_2 & \leq \sqrt{M} \max_i \epsilon_i \nonumber \\
& = \sqrt{M} \epsilon_s \alpha^2  \sqrt{\max_i c_i^2 +1}
\end{align}

For this total error to be at most $\epsilon$, as required by the Hamiltonian learning problem, it serves to choose

\begin{align}
\epsilon_s & = \frac{\epsilon}{\alpha^2 \sqrt{c^2_{\rm max} +1} \sqrt{M}} \label{eq:esUB}
\end{align}

§.§ Proof of Lemma <ref>

Here we provide a formal proof of Lemma <ref> which provides our key result surrounding the cost of preparing the pseudo-Choi state that represents the Hamiltonian.

Begin by preparing the state $\ket{\psi_0} = \ket{0}_C \ket{0}_B \ket{\Phi_d}_{SA}$, and use it as the input state to the circuit in Figure <ref>.
Applying the Hadamard gate to register $C$ gives

\begin{align}
\ket{\psi_1} &= \frac{1}{\sqrt{2}}\Big(  \ket{0}_C \ket{0}_B \ket{\Phi_d}_{SA} + \ket{1}_C \ket{0}_B \ket{\Phi_d}_{SA} \Big)
\end{align}

After the controlled application of $U_{block}$, which acts on registers $B$ and $S$, we have the state

\begin{align}
\ket{\psi_2} &= \frac{1}{\sqrt{2}}\Big(  \ket{0}_C (U_{block}\otimes \Id_A) \ket{0}_B \ket{\Phi_d}_{SA} + \ket{1}_C \ket{0}_B \ket{\Phi_d}_{SA} \Big)
\end{align}

Recall that the block-encoding of the Hamiltonian is of the form

\begin{align}
U_{block} & = \ket{0}_B \bra{0}_B \otimes \frac{2\widetilde{H}t}{\pi} + \ket{0}_B \bra{1}_B \otimes I_S + \ket{1}_B \bra{0}_B \otimes J_S + \ket{1}_B \bra{1}_B \otimes K_S
\end{align}

where $I_S$, $J_S$, and $K_S$ are “junk” operators we do not care about. Thus we can write the previous state as

\begin{align}
\ket{\psi_2} &= \frac{1}{\sqrt{2}}\Bigg(  \ket{0}_C   \ket{0}_B  \left(\frac{\widetilde{H}}{\Delta} \otimes \Id_A\right) \ket{\Phi_d}_{SA}  + \ket{0}_C   \ket{1}_B  ( J_S \otimes \Id_A) \ket{\Phi_d}_{SA}  + \ket{1}_C \ket{0}_B \ket{\Phi_d}_{SA} \Bigg)
\end{align}

The probability of obtaining the outcome $\ket{0}_B$ upon measuring the block-encoding qubit is given by:

\begin{align}
\mathbf{Pr}(0) &= \bra{\psi_2} (\Id_C \otimes \ket{0}_B\bra{0}_B \otimes \Id_{SA})\ket{\psi_2} \nonumber \\
& = \bra{\psi_2}  \left(\frac{  \ket{0}_C   \ket{0}_B  \left(\frac{\widetilde{H}}{\Delta} \otimes \Id_A\right) \ket{\Phi_d}_{SA}   + \ket{1}_C \ket{0}_B \ket{\Phi_d}_{SA}}{\sqrt{2}} \right) \nonumber  \\
& =   \frac{1}{2}\left( \bra{\Phi_d}_{SA} \left(\frac{\widetilde{H}^\dagger \widetilde{H}}{\Delta^2} \otimes \Id_A\right)  \ket{\Phi_d}_{SA}   + 1 \right) \nonumber \\
& = \frac{\norm{\widetilde{\textbf{c}}}_2^2}{2 \Delta^2} + \frac{1}{2},
\end{align}

where in the last line we inserted the representation of the Hamiltonian $\widetilde{H}$ from Definition <ref> (the missing steps are nearly identical to the proof of Equation (<ref>) in Appendix <ref>).

If the outcome of the measurement of register B is $\ket{0}_B$, the resulting state is

\begin{align}
\ket{\psi_3} &= \frac{\left(\Id_C \otimes \ket{0}_B \bra{0}_B \otimes \Id_{SA}\right)\ket{\psi_2}}{\sqrt{\mathbf{Pr}(0)}} \nonumber  \\
& = \frac{\ket{0}_C \ket{0}_B (\frac{\widetilde{H}}{\Delta} \otimes \Id_A) \ket{\Phi_d}_{SA} + \ket{1}_C \ket{0}_B \ket{\Phi_d}_{SA}}{ \sqrt{2}\sqrt{\frac{\norm{\widetilde{\textbf{c}}}_2^2}{2\Delta^2} + \frac{1}{2}}}
\end{align}

where $\Delta = \frac{\pi}{2t}$.

Ignoring the extra qubit in register $B$, this is a pseudo-Choi state of $\frac{\widetilde{H}}{\Delta}$:

\begin{align}
\ket{\psi_c'} &= \left(\frac{\ket{0}_C(\frac{\widetilde{H}}{\Delta} \otimes \Id_A) \ket{\Phi_d}_{SA} + \ket{1}_C\ket{\Phi_d}_{SA}}{\gamma}\right) ,
\end{align}

\begin{align}
\gamma &= \sqrt{\frac{\norm{\widetilde{\textbf{c}}}_2^2}{\Delta^2} + 1}.
\end{align}

To check that the success probability of producing the pseudo-Choi state (ie. measuring the block-encoding qubit and getting the outcome $\ket{0}_B$) is a valid probability, we would like to be sure that the term $\bra{\Phi_d}_{SA} \left(\frac{\widetilde{H}^\dagger \widetilde{H}}{\Delta^2} \otimes \Id_A\right)  \ket{\Phi_d}_{SA}$ is in $[1/2,1] $. We start by relating $\norm{\widetilde{\textbf{c}}}_2^2$ to the spectral norm of the Hamiltonian:

\begin{align}
\norm{\widetilde{\textbf{c}}}_2^2 & = \bra{\Phi_d}_{SA} (\widetilde{H}^\dagger \widetilde{H} \otimes \Id_A)  \ket{\Phi_d}_{SA} \nonumber \\
&= \frac{1}{d}\sum_{i=1}^d \sum_{j=1}^d \bra{i}_S \bra{i}_A (\widetilde{H}^\dagger \widetilde{H} \otimes \Id_A) \ket{j}_S \ket{j}_A \nonumber  \\
& = \frac{1}{d}\sum_{i=1}^d \sum_{j=1}^d \bra{i}_S \widetilde{H}^\dagger \widetilde{H} \ket{j}_S \bra{i}_A \ket{j}_A \nonumber  \\
& = \frac{1}{d}\sum_{i=1}^d  \bra{i}_S \widetilde{H}^\dagger \widetilde{H} \ket{i}_S  \nonumber  \\
& = \frac{1}{d}{\rm Tr} \left(\widetilde{H}^\dagger \widetilde{H} \right) \nonumber   \\
& = \frac{1}{d}\norm{ \widetilde{H} }^2_F  \nonumber  \\
& \geq \frac{\norm{\widetilde{H}}^2_2}{d}.
\end{align}

Using this, we see that

\begin{align}
\mathbf{Pr}(0) & \geq \frac{1}{2}\left( \frac{\norm{\widetilde{H}}^2_2}{d\Delta^2}   + 1 \right) \nonumber \\
& =  \frac{2\norm{\widetilde{H}t}^2_2}{d\pi^2}   + \frac{1}{2} \ge \frac{1}{2}.
\end{align}

where in the second line we used $\Delta = \frac{\pi}{2t}$.  Similarly, using the fact that $\norm{\tilde{H}}_F \le \sqrt{r} \norm{\tilde{H}}_2$ we have that

\begin{align}
\mathbf{Pr}(0) & \leq \frac{1}{2}\left( \frac{r\norm{\widetilde{H}}^2_2}{d\Delta^2}   + 1 \right) \nonumber \\
& =  \frac{2r\norm{\widetilde{H}t}^2_2}{d\pi^2}   + \frac{1}{2}.
\end{align}

From Lemma <ref> we inherit the following upper bound on the evolution time:

\begin{align}
t & \leq \frac{1}{2\norm{H}},
\end{align}

which means that if the block-encoded Hamiltonian had no error (ie. $\widetilde{H} = H$) the success probability would certainly be less than 1. However, we must take into account the error from the block-encoding procedure. Thankfully, the result of Lemma <ref> guarantees that

\begin{align}
\norm{Ht - \widetilde{H}t} &\leq \epsilon_b,
\end{align}

for $\epsilon_b \in (0, \frac{1}{2})$.
Therefore, the success probability remains valid as it can never be more than 1 or less than $\frac{1}{2}$.

§.§ Proof of Equation (<ref>)

Since we have an upper bound on $N_s$, the number of pseudo-Choi states required to solve the Block-Encoded Hamiltonian Learning Problem <ref>, we would now like to know how many queries to $U_{block}$ will suffice to generate $N_s$ pseudo-Choi states with high probability. An upper bound on this value is given by equation (<ref>), which we now prove.

Consider the following Chernoff bound, from <cit.>:

Let $X_1, ..., X_n \in [0,1]$ be independent random variables with $\mathbb{E}[X_i] = p_i$, let $X = \sum_{i=1}^n X_i$, and let $\mu = \mathbb{E}[X] = \sum_{i=1}^N X_i p_i$. For $\beta \in (0,1)$ we have

\begin{align}
\mathbf{Pr}(X \leq (1 - \beta)\mu) & \leq e^{- \frac{\beta^2 \mu}{2}}
\end{align}

Now, let $X$ be the number of pseudo-Choi states produced after $\widetilde{N}$ queries to $U_{block}$. We want $X$ to be greater than or equal to $N_s$, so we seek an upper bound on $\mathbf{Pr}(X \leq N_s)$. Since the success probability of obtaining each pseudo-Choi state from one query to the block-encoding is $\frac{\gamma^2}{2}$ (see Appendix <ref>), we have $\mu = \frac{\widetilde{N} \gamma^2}{2}$.

To use the Chernoff bound <ref>, we therefore choose

\begin{align}
\beta & = 1 - \frac{2 N_s}{\gamma^2\widetilde{N}}
\end{align}

Note that since $\beta$ must be greater than zero to apply the Chernoff bound, we require $\widetilde{N} \geq \frac{2 N_s}{\gamma^2}$.

By the Chernoff bound we then have:

\begin{align}
\mathbf{Pr}(X \leq N_s) & \leq e^{-\frac{\widetilde{N} \gamma^2}{4}\left(1 - \frac{4 N_s}{\gamma^2\widetilde{N}} + \frac{4 N_s^2}{\gamma^4\widetilde{N}^2}\right)}
\end{align}

We want this probability to be at most $\delta_{N_s}$, so we let

\begin{align}
\delta_{N_s} & \equiv e^{-\frac{\widetilde{N} \gamma^2}{4}\left(1 - \frac{4 N_s}{\gamma^2\widetilde{N}} + \frac{4 N_s^2}{\gamma^4\widetilde{N}^2}\right)},
\end{align}

from which we see that

\begin{align}
\ln\left({\frac{1}{\delta_{N_s}}}\right) & = \frac{\widetilde{N} \gamma^2}{4} - N_s + \frac{N_s^2}{\gamma^2 \widetilde{N}} \nonumber \\
& \geq \frac{\widetilde{N} \gamma^2}{4} - N_s
\end{align}

Finally, solving for $\widetilde{N}$ gives

\begin{align}
\widetilde{N} & \leq 4\frac{ \ln\left({\frac{1}{\delta_{N_s}}}\right)}{\gamma^2} + 4 \frac{N_s}{\gamma^2}
\end{align}

In general, we assume $N_s$ will be much larger than $\ln\left({\frac{1}{\delta_{N_s}}}\right)$. Therefore, to generate at least $N_s$ pseudo-Choi states with probability at least $1 - \delta_{N_s}$, the number of queries to $U_{block}$ needed is

\begin{align}
\widetilde{N} & \in \mathcal{O} \left(\frac{N_s}{\gamma^2} \right)
\end{align}