Hamiltonian Locality Testing via Trotterized Postselection

Our main result is a improved upper bound for the Hamiltonian locality testing problem. As with past works, our algorithm is also time-efficient and non-adaptive, though it does requires $n$ qubits of quantum memory, like [12, 3].

We pair it with the first lower bound in the tolerant testing setting. While our upper bound uses only forward time evolution and does not require controlled application of $e^{-itH}$, our lower bound also applies to algorithms using either of these tools.

Finally, we show that, when reverse time evolution and controlled operations are allowed, it is possible to saturate this lower bound even in the tolerant case (proof in the appendix).

For simplicity, we will consider the intolerant case (${\epsilon }_1=0$, ${\epsilon }_2=\epsilon$) for this proof overview; the same techniques apply in the tolerant case but require somewhat more care. First we start with the intuition behind the algorithm of [12, 3].

We will need the fact that the space of $2n$ qubit states ${ℂ}^{2^{2n}}$ has the Bell basis ${(|{\sigma }_P⟩)}_P$, where $P$ spans the $n$-fold Paulis, $|{\sigma }_{I^{\otimes n}}⟩$ is the maximally entangled state $\frac{1}{\sqrt{2^n}}{\sum }_{x\in {\{0,1\}}^n}|x⟩\otimes |x⟩$, and $|{\sigma }_P⟩=(I^{\otimes n}\otimes P)|{\sigma }_{I^{\otimes n}}⟩$. Therefore, for any unitary $U$, if we apply $I^{\otimes n}\otimes U$ to $|{\sigma }_{I^{\otimes n}}⟩$ and then measure in the Bell basis, we are able to sample from the (squared) Pauli spectrum⁴⁴4That is, ${\alpha }_P^2$ when $U$ is written as ${\sum }_P{\alpha }_{p}P$. of $U$ (the squares of the Pauli decomposition coefficients always sum to $1$ for a unitary [17]).

For any Hamiltonian $H$, the closest $k$-local Hamiltonian is given by dropping all of the non-local Paulis from its Pauli decomposition. Therefore, as by the first-order Taylor series expansion,

for small enough $t$, we can set $U=e^{-iH\cdot t}$ in the aforementioned procedure, and if $H$ is $\epsilon$-far from local we will sample a non-local Pauli term with $\approx {(t\cdot \epsilon )}^2$ probability. Conversely, if $H$ is local we should sample no non-local terms, giving us a distinguishing algorithm if the process is repeated $O\left({(t\cdot \epsilon )}^{-2}\right)$ times, for a total time evolution of $O\left(t^{-1}\cdot {\epsilon }^{-2}\right)$.

So ideally we would like $t$ to be $\Theta \left(1/\epsilon \right)$ and only repeat a constant number of times, leading to a total time evolution of $O\left({\epsilon }^{-1}\right)$, which would be optimal by Theorem 2.

Unfortunately, these higher-order terms in the Taylor series cannot be ignored at larger values of $t$. As we have ${\parallel H\parallel }_{\mathrm{\infty }}\le 1$, we can bound the $k^{\text{th}}$ order term of the Taylor series expansion of $H$ by $O\left(t^k\right)$, and so we must set $t$ to be at most $\Theta \left(\epsilon \right)$, resulting in the total time evolution of $O\left({\epsilon }^3\right)$ obtained in previous work [12, 3].

To evade this barrier, we will instead show that it is possible to (approximately) simulate evolving by $H_{>k}$, which is composed of only the non-local terms of the Pauli decomposition of $H$. Note that if $H$ is $k$-local, this is $0$, while if it is not, $H_{>}k$ is the difference between $H$ and the closest $k$-local Hamiltonian. Suppose we could evolve by the time evolution operator of this Hamiltonian. Then performing the Bell sampling procedure from before would return $|{\sigma }_{I^{\otimes n}}⟩$ with probability

as $H$ contains no identity term.

To tame this infinite series, imagine that ${\parallel H_{>k}\parallel }_{\mathrm{\infty }}\le 1$ (we will eventually evolve by a related operator $A$ that does satisfy ${\parallel A\parallel }_{\mathrm{\infty }}\le 1$). Then we have

for all integers $\mathrm{\ell }\ge 2$, so as long as $t$ is a sufficiently small constant, we have that ${\left|⟨{\sigma }_{I^{\otimes n}}|\left(I^{\otimes n}\otimes e^{-i{H}_{>k}t}\right)|{\sigma }_{I^{\otimes n}}⟩\right|}^2$ is at least

where $\mathrm{Tr}\left({(H_{>k})}^2\right)/2^n={\epsilon }^2$ is exactly the squared normalized Frobenius distance of $H$ from being $k$-local. So if we apply $e^{-i{H}_{>k}t}$ with $t=\Theta \left(1\right)$, we are left with a $\approx {\epsilon }^2$ probability of sampling a non-local Pauli term if $H$ is non-local, and are guaranteed to measure identity if $H$ is local (as then $e^{-i{H}_{>k}\cdot t}$ is the identity). This means we can distinguish locality from non-locality with $O\left({\epsilon }^{-2}\right)$ repetitions, requiring $O\left({\epsilon }^{-2}\right)$ total evolution time.⁵⁵5Unfortunately, even with access to the time evolution operator of $H_{>k}$ we cannot set $t$ to the optimal $\Theta \left(1/\epsilon \right)$, as we lose control of the higher-order terms of the Taylor expansion.

Now, we cannot actually apply $e^{-i{H}_{>k}t}$. However, when starting at $|{\sigma }_{I^{\otimes n}}⟩$, we can approximate it up to $t=\Theta \left(1\right)$ by the use of a process reminiscent of the Elitzur-Vaidman bomb-tester [9] and Quantum Zeno effect [10], which we refer to as Trotterized post-selection.

Let $D$ be the subspace of Bell states corresponding to non-local Paulis or identity and let ${\mathrm{\Pi }}_D$ be the projector onto that subspace. Starting with $|{\sigma }_{I^{\otimes n}}⟩$ once again, we apply $I^{\otimes n}\otimes e^{-iH{t}^{\prime }}$ for $t^{\prime }=O\left(\epsilon \right)$, measure with $\{{\mathrm{\Pi }}_D,I^{\otimes 2n}-{\mathrm{\Pi }}_D\}$, and then post-select on the measurement result ${\mathrm{\Pi }}_D$. We then repeat our application of $I^{\otimes n}\otimes e^{-iH{t}^{\prime }}$ and post-selection, for $O\left(1/t^{\prime }\right)$ iterations, provided our post-selection succeeds each time.

As we start with $|{\sigma }_{I^{\otimes n}}⟩$, then make small adjustments (i.e., $e^{-iHt}\approx I^{\otimes 2n}$ for small $t$), the chance of failing the post-selection is small: only $O\left({\epsilon }^2\right)$ at each iteration, and so as long as we only use $O\left(1/\epsilon \right)$ iterations, we will succeed with probability $1-O\left(\epsilon \right)$. Now, as we are taking small steps, we can approximate each iteration of ${\mathrm{\Pi }}_D\left(I^{\otimes n}\otimes e^{-iH\cdot O\left(\epsilon \right)}\right){\mathrm{\Pi }}_D$ as

where we define $A≔{\mathrm{\Pi }}_D(I^{\otimes n}\otimes H){\mathrm{\Pi }}_D$ and choose some ${\parallel R\parallel }_{\mathrm{\infty }}\le O\left({\epsilon }^2\right)$.⁶⁶6Note that the ${\mathrm{\Pi }}_D$ on the right does nothing besides make $A$ obviously Hermitian, assuming our invariant of our post-selection succeeding.

Now, in general, $A\ne I^{\otimes n}\otimes H_{>k}$, but as long as $H$ has no identity term in its Pauli decomposition⁷⁷7We can assume this without loss of generality, as our algorithm never uses controlled application of $e^{-iH\cdot t}$, and so any identity term would manifest as an undetectable global phase., by construction $A|{\sigma }_{I^{\otimes n}}⟩=\left(I^{\otimes n}\otimes H_{>k}\right)|{\sigma }_{I^{\otimes n}}⟩$, and so $⟨{\sigma }_{I^{\otimes n}}|A^2|{\sigma }_{I^{\otimes n}}⟩=⟨{\sigma }_{I^{\otimes n}}|I\otimes {\left(H_{>k}\right)}^2|{\sigma }_{I^{\otimes n}}⟩$. Combined with the fact that ${\parallel A\parallel }_{\mathrm{\infty }}={\parallel {\mathrm{\Pi }}_D\left(I^{\otimes n}\otimes H\right){\mathrm{\Pi }}_D\parallel }_{\mathrm{\infty }}\le {\parallel H\parallel }_{\mathrm{\infty }}\le 1$, we can argue that, if we iterate $t/t^{\prime }$ times

where the final inequality follows from the fact that for all $k>2$,

So as our method based on access to the time evolution operator of $H_{>k}$ only required distinguishing between $⟨{\sigma }_{I^{\otimes n}}|H_{>k}|{\sigma }_{I^{\otimes n}}⟩$ being $\Theta \left({\epsilon }^2\right)$ and $0$ we can emulate it with access to $e^{-iAt}$ without losing too much accuracy, as long as we take $t$ to be a small enough constant. We can therefore test locality with a total time evolution of $O\left({\epsilon }^{-2}\right)$.

To prove the lower bound, it suffices to show that for any $k$ there exists Hamiltonians $H_1$ and $H_2$ such that a query to the time $t$ evolution of $H_1$ and $H_2$ differ in diamond distance by at most $O\left(({\epsilon }_2-{\epsilon }_1)t\right)$, with $H_1$ ${\epsilon }_1$-close to being $k$-local and $H_2$ ${\epsilon }_2$-far from being $k$-local.

We achieve this by considering the weight-$k$ Pauli $Z_{1:k}$ that is $Z$ on the first $k$ qubits, and identity on the last $n-k$ qubits. We then set $H_1≔{\epsilon }_1{Z}_{1:k}$ and $H_2≔{\epsilon }_2{Z}_{1:k}$. Because $Z_{1:k}$ is diagonal, so is $e^{-i\epsilon Z_{1:k}\cdot t}$, making it straightforward to bound the diamond distance of the two time evolution operators by $O\left(t({\epsilon }_2-{\epsilon }_1)\right)$. By the sub-additivity of diamond distance, the total time evolution required to distinguish the two Hamiltonians with constant probability is therefore at least $\Omega \left({({\epsilon }_2-{\epsilon }_1)}^{-1}\right)$.

A Hamiltonian on $n$-qubits is a $2^n\times 2^n$ Hermitian matrix. The time evolution operator of a Hamiltonian $H$ for time $t\ge 0$ is the unitary matrix

We define the $n$-qubit Pauli matrices to be ${𝒫}^{\otimes n}≔{\{I,X,Y,Z\}}^{\otimes n}$, where , , . For any Pauli $P$, we denote the locality $|P|$ to be the number of non-identity terms in the tensor product. Let the Frobenius inner product between matrices $A$ and $B$ be $⟨A,B⟩≔\mathrm{Tr}(A^{†}B)$. The orthogonality of Pauli matrices under the Frobenius inner product is implied by the fact that any product of Paulis is another Pauli (up to sign) and the fact that among them only the identity has non-zero trace. Given a matrix $A={\sum }_{P\in {𝒫}^{\otimes n}}{\alpha }_{P}P$, the locality of $A$ is the largest $|P|$ such that ${\alpha }_P\ne 0$. If $A$ is a Hamiltonian (i.e., Hermitian) then all ${\alpha }_P$ are real-valued. The normalized Frobenius norm is given by

and will be used as our distance to $k$-locality, in keeping with the previous literature [6, 12, 3]. The other important norm will be the (unnormalized) spectral norm ${\parallel A\parallel }_{\mathrm{\infty }}$, which is the largest singular value of $A$. For any matrix $A$, ${\parallel A\parallel }_2\le {\parallel A\parallel }_{\mathrm{\infty }}$, recalling that ${\parallel \cdot \parallel }_2$ is the normalized Frobenius norm. As a form of normalization and to be consistent with the literature, we will assume that ${\parallel H\parallel }_{\mathrm{\infty }}\le 1$ for any Hamiltonian referenced. We will also WLOG assume that $\mathrm{Tr}(H)=0$ for any Hamiltonian, since it does not affect the time evolution unitary beyond a global phase, and so as our algorithms do not use controlled application of the unitary, they cannot be affected by it.

We define $A_{>k}≔{\sum }_{|P|>k}{\alpha }_{P}P$ and subsequently $A_{\le k}≔{\sum }_{|P|\le k}{\alpha }_{P}P$. By the orthogonality of the Pauli matrices under the Frobenius inner product, $A_{\le k}$ is the $k$-local Hamiltonian that is closest to $A$ with distance ${\parallel A-A_{\le k}\parallel }_2={\parallel A_{>k}\parallel }_2$.

Let $B=\{|{\mathrm{\Phi }}^{+}⟩,|{\mathrm{\Phi }}^{-}⟩,|{\mathrm{\Psi }}^{+}⟩,|{\mathrm{\Psi }}^{-}⟩\}$ denote the set containing the four Bell states. We will view $B^{\otimes n}$ as a basis of ${ℂ}^{2^n}\otimes {ℂ}^{2^n}$, in which for each copy of $B$, one qubit is assigned to the left register and one to the right. Note that, up to phase, every state in $B^{\otimes n}$ is equal to $(I^{\otimes n}\otimes P){|{\mathrm{\Phi }}^{+}⟩}^{\otimes n}$ for a unique $P\in {𝒫}^{\otimes n}$. We will write $|{\sigma }_P⟩$ for this basis element. As an example,

If $U={\sum }_{P\in {𝒫}^{\otimes n}}{\alpha }_{P}P$ is a unitary matrix, then by Parseval’s identity, ${\sum }_{P\in {𝒫}^{\otimes n}}{|{\alpha }_P|}^2=1$, i.e. ${|{\alpha }_P|}^2$ gives a probability distribution over the Paulis. Applying $I^{\otimes n}\otimes U$ to the state $|{\sigma }_{I^{\otimes n}}⟩={|{\mathrm{\Phi }}^{+}⟩}^{\otimes n}$ and measuring in the Bell basis $B^{\otimes n}$ allows one to sample from this distribution [17].

For a quantum channel that takes as input an $n$-qubit state, we will let the diamond norm refer to ${\parallel \mathrm{\Lambda }\parallel }_{\diamond }≔{\max }_{\rho }\parallel (I^{\otimes n}\otimes \mathrm{\Lambda })(\rho ){\parallel }_1$ where the maximization is over all $2n$-qubit states $\rho$. The diamond distance famously characterizes the maximum statistical distinguishability (i.e., induced trace distance) between quantum channels [21, Section 9.1.6], even with ancillas.

We will not need a particularly tight form of this bound, so for ease of analysis we state the following (loose) corollary.

We start by giving an algorithm that returns a Bernoulli random variable $X\in \{0,1\}$, where $𝔼\left[X\right]$ approximates the distance of $H$ from being $k$-local. It does so by iteratively applying $e^{-i\alpha H}$ sandwiched by $\{{\mathrm{\Pi }}_D,I^{\otimes 2n}-{\mathrm{\Pi }}_D\}$ measurements.

Let $\alpha ≔\frac{{\epsilon }_2^2-{\epsilon }_1^2}{100{\epsilon }_2}$ be the step-size used in line 3, $t≔\frac{\sqrt{{\epsilon }_2^2-{\epsilon }_1^2}}{2{\epsilon }_2}$ be the total time evolution used in Algorithm 1, and let $m≔t/\alpha =\frac{50}{\sqrt{{\epsilon }_2^2-{\epsilon }_1^2}}$ be the number of iterations used in line 2. In our analysis will frequently use the fact that $\alpha \le \frac{{\epsilon }_2}{100}\le \frac{1}{100}$ and $t\le 0.5$ to simplify higher-order terms.

First we show that the final state of the Trotterized postselection algorithm corresponds to evolving $|{\sigma }_{I^{\otimes n}}⟩$ by $e^{-iAt}$, with a bounded error term. There are two main sources of error: (1) the error from higher-order terms in the respective Taylor series of $e^{-iA\alpha }$ and ${\mathrm{\Pi }}_D\left(I^{\otimes n}\otimes e^{-iH\alpha }\right){\mathrm{\Pi }}_D$ not matching and (2) the error from post-selection causing normalization issues. The following technical lemma allows us to tackle the error from (1). This is done by showing that $e^{-itA}={\mathrm{\Pi }}_D\left(I^{\otimes n}\otimes e^{-itH}\right){\mathrm{\Pi }}_D\pm O\left({\alpha }^2\right)$ for sufficiently small $\alpha$. By chaining these together, the triangle inequality will eventually show in Lemma 14 that the accumulated error is then at most $O\left({\alpha }^{2}m\right)=O\left(\alpha t\right)$.