\hideLIPIcs

QuSoft & University of Amsterdam (UvA), [email protected] QuSoft & CWI, [email protected] Paderborn University, [email protected] Kyoto University, [email protected] Nagoya University, [email protected] Kyoto University, [email protected] QuSoft & CWI, [email protected] \CopyrightChris Cade, Marten Folkertsma, Sevag Gharibian, Ryu Hayakawa, Francois Le Gall, Tomoyuki Morimae and Jordi Weggemans {CCSXML} <ccs2012> <concept> <concept_id>10003752.10003753.10003758.10003784</concept_id> <concept_desc>Theory of computation Quantum complexity theory</concept_desc> <concept_significance>500</concept_significance> </concept> </ccs2012> \ccsdesc[500]Theory of computation Quantum complexity theory This paper is based on our following two technical reports \relatedversiondetailsPrevious Versionhttps://arxiv.org/abs/2207.10097 \relatedversiondetailsPrevious Versionhttps://arxiv.org/abs/2207.10250

Acknowledgements.

We thank Jonas Helsen for feedback on an earlier draft, and Ronald de Wolf for helpful comments. CC acknowledges support from QuSoft and CWI, as well as the University of Amsterdam (UvA) under a POC (proof of concept) fund. MF and JW were supported by the Dutch Ministry of Economic Affairs and Climate Policy (EZK), as part of the Quantum Delta NL programme. RH, FLG, and TM were supported by MEXT Quantum Leap Flagship Program (MEXT Q-LEAP) grant No. JPMXS0120319794. RH was also supported by JSPS KAKENHI Grant Number JP22J11727. FLG was also supported by JSPS KAKENHI grants Nos. JP19H04066, JP20H05966, JP20H00579, JP20H04139, JP21H04879. SG was supported by DFG grants 450041824 and 432788384. TM was supported by JST Moonshot JPMJMS2061-5-1-1, JST FOREST, the Grant-in-Aid for Scientific Research (B) No.JP19H04066, the Grant-in Aid for Transformative Research Areas (A) 21H05183, and the Grant-in-Aid for Scientific Research (A) No.22H00522.\EventEditorsKousha Etessami, Uriel Feige, and Gabriele Puppis \EventNoEds3 \EventLongTitle50th International Colloquium on Automata, Languages, and Programming (ICALP 2023) \EventShortTitleICALP 2023 \EventAcronymICALP \EventYear2023 \EventDateJuly 10–14, 2023 \EventLocationPaderborn, Germany \EventLogo \SeriesVolume261 \ArticleNo93

Improved Hardness Results for the Guided Local Hamiltonian Problem

Chris Cade Marten Folkertsma Sevag Gharibian Ryu Hayakawa François Le Gall Tomoyuki Morimae Jordi Weggemans

Abstract

Estimating the ground state energy of a local Hamiltonian is a central problem in quantum chemistry. In order to further investigate its complexity and the potential of quantum algorithms for quantum chemistry, Gharibian and Le Gall (STOC 2022) recently introduced the guided local Hamiltonian problem (GLH), which is a variant of the local Hamiltonian problem where an approximation of a ground state (which is called a guiding state) is given as an additional input. Gharibian and Le Gall showed quantum advantage (more precisely, BQP-completeness) for GLH with $6$ -local Hamiltonians when the guiding state has fidelity (inverse-polynomially) close to $1/2$ with a ground state.

In this paper, we optimally improve both the locality and the fidelity parameter: we show that the BQP-completeness persists even with 2-local Hamiltonians, and even when the guiding state has fidelity (inverse-polynomially) close to 1 with a ground state. Moreover, we show that the BQP-completeness also holds for 2-local physically motivated Hamiltonians on a 2D square lattice or a 2D triangular lattice. Beyond the hardness of estimating the ground state energy, we also show BQP-hardness persists when considering estimating energies of excited states of these Hamiltonians instead. Those make further steps towards establishing practical quantum advantage in quantum chemistry.

keywords:

Quantum computing, Quantum advantage, Quantum Chemistry, Guided Local Hamiltonian Problem

category:

Track A: Algorithms, Complexity and Games \relatedversion

1 Introduction

Simulation of physical systems is one of the originally envisioned applications of quantum computing [12, 13]. Quantum chemistry, in particular, has seen much activity on this front in recent years, e.g. [1, 4, 5, 24, 29, 31]. There, a central goal is to estimate the ground state energy of a given $k$ -local Hamiltonian $H$ , denoted the $k$ -local Hamiltonian problem ( $k$ -LH). Roughly, for this problem, a $k$ -local Hamiltonian $H=\sum_{i}H_{i}$ on $n$ qubits is a $2^{n}\times 2^{n}$ Hermitian matrix, specified succinctly via “local quantum clauses” $H_{i}$ acting on $k\in O(1)$ qubits each. The eigenvalues of $H$ are the discrete energy levels of the corresponding quantum system. In particular, the smallest eigenvalue, which we denote $\lambda_{0}(H)$ , is called the ground state energy. An eigenvector corresponding to $\lambda_{0}(H)$ is called a ground state, and describes a state of the quantum system in the energy configuration $\lambda_{0}(H)$ . Note that $k$ -LH strictly generalizes classical $k$ -SAT, in that any instance of the latter can be embedded into the former.

Unfortunately, it is nowadays well-known that estimating ground state energies of local Hamiltonians is QMA-complete [23]. This hardness persists, moreover, even in the bosonic [32] and fermionic settings [30]. Thus, assuming $\textup{BQP}\neq\textup{QMA}$ , one cannot hope for an efficient algorithm for $k$ -LH on all $k$ -local Hamiltonians.

What actually happens in practice.

In an attempt to bypass worst-case hardness results, in practice the quantum chemistry community often adopts the following two-step procedure:

•

(Step 1: Ground state approximation) A classical heuristic algorithm is applied to obtain a “guiding state” $\ket{\psi}$ , which is hoped to have “good” fidelity with a ground state.
•

(Step 2: Ground state energy approximation) The guiding state $\ket{\psi}$ is used in Quantum Phase Estimation (QPE) [22] to efficiently compute the corresponding ground state energy [2, 4]. (A more recent approach is based on variational quantum algorithms, aimed more at near-term hardware (see [9] for a survey), but which is heuristic in nature (unlike QPE).)

Two comments: (1) There is something special about Step 2 — it is a unique strength of quantum computers to be able to resolve an eigenvalue (within additive $1/\mathrm{poly}(n)$ precision) of a (sparse) Hermitian matrix given just an approximation $\ket{\psi}$ to the corresponding eigenvector (via QPE)!¹¹1 Actually, quantum computers can efficiently prepare a ground state with fidelity $1-1/\exp(n)$ given access to a guiding state $\ket{u}$ that has inverse polynomial fidelity with a ground state $\ket{g}$ (i.e. $|\langle u|g\rangle|\geq 1/\mathrm{poly}(n)$ ) using quantum amplitude amplification for local Hamiltonians that have inverse-polynomial spectral gaps [26]. Indeed, the closely related task of (sparse) matrix inversion, which can be solved efficiently on a quantum computer coherently by diagonalizing the matrix and “manually” inverting its eigenvalues via postselection, is BQP-complete [19]. (2) In general, one does not expect a good²²2“Good” here meaning a state $\ket{\psi}$ with inverse polynomial fidelity with a ground state, and with a succinct classical description allowing $\ket{\psi}$ to be prepared efficiently. guiding state for arbitrary local Hamiltonian $H$ to exist, as this would imply $\textup{QCMA}=\textup{QMA}$ . And even if such a guiding state did exist, finding it can still be hard. For example, minimizing $\mathrm{tr}(H\rho)$ over the “simplest” quantum ansatz of tensor product states, i.e. $\rho=\rho_{1}\otimes\rho_{2}\otimes\cdots\otimes\rho_{n}$ for $\rho_{i}\in\mathcal{L}({\mathbb{C}}^{2})$ , remains NP-hard (seen by letting $H$ be a diagonal Hamiltonian encoding a classical $3$ -SAT instance).

Directions for study.

With Steps 1 and 2 above in mind, in order to practically obtain a quantum advantage for quantum chemistry problems, there are two branches of study necessary:

•

(Step 1: Ground state approximation) Here, the best one can hope for is fast algorithms tailored to physically motivated special cases of Hamiltonians $H$ (either heuristic or worst-case poly-time complexity). This is arguably the bottleneck for fast quantum algorithms outperforming classical techniques [25].
•

(Step 2: Ground state energy approximation) A thorough complexity theoretic understanding of which Hamiltonian families provably permit quantum computers to outperform classical ones, assuming a good guiding state has been found (in Step 1).

In [15], the formal study of the second step above was initiated. Specifically, the Guided $k$ -local Hamiltonian problem ( $k$ -GLH) was introduced, which is stated roughly as follows (formally given in Definition 3.1): Given a $k$ -local Hamiltonian $H$ , an appropriate “representation” of a guiding state $\ket{\psi}$ with $\delta$ -fidelity with the ground space of $H$ , and real thresholds $\beta>\alpha$ , estimate the ground state energy of $H$ . Then, two results were shown:

•

For any constant $k$ , $k$ -GLH can be efficiently solved classically within constant precision, i.e. for $\beta-\alpha\in\Theta(1)$ and $\delta\in\Theta(1)$ .
•

In contrast, $6$ -GLH is BQP-hard for inverse polynomial precision, i.e. $\beta-\alpha\geq 1/\mathrm{poly}(n)$ , and $\delta=1/\sqrt{2}-1/\mathrm{poly}(n)$ .

The latter regime of inverse-polynomial precision turns out to be the relevant one for solving quantum chemistry problems in practice — the desired “chemical accuracy” is about 1.6 millihartree (which is constant relative to an unnormalized Hamiltonian), which upon renormalization of the Hamiltonian (as done here) yields the claimed inverse polynomial precision. This BQP-hardness result thus gives theoretical evidence for the superiority of quantum algorithms for chemistry.

Four important problems were left open in [15]: Is $k$ -GLH still BQP-hard with larger $\delta$ , and in particular for $\delta$ arbitrarily close to 1? Is $k$ -GLH still BQP-hard for $k<6$ ? Is $k$ -GLH still BQP-hard for estimating the excited state energies? Is $k$ -GLH still BQP-hard for physically motivated Hamiltonians?

This work.

In this work, we continue the agenda toward Step 2 above by resolving these four open questions. Here are our main contributions:

•

First, we show that BQP-hardness continues to hold even for $\delta=1-1/\mathrm{poly}(n)$ , i.e. even when we are promised the guiding state $\ket{\psi}$ is a remarkably good approximation to the ground state.
•

Second, we show that BQP-hardness continues to hold even for $k=2$ . (Note that for $k=1$ , the problem can be solved efficiently classically, even without a guiding state.)
•

Third, we extend the BQP-hardness results to the case when one is interested in estimating energies of excited states, rather than just the groundstate. Interestingly, we are only able to show BQP-completeness in this setting by showing that the first point holds, i.e. the BQP-hardness in the regime $\delta\in[\frac{1}{2}+\Omega(1/poly(n)),1-{\Omega}(1/poly(n))]$ .
•

Fourth, we prove hardness results for physically motivated Hamiltonians. They include XY model (constraints of the form $XX+YY$ ), Heisenberg model (constraints of the form $XX+YY+ZZ$ ), the antiferromagnetic $XY$ model and the antiferromagnetic Heisenberg model (i.e. “Quantum Max Cut” [16]). In contrast, the BQP-hardness construction of [15] is arguably artificial, because they used the circuit-to-Hamiltonian construction of [23] and query Hamiltonian construction of [3].

To formalize the third direction, we introduce the Guided $k$ -Local Hamiltonian Low Energy-problem ( $k$ -GLHLE) in which the guiding state has $\delta$ -fidelity with the $c$ ’th excited state of $H$ and the problem is to estimate the $c$ ’th excited state energy of $H$ (for a formal definition, see Definition 3.1). Then, the four contributions above are summarized in the following theorem.

Theorem 1.1 (Main result).

For any $\delta\in(0,1-\Omega(1/\mathrm{poly}(n)))$ , constant $k\geq 2$ and some integer $0\leq c\leq\mathcal{O}(poly(n))$ , there exist $a,b\in[-1,1]$ with $b-a\in\Omega(1/\mathrm{poly}(n))$ such that k-GLHLE is BQP-hard. Moreover, it is still BQP-hard if the 2-local Hamiltonian is restricted to any of the following families of Hamiltonians:

•

non-2SLD Hamiltonian on a 2D square lattice
•

antiferromagnetic Heisenberg model
•

antiferromagnetic $XY$ model on a 2D triangular lattice.

Here, the “non-2SLD” Hamiltonians are, roughly, $2$ -local Hamiltonians that cannot be diagonalized via single-qubit unitaries (see Definition 2.5 for the formal definition). (The term 2SLD is short for “the 2-local parts of all interactions in the set are simultaneously locally diagonalizable”.) It was originally introduced in the Hamiltonian complexity classification of Cubitt and Montanaro [10]. The $XY$ model and the Heisenberg model are examples of non-2SLD Hamiltonians.

Techniques.

Now let us explain our technical contributions. Our first result is the improvement of the fidelity $\delta$ (Proposition 3.2 in Section 3). The construction of [15] cannot exceed $\delta=1/2$ , but we achieve the fidelity $\delta=1-1/\mathrm{poly}(n)$ . Let us explain why the construction of [15] cannot exceed the fidelity $\delta=1/2$ . Their construction for the BQP-hardness result is the following local Hamiltonian

H=\frac{\alpha+\beta}{2}I\otimes\ket{0}\bra{0}+H^{\prime}\otimes\ket{1}\bra{1},

where $\beta-\alpha>1/\mathrm{poly}(n)$ and $H^{\prime}$ is a certain local Hamiltonian whose lowest eigenvalue is $\leq\alpha$ in the YES case and is $\geq\beta$ in the NO case. It is clear that a ground state of $H$ is $\ket{\psi}\otimes\ket{1}$ in the YES case, where $\ket{\psi}$ is a ground state of $H^{\prime}$ . For the NO case, a ground state is $|0...0\rangle\otimes\ket{0}$ . It can then be easily observed that the optimal guiding state (i.e. the guiding state that has the maximum fidelity with ground states in both the YES and the NO cases) is written as $|\phi\rangle\otimes|+\rangle$ for a certain choice of $|\phi\rangle$ , which shows that the fidelity cannot exceed $1/2$ in this construction.

To overcome the problem, we use the perturbation theory approaches of [21, 7]. In particular, we use first-order perturbation theory, either using the general Schrieffer-Wolf transform framework of [7] or a more first-principles approach via the Projection Lemma. The main idea is to use a large energy penalty term to rule out all low-energy states which do not look like “history states”. We then show that the corresponding guiding state can be chosen as the semi-classical subset state introduced in [15] (see Definition 2.1 in Section 2). To obtain this, we notice that the ground state of our Hamiltonian is gapped and unique. This is because we are doing a reduction from BQP (as opposed to QMA). In other words, there is no QMA “proof” to be plugged into the history state construction, and therefore there is a unique low-energy history state. In sum, via perturbation theory, we are able to directly approximate the ground state with a guiding state in both YES and NO cases, as opposed to the block encoding approach of [15], which used equally weighted orthogonal subspaces to separately encode the YES and NO cases, respectively.

Our second result is BQP-hardness of $k$ -GLH for $k=2$ (Propositions 3.6 in Section 3). Here, the universal simulation setup of [11, 33] cannot be directly applied, because although their results can approximately preserve the ground space of the input Hamiltonian, it was not known whether semi-classical subset states can be mapped to semi-classical subset states under such simulation frameworks, and the latter is essential for guiding states used in GLH. We show that this is indeed the case. In particular, we show that the original semi-classical subset state of the input 5-GLH instance is mapped to a state with polynomially many ancilla qubits in the low-energy subspace of the simulating 2-local Hamiltonian.

Our third result is the BQP-hardness for physically motivated 2-local Hamiltonians (Proposition 3.7 and Proposition 3.11). The main obstacle here is that ground states of physically motivated 2-local Hamiltonians are not known to be guided by semi-classical subset states. To solve the problem, we introduce another class of semi-classical states which we call semi-classical encoded states (see Definition 2.2 in Section 2). Intuitively, semi-classical encoded states are states constructed from semi-classical subset states by applying a local isometry on each qubit. Although semi-classical encoded states are more general than semi-classical subset states, they still allow succinct descriptions and efficient classical sampling algorithms (Lemma 2.3). For us, it is essential that semi-classical encoded states are closed under the applications of the local encoding of states during the perturbative simulations. We show that semi-classical encoded states indeed satisfy this property, and therefore can guide ground states of physically motivated 2-local Hamiltonians. The semi-classical encoded states newly introduced in this paper are of independent interest, and seem to have many other interesting applications.

Finally, our fourth result is to extend the $k$ -GLH problem to the question of excited state energy estimation, we call this the Guided k-Local Hamiltonian Low Energy ( $k$ -GLHLE) problem. In Ref. [20], the authors show that determining the $c$ th excited state energy of a $k$ -local Hamiltonian ( $k\geq 3$ ), where $c=\mathrm{poly}(n)$ , is QMA-complete – even if all the $c-1$ energy eigenstates and corresponding energies are known. In their construction, they embed a $k$ -local Hamiltonian $H$ , encoding the QMA computation, in a Hamiltonian $H^{\prime}$ living on a larger Hilbert space. This allows them to add up to polynomial number of artificial eigenstates to $H^{\prime}$ below the groundstate of $H$ . Finding the $c$ ’th eigenvalue of $H^{\prime}$ is then just as hard as finding the groundstate of $H$ . We show that this construction translates to the setting with guiding states. As a bonus, we also show that the unguided problem is QMA-hard for $k=2$ , which was left open in [20].

Open questions.

There are many open questions surrounding GLH, as well as the more general important goal of solving quantum chemistry problems on quantum computers. For example, we have shown BQP-hardness of GLH for physically motivated Hamiltonians such as those with Heisenberg interactions. An important next step would be to show BQP-hardness for the specific types of fermionic Hamiltonians which are currently being studied in the quantum chemistry literature. Another subtle but important point is that, technically, the level of precision required for GLH in quantum chemistry scales as $1/n$ , while the hardness promise gap scales as $o(1/n)$ in [15] and the present paper. Can this be improved to $\Theta(1/n)$ ? A positive resolution to the quantum PCP conjecture would presumably, in turn, allows one to obtain hardness for gap $\Theta(1)$ . Absent this, we are unaware of any circuit-to-Hamiltonian construction which is able to achieve $O(1/n)$ promise gap. Moreover, as mentioned earlier, the main bottleneck for quantum chemistry on quantum computers is the arduous task of finding a good guiding state (if it even exists!). Can good heuristics be designed for this? Efforts to date suggest the answer so far is negative [25]. Finally, more interestingly (but more challengingly), can one show rigorous poly-time guiding-state computation algorithms for the specific families of Hamiltonians considered in the quantum chemistry literature?

2 Preliminaries

Notation

We denote by $[M]$ the set $\{1,\dots,M\}$ . We write $\lambda_{i}(A)$ to denote the $i$ th eigenvalue of a Hermitian matrix $A$ , ordered in non-decreasing order, with $\lambda_{0}(A)$ denoting the smallest eigenvalue (ground energy). We denote $\text{eig}(A)=\{\lambda_{0}(A),\dots,\lambda_{\text{dim}(A)-1}(A)\}$ for the (ordered) set of all eigenvalues of $A$ .

2.1 Semi-classical states

In this section, we formally introduce the guided local Hamiltonian problem. We first define two classes of semi-classical states. The term “semi-classical” is motivated by the requirement for such states that they should be efficiently described (as an input of the problem) and efficiently samplable.³³3 The requirement of sampling access for a guiding state is motivated by the existence of an efficient classical algorithm for the GLH problem with constant precision, given a guiding state with sampling access, as shown in [15]. One type of a semi-classical state we use in this paper is a polynomial-size variant of the notion of subset states, first introduced in [18].

Definition 2.1 (Semi-classical subset state).

We say that a normalized state $\ket{u}\in\mathbb{C}^{2^{n}}$ is a semi-classical subset state if there is a subset $S\subseteq\{0,1\}^{n}$ with $|S|=\mathrm{poly}(n)$ such that

\ket{u}=\frac{1}{\sqrt{|S|}}\sum_{x\in S}\ket{x}.

A semi-classical subset state can be efficiently described by the description of $S$ . It is clear that we can efficiently sample from the probability distribution that outputs $x\in\{0,1\}^{n}$ with probability $|\langle x|u\rangle|^{2}$ , i.e. according to the uniform distribution over $S$ .

We next introduce a generalized version of a semi-classical subset state.

Definition 2.2 (Semi-classical encoded state).

We say that a normalized state $\ket{u}\in\mathbb{C}^{2^{m}}$ , for $n<m\in\mathcal{O}(n)$ , is a semi-classical encoded state if there is a subset $S\subseteq\{0,1\}^{n}$ with $|S|=\mathrm{poly}(n)$ and a set of isometries $V_{1},V_{2},...,V_{n}$ , where each of $V_{i}$ maps a $1$ -qubit state to an $\mathcal{O}(1)$ -qubit state, such that

\ket{u}=\frac{1}{\sqrt{|S|}}\sum_{x\in S}V_{1}(\ket{x_{1}})\otimes V_{2}(\ket{x_{2}})\otimes\cdots\otimes V_{n}(\ket{x_{n}}).

A semi-classical encoded state is indeed a semi-classical subset state if the encoding is trivial (i.e. $V_{1}=V_{2}=\cdots=V_{n}=I$ ). A semi-classical encoded state can be described by the description of $S$ and isometries $V_{1},V_{2}...,V_{n}$ . We can also efficiently sample from the semi-classical encoded state as we show in the following lemma.

Lemma 2.3.

Given the description of an $m$ -qubit semi-classical encoded state $\ket{u}$ , we can classically efficiently sample from the probability distribution that outputs $x\in\{0,1\}^{m}$ with probability $|\langle x|u\rangle|^{2}$ .

Proof 2.4.

Assume we are given the description, $S\subseteq\{0,1\}^{n}$ and $V_{1},V_{2},...,V_{n}$ , of the semi-classical encoded state

\ket{u}=\frac{1}{\sqrt{|S|}}\sum_{x\in S}V_{1}(\ket{x_{1}})\otimes V_{2}(\ket{x_{2}})\otimes\cdots\otimes V_{n}(\ket{x_{n}}).

Let $P(y_{0},y_{1},...,y_{i-1})=|(\bra{y_{0},y_{1},...,y_{i-1}}\otimes I)\ket{u}|^{2}$ be the probability that the measurement outcome of the first $i$ qubits of $\ket{u}$ in the computational basis is $y_{0},y_{1},...,y_{i-1}$ . For each $i\in[m]$ , we can efficiently calculate $P(y_{0},y_{1},...,y_{i-1})$ because $|S|=\mathrm{poly}(n)$ and $V_{1}(\ket{x_{1}})\otimes V_{2}(\ket{x_{2}})\otimes\cdots\otimes V_{n}(\ket{x_{n}})$ is a product state of $\mathcal{O}(1)$ -qubit states. Then, we can also efficiently calculate the conditional probability

P(z|y_{0},y_{1},...,y_{i-1})=\frac{P(y_{0},y_{1},...,y_{i-1},z)}{P(y_{0},y_{1},...,y_{i-1})}.

If the bits $y_{0},y_{1},...,y_{i-1}$ have already been sampled, we compute $P(z|y_{0},y_{1},...,y_{i-1})$ and sample the next bit by tossing the coin with bias $P(0|y_{0},y_{1},...,y_{i-1})$ . In this way, we can classically efficiently sample from the probability distribution that outputs $x$ with probability $|\langle x|u\rangle|^{2}$ .

2.2 Non-2SLD Hamiltonian and geometry of interaction

To state the result, we introduce some families of Hamiltonians. Given a set of (at most) two-body interactions $\mathcal{S}=\{h_{\alpha}\}$ , $\mathcal{S}$ -Hamiltonian refers to the family of Hamiltonians that can be written in the form

H=\sum_{\langle i,j\rangle\in E}J_{i,j}h_{\alpha_{i,j}}^{(i,j)},

(1)

where $J_{i,j}\in\mathbb{R}$ , $h_{\alpha_{i,j}}^{(i,j)}$ is two-local interaction chosen from $\mathcal{S}$ and $E$ is the set of edges that represents the connectivity of interaction [10]. If the connectivity of two-body interaction is restricted to a 2D square lattice, we call such a family $\mathcal{S}$ -Hamiltonian on a 2D square lattice. We also introduce the notion of 2SLD and non-2SLD:

Definition 2.5 (2SLD interaction [10]).

Suppose $\mathcal{S}$ is a set of interactions at most 2 qubits. We say that $\mathcal{S}$ is 2SLD if there exists $U\in{\rm SU}(2)$ , such that for all $h_{i}\in\mathcal{S}$ ,

U^{\otimes 2}h_{i}(U^{\dagger})^{\otimes 2}=\alpha_{i}Z\otimes Z+A_{i}\otimes I+I\otimes B_{i},

where $\alpha_{i}\in\mathbb{R}$ and $A_{i},B_{i}$ are arbitrary single-qubit Hamiltonians.

A set $\mathcal{S}$ is non-2SLD if it is not 2SLD. In particular, such non-2SLD $\mathcal{S}$ includes the following physically motivated⁴⁴4For clarity, in [10] and here, all hardness results require non-uniform weights on constraints. It is an open question whether one can obtain (say) QMA-hardness results with uniform (i.e. unit weight) constraints for such models. This remains an interesting open question, as many-body physicists typically utilize unit weights to model physical systems. Hamiltonians:

•

$\{Z,X,ZZ,XX\}$ ( $ZZXX$ interaction [6])
•

$\{Z,X,ZX,XZ\}$ ( $ZX$ interaction [6])
•

$\{XX+YY\}$ (general $XY$ interaction)
•

$\{XX+YY+ZZ\}$ (general Heisenberg interaction).

If there is only a single type of interaction (like $\mathcal{S}=\{XX+YY+ZZ\}$ ), the Hamiltonian is called semi-translationally-invariant. (Interaction strength can differ in each term.)

Restriction on the sign of the interaction.

We also introduce a further restricted class of $\mathcal{S}$ -Hamiltonian in which all the signs of the coefficients are promised to be non-negative (i.e. all of $J_{i,j}$ in eq. (1) must satisfy $J_{i,j}\geq 0$ ). We call such a family of Hamiltonians as $\mathcal{S}^{+}$ -Hamiltonian following [28]. In [28], the following results are shown:

•

$\{\alpha XX+\beta YY+\gamma ZZ\}^{+}$ -Hamiltonian is QMA-complete if $\alpha+\beta>0$ , $\alpha+\gamma>0$ and $\beta+\gamma>0$ hold.
•

$\{\alpha XX+\beta YY+\gamma ZZ\}^{+}$ -Hamiltonian is QMA-complete if the interactions are restricted to the edges of a 2D triangular lattice if $\alpha XX+\beta YY+\gamma ZZ$ is not proportional to $XX+YY+ZZ$ in addition to the condition that $\alpha+\beta>0$ , $\alpha+\gamma>0$ and $\beta+\gamma>0$ hold.

The first type of $\mathcal{S}^{+}$ -Hamiltonian includes the antiferromagnetic Heisenberg model ( $\{XX+YY+ZZ\}^{+}$ -Hamiltonian) and the antiferromagnetic $XY$ model ( $\{XX+YY\}^{+}$ -Hamiltonian) as important special cases. The antiferromagnetic $XY$ model (unlike the antiferromagnetic Heisenberg model) remains QMA-complete if its geometric interaction is restricted to a 2D triangular lattice as it is included in the second type of $\mathcal{S}^{+}$ -Hamiltonian above.

3 GLHLE hardness constructions

We next define the guided local Hamiltonian low energy (GLHLE) problem, which can be viewed as a generalization of GLH by considering arbitrary eigenstates of Hamiltonians⁵⁵5This definition of GLH is very similar to the definition of $\textup{GLH}^{*}(k,a,b,\delta)$ in [15]. The difference is that while the guiding states used in [15] are restricted to semi-classical subset states (Definition 2.1), in our definition we use the more general concept of semi-classical encoded states (Definition 2.2). Note that our BQP-hardness result for general 2-local Hamiltonians (Proposition 3.6) actually holds even when the guiding state is a semi-classical subset state. Proposition 3.6, which optimally improves both the locality and fidelity parameters of [15], therefore holds in exactly the same setting as [15]. We use semi-classical encoded states only to show BQP-hardness for further restricted families of Hamiltonians (Propositions 3.7 and 3.11).. For an $n$ -qubit Hamiltonian $H$ , we denote $\Pi_{c}$ the projector onto the space spanned by the states of $H$ that have energy $\lambda_{c}(H)$ .

Definition 3.1 (Guided Local Hamiltonian Low Energy).

$\text{GLHLE}(k,c,a,b,\delta)$

Input:: A $k$ -local Hamiltonian $H$ on $n$ qubits such that $\|H\|\leq 1$ and the description of a semi-classical encoded state $\ket{u}\in\mathbb{C}^{2^{n}}$ , a constant $c\in\mathbb{N}_{\geq}{0}$ .
Promise:: $\|\Pi_{c}\ket{u}\|^{2}\geq\delta$ , where $\Pi_{c}$ denotes the projection on the subspace spanned by the $c$ th eigenstates, ordered in order of non-decreasing energy, of $H$ , and either $\lambda_{c}(H)\leq a$ or $\lambda_{c}(H)\geq b$ holds.
Goal:: Decide whether $\lambda_{c}(H)\leq a$ or $\lambda_{c}(H)\geq b$ .

The proof of Theorem 1.1 consists of five parts: first, we show that 5-local GLH with $\delta=1-\Omega(1/\mathrm{poly}(n))$ fidelity is BQP-hard. Then, we show how to extend this result to the BQP-hardness of the 6-local GLHLE problem. Next, we improve the locality parameter and show a reduction from 6-local GLHLE to 2-local GLHLE. Simultaneously we show that this also holds when we restict the Hamiltonians to be non $-2SLD$ $\mathcal{S}$ -Hamiltonian on a $2D$ square lattice. Finally, we show that BQP-hardness persists if we restrict the family of Hamiltonians to be $\{XX+YY+ZZ\}^{+}$ -Hamiltonians, or $\{XX+YY\}^{+}$ -Hamiltonians on a $2D$ triangular lattice.

We state these five parts as propositions and prove them one by one, from this our main result (Theorem 1.1) follows.

3.1 Increasing the allowed fidelity

The first proposition focuses on increasing the allowed fidelity of the guiding state with the ground state of the Hamiltonian of interest (and hence $c=0$ ).

Proposition 3.2.

For any $\delta\in(0,1-\Omega(1/\mathrm{poly}(n)))$ , there exist $a,b\in[0,1]$ with $b-a\in\Omega(1/\mathrm{poly}(n))$ such that the problem $\text{GLHLE}(5,0,a,b,\delta)$ is BQP-hard. Moreover, it is still BQP-hard with the additional two promises that

1.

$H$ has a non-degenerate ground state separated from the first excited state by a spectral gap $\gamma\in\Omega(1/\mathrm{poly}(n))$ in both the cases $\lambda_{0}(H)\leq a$ and $\lambda_{0}(H)\geq b$ .(We call such instances $\gamma$ -gapped $\textup{GLH}(k,a,b,\delta)$ .)
2.

The guiding state is restricted to be a semi-classical subset state.

Proof 3.3.

Let $\Pi=(\Pi_{\rm yes},\Pi_{\rm no})$ be a promise problem in BQP, and $x\in\{0,1\}^{n}$ be an input. Let $U_{x}=U_{m}U_{m-1}...U_{1}$ be a quantum circuit that decides $x$ consisting of $m=\mathrm{poly}(n)$ gates. $U_{x}$ acts on $\ket{x}_{A}\otimes\ket{0...0}_{B}$ where $A$ denotes the $n$ -qubit input register and $B$ denotes the poly-size ancilla register. By measuring the output register of $U_{x}\ket{x}_{A}\otimes\ket{0...0}_{B}$ , the quantum verifier outputs $1$ with probability at least $\alpha$ if $x\in\Pi_{\rm YES}$ (at most $\beta$ if $x\in\Pi_{\rm NO}$ , respectively). We may assume $\alpha=1-2^{-n}$ and $\beta=2^{-n}$ via the standard error reduction for BQP.

Consider a pre-idled quantum verifier $\tilde{U}_{x}\coloneqq U_{x}I\cdots I$ , where $I$ is the identity gate. The $\tilde{U}_{x}$ consists of $M\coloneqq m+N$ gates, where $N$ is the number of idling steps. ( $N=\mathrm{poly}(n)$ is taken properly later.) Consider Kitaev’s [23] 5-local circuit-to-Hamiltonian construction with an additional scaling factor:

\displaystyle H\coloneqq\Delta(H_{\textup{in}}+H_{\textup{prop}}+H_{\textup{stab}})+H_{\textup{out}}.

(2)

Here,

	$\displaystyle H_{\textup{in}}\coloneqq(I-\ket{x}\bra{x})_{A}\otimes(I-\ket{0...0}\bra{0...0})_{B}\otimes(\ket{0}\bra{0})_{C}$		(3)
	$\displaystyle H_{\textup{out}}\coloneqq\ket{0}\bra{0}_{\textup{out}}\otimes\ket{M}\bra{M}_{C}$		(4)
	$\displaystyle H_{\textup{stab}}\coloneqq\sum_{j=1}^{M-1}\ket{0}\bra{0}_{C_{j}}\otimes\ket{0}\bra{0}_{C_{j+1}}$		(5)
	$\displaystyle H_{\textup{prop}}\coloneqq\sum_{t=1}^{M}{H_{t}},\rm{where}$		(6)
	$\displaystyle\;H_{t}\coloneqq-\frac{1}{2}U_{t}\otimes\ket{t}\bra{t-1}_{C}-\frac{1}{2}U_{t}^{\dagger}\otimes\ket{t-1}\bra{t}_{C}+\frac{1}{2}I\otimes(\ket{t}\bra{t}_{C}+\ket{t-1}\bra{t-1}_{C}).$		(7)

It is known that the non-degenerate and zero-energy ground space of $H_{0}\coloneqq H_{\textup{in}}+H_{\textup{prop}}+H_{\textup{stab}}$ is spanned by $\ket{\psi_{\textup{hist}}}$ , where

\ket{\psi_{\textup{hist}}}\coloneqq\frac{1}{\sqrt{M+1}}\sum_{t=0}^{M}\tilde{U_{t}}\tilde{U}_{t-1}\cdots\tilde{U}_{1}\ket{x}_{A}\otimes\ket{0...0}_{B}\otimes\ket{t}_{C}.

It is also known that the smallest non-zero eigenvalue of $H_{0}$ is larger than $\pi^{2}/(64M^{2})$ [17, Lemma 2.2] (based on [14, Lemma 3]).

We apply the Schrieffer-Wolf transformation for this $H$ by taking sufficiently large $\Delta$ . Note that $H_{\textup{out}}=\ket{0}\bra{0}\otimes I\otimes\ket{M}\bra{M}$ and $\|H_{\textup{out}}\|=1$ . We would take

\Delta\geq 16\cdot 64M^{2}/\pi^{2}.

Then, $H$ has a one-dimensional ground space spanned by a ground state $\ket{g}$ . In the following, we analyze the fidelity between $\ket{g}$ and $\ket{\psi_{\textup{hist}}}$ , and the eigenvalue of $\ket{g}$ in the YES and NO cases.

Analysis of fidelity.

Using Equation (12) of Appendix B , the bound

\|\ket{g}-\ket{\psi_{\textup{hist}}}\|\in\mathcal{O}\left((\Delta/M^{2})^{-1}\right)

holds. Let us introduce the following state:

\ket{u}\coloneqq\frac{1}{\sqrt{N}}\sum_{t=1}^{N}\ket{x}_{A}\otimes\ket{0...0}_{B}\otimes\ket{t}_{C}.

This is a semi-classical subset state. This state satisfies

|\langle u|\psi_{\textup{hist}}\rangle|^{2}=\frac{N}{m+N+1}.

Therefore, for any positive polynomial $r$ , we can take sufficiently large $N,\Delta\in\mathcal{O}(\mathrm{poly}(n))$ so that $|\langle u|g\rangle|^{2}\geq 1-1/r(n)$ .

Analysis of eigenvalue.

Next, we see the ground state energy of $H$ in both the YES case and the NO case. The first-order effective Hamiltonian is given by

H_{\rm{eff},1}=\ket{\psi_{\textup{hist}}}\bra{\psi_{\textup{hist}}}H_{\textup{out}}\ket{\psi_{\textup{hist}}}\bra{\psi_{\textup{hist}}}.

The history state is defined as

\ket{\psi_{\textup{hist}}}=\frac{1}{\sqrt{M+1}}\sum_{t=1}^{M}\tilde{U}_{t}\cdots\tilde{U}_{1}\ket{x}_{A}\otimes\ket{0...0}_{B}\otimes\ket{t}_{C}

and

\bra{\psi_{\textup{hist}}}H_{\textup{out}}\ket{\psi_{\textup{hist}}}=\frac{1}{M+1}\bra{x,0}U_{x}^{\dagger}(\ket{0}\bra{0}_{\textup{out}}\otimes I)U_{x}\ket{x,0}.

The eigenvalue of $H_{\rm{eff},1}$ is given by $\bra{\psi_{\textup{hist}}}H_{\textup{out}}\ket{\psi_{\textup{hist}}}$ and this is $\mathcal{O}((\Delta/M^{2})^{-1})=\mathcal{O}(1/\mathrm{poly}(n))$ -close to the ground state energy of $H$ using Equation (11).

It can be verified that $\bra{\psi_{\textup{hist}}}H_{\textup{out}}\ket{\psi_{\textup{hist}}}\leq(1-\alpha)/(M+1)$ if $U_{x}$ accepts $x$ with probability at least $\alpha$ and $\bra{\psi_{\textup{hist}}}H_{\textup{out}}\ket{\psi_{\textup{hist}}}\geq(1-\beta)/(M+1)$ if $U_{x}$ accepts $x$ with probability at most $\beta$ . As we have mentioned earlier, we can assume $\alpha=1-2^{-n}$ and $\beta=2^{-n}$ . Therefore, the ground state energy $a$ of $H$ lies in the range of $0\pm\mathcal{O}((\Delta/M^{2})^{-1})$ if $x\in\Pi_{\textup{yes}}$ and the ground state energy $b$ of $H$ lies in the range of $1/(M+1)\pm\mathcal{O}((\Delta/M^{2})^{-1})$ if $x\in\Pi_{\textup{no}}$ .

We also see the spectral gap between the ground state and any excited state in both the YES and NO cases. We first see the NO case. As we have shown, the ground state energy lies in $\frac{1-2^{n}}{M+1}\pm\mathcal{O}((M^{2}/\Delta))$ . In $H=\Delta(H_{\textup{in}}+H_{\textup{prop}}+H_{\textup{stab}})+H_{\textup{out}}$ , the eigenvalues of $\Delta(H_{\textup{in}}+H_{\textup{prop}}+H_{\textup{stab}})$ is perturbed at most $\|H_{\textup{out}}\|=1$ . Therefore, the smallest non-zero eigenvalue of $H$ is larger than $(\Delta\pi^{2})/(64M^{2})-1$ . The spectral gap in the NO case is therefore

\mathcal{O}\left(\frac{\Delta}{M^{2}}\right)-1-\left(\frac{1-2^{-n}}{M+1}+\mathcal{O}\left(\frac{M^{2}}{\Delta}\right)\right).

The ground state energy in the YES case is smaller than that in the NO case. Therefore, we can take sufficiently large $\Delta\in\mathrm{poly}(n)$ so that $H$ has inverse-polynomial spectral gap and $b-a\in\Omega(1/\mathrm{poly}(n))$ . Finally, we can normalize $H$ by a polynomially large factor, which concludes the proof.

3.2 Extending to excited states

The next proposition extends the result to excited states, at the cost of increasing the locality of the construction by one.

Proposition 3.4.

For any $\delta\in\Omega(0,1-1/\text{poly}(n))$ there exist $a,b\in[-1,1]$ with $b-a\in\Omega(1/\text{poly}(n))$ and some number $0\leq c\leq\text{poly}(n)$ such that $\text{GLHLE}(6,c,a,b,\delta)$ is BQP-hard even when,

1.

the $c$ ’th eigenvalue of $H$ , $\lambda_{c}(H)$ , is non-degenerate and is separated by a gap $\gamma\in\Omega(1/\text{poly}(n))$ from both $\lambda_{c-1}(H)$ and $\lambda_{c+1}(H)$ . (We call such instances $\gamma$ -gapped
$\text{GLHLE}(k,c,a,b,\delta)$ .)
2.

The guiding state is restricted to be a semi-classical subset state.

Proof 3.5.

We will reduce directly from the BQP-complete Hamiltonian $H$ as defined in Eq. (2). Again, let $\ket{u}$ be a semi-classical guiding state such that $\left|\braket{u}{\psi_{0}}\right|\geq\zeta$ . Consider the following $6$ -local Hamiltonian $H^{(c)}$ on $n+1$ qubits⁶⁶6Note that this gadget can be trivially changed such that estimating the $n$ highest energy states is BQP-hard.:

\displaystyle H^{(c)}=H^{(z)}\otimes\ket{0}\bra{0}+H^{(s)}\otimes\ket{1}\bra{1},

(8)

where

	$\displaystyle H^{(z)}=\sum_{i=0}^{d}2^{i}\|1\rangle\langle 1\|_{i}+\sum_{i=d+1}^{n}2^{d+1}\|1\rangle\langle 1\|_{i}-\left(c-\frac{1}{2}\right)I,$
	$\displaystyle H^{(s)}=\frac{1}{2}\frac{H+I/4}{\\|H\\|+1/4}-\frac{1}{4}I,$

where we have that $d=\lceil\log_{2}(c)\rceil$ . $H^{(z)}$ has exactly $c$ states with negative energy, with the smallest eigenvalue being $-c+\frac{1}{2}$ and the largest eigenvalue value at $\sum_{i=0}^{d}2^{i}+\sum_{i=d+1}^{n}2^{d+1}-\left(c-\frac{1}{2}\right)=2^{d+1}+2^{d+1}(n-d)-\frac{1}{2}-c$ . The spectrum jumps in integer steps of $1$ , and has as largest negative (resp. smallest non-negative) energy value $-\frac{1}{2}$ (resp. $\frac{1}{2}$ ). Since $\text{eig}(H^{(s)})\in[-1/4,1/4]$ , we must have that $H^{(s)}$ sits precisely at the $c$ ’th excited state level (or $c+1$ ’th eigenstate level) in $H^{(c)}$ . Therefore, given a guiding state $\ket{u}$ for $H$ such that $\left|\bra{u}{\psi_{0}}\rangle\right|\geq\delta$ , one has that the guiding state $\lvert u^{(c)}\rangle=\ket{u}\otimes\ket{1}$ is also semi-classical and must have $|\langle u^{(c)}\lvert\psi_{c}^{(c)}\rangle|\geq\delta$ , where $\lvert\psi_{c}^{(c)}\rangle$ denotes the $c$ th excited state of $H^{(c)}$ . Since this construction of $H^{(c)}$ and $\lvert u^{(c)}\rangle$ provides a polynomial time reduction from an instance of $\text{GLH}(k,a,b,\delta)$ to one of $\text{GLHLE}(k,c,a,b,\delta)$ , whenever $c=\mathcal{O}(\mathrm{poly}(n))$ , we must have that $\text{GLHLE}(k,c,a,b,\delta)$ is BQP-hard whenever $k\geq 6$ . The gap between $\lambda_{c}(H^{(c)})-\lambda_{c-1}(H^{(c)})=\frac{1}{4}$ and the gap between $\lambda_{c+1}(H^{(c)})-\lambda_{c}(H^{(c)})=\gamma$ as before. The norm of the new Hamiltonian is bounded by $|H^{(c)}|=\mathcal{O}(\text{poly}(n))$ , hence after normalisation we retain $\lambda_{c}(H^{(c)})-\lambda_{c-1}(H^{(c)})\geq\lambda_{c+1}(H^{(c)})-\lambda_{c}(H^{(c)})=\Omega(1/\text{poly}(n))$ .

3.3 Locality reduction and reduction to physically motivated Hamiltonians via strong Hamiltonian simulation

The next two propositions bring (i) the locality $k$ down to $2$ and (ii) extend the result to any of non-2SLD $\mathcal{S}$ -Hamiltonian on a 2D square lattice.

Proposition 3.6.

Any $\gamma$ -gapped $\text{GLHLE}(k,c,a,b,\delta)$ with $k\in\mathcal{O}(1)$ , $b-a\in\Omega(1/\mathrm{poly}(n))$ , $\delta\in(0,1-\Omega(1/\mathrm{poly}(n)))$ , $0\leq c\leq\text{poly}(n)$ , and $\gamma\in\Omega(1/\mathrm{poly}(n))$ with a guiding semi-classical subset state can be reduced to $\gamma^{\prime}$ -gapped $\text{GLHLE}(2,c,a^{\prime},b^{\prime},\delta^{\prime})$ with $b^{\prime}-a^{\prime}\in\Omega(1/\mathrm{poly}(n))$ , $\delta^{\prime}\in(0,1-\Omega(1/\mathrm{poly}(n)))$ and $\gamma^{\prime}\in\Omega(\mathrm{poly}(n))$ , and with a guiding semi-classical subset state in polynomial time.

Proposition 3.7.

Any $\gamma$ -gapped $\text{GLHLE}(k,c,a,b,\delta)$ with $k\in\mathcal{O}(1)$ , $b-a\in\Omega(1/\mathrm{poly}(n))$ , $\delta\in(0,1-\Omega(1/\mathrm{poly}(n)))$ , $0\leq c\leq\text{poly}(n)$ and $\gamma\in\Omega(1/\mathrm{poly}(n))$ , and with a guiding semi-classical subset state can be reduced to $\gamma^{\prime}$ -gapped $\text{GLHLE}(2,c,a^{\prime},b^{\prime},\delta^{\prime})$ with $b^{\prime}-a^{\prime}\in\Omega(1/\mathrm{poly}(n))$ , $\delta^{\prime}\in(0,1-\Omega(1/\mathrm{poly}(n)))$ and $\gamma^{\prime}\in\Omega(\mathrm{poly}(n))$ in polynomial time whose Hamiltonian is restricted to any of non-2SLD $\mathcal{S}$ -Hamiltonian on a 2D square lattice.

Proof 3.8 (Proof of Propositions 3.6 and 3.7).

Let $H$ and $\ket{u}$ be arbitrary inputs of $\text{GLHLE}(k,c,a,b,\delta)$ with $k\in\mathcal{O}(1)$ , $b-a\in\Omega(1/\mathrm{poly}(n))$ , $\delta\in(0,1-\Omega(1/\mathrm{poly}(n)))$ . From Theorem A.3 (in Appendix A.1 ), we can efficiently find a non-2SLD $\mathcal{S}$ -Hamiltonian $H^{\prime}$ on a 2D square lattice that is a strong $(\Delta,\eta,\epsilon)$ -simulation of $H$ given the description of $H$ . We take $\epsilon<(b-a)/2$ , $b^{\prime}=b-\epsilon$ , $a^{\prime}=a+\epsilon$ and $\Delta=\mathcal{O}(\epsilon^{-1}\|H\|^{2}+\eta^{-1}\|H\|)$ so that $\lambda_{c}(H^{\prime})\leq a^{\prime}$ if $\lambda_{c}(H)\leq a$ , and $\lambda_{c}({H^{\prime}})\geq b^{\prime}$ if $\lambda_{c}({H})\geq b^{\prime}$ while $b^{\prime}-a^{\prime}\in\Omega(1/\mathrm{poly}(n))$ .

We have shown the existence of desirable eigenvectors in the simulated Hamiltonian. What remains to show is that (i) the encoded state of $\ket{u}$ still has $1-1/\mathrm{poly}(n)$ fidelity with $c$ ’th excited state of $H^{\prime}$ and (ii) the encoded state is still a semi-classical subset state after the simulation by a 2-local Hamiltonian (for concluding Proposition 3.6) , and (iii) the encoded state is still a semi-classical encoded state after the simulation by an arbitrary non-2SLD $\mathcal{S}$ -Hamiltonian on a 2D square lattice (for concluding Proposition 3.7).

(i) Verification of the fidelity.

The fidelity can be analyzed by the following lemma:

Lemma 3.9 (Simulation of the gapped excited state).

Suppose the $c$ ’th excited state $\ket{g}$ of $H$ is non-degenerate and separated from both the $c-1$ ’th excited state and $c+1$ ’th excited state by a gap $\gamma$ . Suppose $H^{\prime}$ is a $(\Delta,\eta,\epsilon)$ -simulation of $H$ such that $2\epsilon<\gamma$ . Then $H^{\prime}$ has a non-degenerate $c$ ’th excited state $\ket{g^{\prime}}$ and

\|\mathcal{E}_{\textup{state}}(\ket{g})-\ket{g^{\prime}}\|\leq\eta+\mathcal{O}(\gamma^{-1}\epsilon).

Proof 3.10.

This is a slight modification of Lemma 2 of [8]. First, the non-degeneracy of the $c$ ’th excited state of $H^{\prime}$ follows because the $i$ ’th smallest eigenvalues of $H$ and $H^{\prime}$ differs at most $\epsilon$ for all $0\leq i\leq{\rm dim}(H)-1$ , and $\epsilon$ satisfies $2\epsilon<\gamma$ . Consider $H$ as an unperturbed Hamiltonian and $V\coloneqq\tilde{\mathcal{E}}^{\dagger}H^{\prime}\tilde{\mathcal{E}}-H$ as a perturbation. Then, the perturbed Hamiltonian $H+V=\tilde{\mathcal{E}}^{\dagger}H^{\prime}\tilde{\mathcal{E}}$ has a non-degenerate $c$ ’th excited state $\tilde{\mathcal{E}}_{\textup{state}}(\ket{g^{\prime}})$ . The first-order perturbation theory for eigenvectors gives $\|\ket{g}-\tilde{\mathcal{E}}_{\textup{state}}^{\dagger}(\ket{g^{\prime}})\|\in\mathcal{O}(\gamma^{-1}\epsilon)$ . Therefore, it follows that $\|\tilde{\mathcal{E}}_{\textup{state}}(\ket{g})-\ket{g^{\prime}}\|=\|\tilde{\mathcal{E}}_{\textup{state}}(\ket{g})-\tilde{\mathcal{E}}_{\textup{state}}(\tilde{\mathcal{E}}_{\textup{state}}^{\dagger}(\ket{g^{\prime}}))\|\in\mathcal{O}(\gamma^{-1}\epsilon)$ using that $\tilde{\mathcal{E}}_{state}$ is an isometry and $\ket{g^{\prime}}\in{\rm Im}(\tilde{\mathcal{E}}_{state})$ . Finally, by using $\|\mathcal{E}_{state}-\tilde{\mathcal{E}}_{state}\|\leq\eta$ , $\|\mathcal{E}_{\textup{state}}(\ket{g})-\ket{g^{\prime}}\|\leq\eta+\mathcal{O}(\gamma^{-1}\epsilon)$ follows.

Using Lemma 3.9, we can take sufficiently small $\epsilon$ and $\eta$ to ensure $\|\mathcal{E}_{\textup{state}}(\ket{u})-\ket{g^{\prime}}\|\leq\delta^{\prime}=\delta-1/\mathrm{poly}(n)$ . Because the Hamiltonian simulation is efficient, the operator norm $\|H^{\prime}\|$ and the number of qubits of $H^{\prime}$ is in $\mathrm{poly}(n)$ .

(ii) Verification of the semi-classical property for Proposition 3.6.

We start from a semi-classical subset state $\ket{u}=1/\sqrt{|S|}\sum_{x\in S}\ket{x}$ . We show that after the simulation of the original $k$ -local Hamiltonian $H$ where $k\in\mathcal{O}(1)$ by an $2$ -local Hamiltonian, the corresponding encoding $\mathcal{E}_{\textup{state}}(\ket{u})$ is still a semi-classical subset state.

In order to simulate the $k$ -local Hamiltonian by a $2$ -local Hamiltonian (that has no restriction on the family of Hamiltonian), it is enough to use mediator qubit gadgets that attach $\ket{0}$ states for mediator qubits (called subdivision and 3-to-2 gadgets [27]). A $k$ -local term can be simulated by $(\lceil k/2\rceil+1)$ -local terms using the subdivision gadget. Moreover, subdivision gadgets can be applied to each of the terms of the Hamiltonian in parallel [28, 11]. Therefore, we can reduce a $k$ -local Hamiltonian to a 3-local Hamiltonian by $\mathcal{O}(\log{k})$ rounds of applications of the subdivision gadgets. Then we can use the 3-to-2 gadgets in parallel to reduce to a 2-local Hamiltonian. In the corresponding encoding of states of this procedure, polynomially many $\ket{0}$ states are attached to the original state. Clearly, by attaching polynomially many $\ket{0}$ states, a polynomial-size subset state is mapped to another polynomial-size subset state:

\frac{1}{\sqrt{|S|}}\sum_{x\in S}\ket{x}\rightarrow\frac{1}{\sqrt{|S|}}\sum_{x\in S}\ket{x}\ket{0}^{\otimes\mathrm{poly}(n)}=\frac{1}{\sqrt{|S|}}\sum_{x\in S\times\{0...0\}}\ket{x}.

This concludes the proof of Proposition 3.6.

(iii) Verification of the semi-classical property for Proposition 3.7.

We proceed to show that starting from a semi-classical subset state $\ket{u}$ , the resulting state is a semi-classical encoded state when we simulate the original Hamiltonian by a non-2SLD $\mathcal{S}$ -Hamiltonian on a 2D square lattice. There are three types of encodings used in the simulation:

•

Mediator qubits. In this encoding, some simple ancilla states are attached to the original state.
•

Subspace encoding. In this encoding, a local isometry is applied to the original state.
•

Local Unitaries. In this encoding, local unitary $U\otimes U\otimes\cdots\otimes U$ , where each of $U$ acts on one qubit, is applied to the original state.

We restate the chain of Hamiltonian simulations of Appendix C : {screen} Arbitrary $k$ -local Hamiltonian
$\downarrow$       (1) Mediator qubits. (Attach a semi-classical subset state $\ket{\alpha}$ .)
Spatially sparse $5$ -local Hamiltonian
$\downarrow$       (2) Mediator qubits. (Attach polynomially many $\ket{+_{y}}$ states.)
Spatially sparse $10$ -local real Hamiltonian
$\downarrow$       (3) Mediator qubits. (Attach polynomially many $\ket{0}$ or $\ket{1}$ states.)
Spatially sparse $2$ -local Pauli interactions with no $Y$ -terms
$\downarrow$       (4) Subspace encoding.
Spatially sparse $\mathcal{S}_{0}=\{XX+YY+ZZ\}$ or $\{XX+YY\}$ Hamiltonian
$\downarrow$       (5) Mediator qubits. (Attach polynomially many $\ket{0}$ or $\ket{1}$ states.)
$\mathcal{S}_{0}$ -Hamiltonians on a 2D square lattice
$\downarrow$       (6) Mediator qubits, Subspace encoding, and local unitary.
Arbitrary non-2SLD $\mathcal{S}$ -Hamiltonian on a 2D square lattice In step (1), a semi-classical subset state is attached to a semi-classical subset state $\ket{u}$ . The resulting state is also a semi-classical subset state:

	$\displaystyle\ket{u}=\frac{1}{\sqrt{\|S\|}}\sum_{x\in S}\ket{x}\rightarrow$	$\displaystyle\frac{1}{\sqrt{\|S\|}}\sum_{x\in S}\ket{x}\otimes\frac{1}{\sqrt{\|S^{\prime}\|}}\sum_{x^{\prime}\in S^{\prime}}\ket{x^{\prime}}$
		$\displaystyle=\frac{1}{\sqrt{\|S\|\|S^{\prime}\|}}\sum_{x\in S\times S^{\prime}}\ket{x}.$		(9)

The resulting state after the encodings of steps (2) $\sim$ (4) is a semi-classical encoded state because in these steps, a tensor product of single-qubit states is attached to a semi-classical subset state and then the state is encoded by a local isometry. By further performing a local encoding to the semi-classical encoded state, the resulting state is also a semi-classical encoded state. This concludes the proof of Proposition 3.7. Finally, we show a BQP-hardness result for the antiferromagnetic Hamiltonian.

Proposition 3.11.

For any $\delta\in(0,1-\Omega(1/\mathrm{poly}(n)))$ , there exist $a,b\in[0,1]$ with $b-a\in\Omega(1/\mathrm{poly}(n))$ and $0\leq c\leq\mathcal{O}(poly(n))$ such that the problem $\text{GLHLE}(2,c,a,b,\delta)$ with $b-a\in\Omega(1/\mathrm{poly}(n))$ is BQP-hard for Hamiltonians that are restricted to either $\{XX+YY+ZZ\}^{+}$ -Hamiltonian, or $\{XX+YY\}^{+}$ -Hamiltonian on a 2D triangular lattice.

Proof 3.12.

We first prove the case of $\{XX+YY+ZZ\}^{+}$ -Hamiltonian. This can be reduced from the GLHLE problem of $\{XX+YY+ZZ\}$ -Hamiltonian with a semi-classical encoded state as a guiding state, which is shown to be BQP-hard in Proposition 3.7. The $\{XX+YY+ZZ\}$ -Hamiltonian can be simulated by $\{XX+YY+ZZ\}^{+}$ -Hamiltonian using the “basic gadget” (this is a type of a mediator qubit gadget) of [28]. In the corresponding encoding of the state, a tensor product of two-qubit states is attached to the original state. This encodes a semi-classical encoded state to another semi-classical encoded state. The reason is as follows. Let us denote the attached tensor product of polynomially many two-qubit states as

\ket{\phi_{1}}\otimes\ket{\phi_{2}}\otimes\cdots\ket{\phi_{m}}=V^{\prime}_{1}\ket{0}\otimes V^{\prime}_{2}\ket{0}\otimes\cdots V^{\prime}_{m}\ket{0},

where $\ket{\phi_{1}},...,\ket{\phi_{m}}$ are two-qubit states and $V^{\prime}_{1},...,V^{\prime}_{m}$ are isometries such that $V^{\prime}_{i}\ket{0}=\ket{\phi_{i}}$ for each $i\in[m]$ . Then, the original semi-classical encoded state represented by a polynomial-size subset $S$ and a local isometry $V_{1}\otimes V_{2}\otimes\cdots\otimes V_{n}$ is mapped to a semi-classical encoded state represented by a subset $S\times\{0...0\}$ and a local isometry $V_{1}\otimes\cdots\otimes V_{n}\otimes V^{\prime}_{1}\otimes\cdots\otimes V^{\prime}_{m}$ . This concludes the case of $\{XX+YY+ZZ\}^{+}$ -Hamiltonian.

We next show the BQP-hardness of the GLHLE problem of $\{XX+YY\}^{+}$ -Hamiltonian on a 2D triangular lattice with a semi-classical encoded state. We show a reduction from the GLHLE problem of $\{XX+YY\}$ -Hamiltonian on a 2D square lattice with a semi-classical encoded state as a guiding state, which is shown to be BQP-hard in Proposition 3.7. It is shown in [28] how to simulate $\{XX+YY\}$ -Hamiltonian on a 2D square lattice by $\{XX+YY\}^{+}$ -Hamiltonian on a 2D triangular lattice by using mediator qubit gadgets. The corresponding encoding is just attaching a product state of polynomially many $\mathcal{O}(1)$ -qubit states to the original guiding state. Therefore, the original semi-classical encoded state is mapped to another semi-classical encoded state (by a similar reason as in the case of $\{XX+YY+ZZ\}^{+}$ -Hamiltonian).

References

[1] Scott Aaronson. Why quantum chemistry is hard. Nature Physics, 5:707–708, 2009. doi:10.1038/nphys1415.
[2] Daniel S. Abrams and Seth Lloyd. Quantum algorithm providing exponential speed increase for finding eigenvalues and eigenvectors. Physical Review Letters, 83:5162–5165, 1999. URL: https://link.aps.org/doi/10.1103/PhysRevLett.83.5162, doi:10.1103/PhysRevLett.83.5162.
[3] Andris Ambainis. On physical problems that are slightly more difficult than QMA. In 29th IEEE Conference on Computational Complexity (CCC), pages 32–43, 2014.
[4] Alán Aspuru-Guzik, Anthony D. Dutoi, Peter J. Love, and Martin Head-Gordon. Simulated quantum computation of molecular energies. Science, 309(5741):1704–1707, 2005. doi:10.1126/science.1113479.
[5] Bela Bauer, Sergey Bravyi, Mario Motta, and Garnet Kin-Lic Chan. Quantum algorithms for quantum chemistry and quantum materials science. Chemical Reviews, 120(22):12685–12717, 2020. arXiv:https://doi.org/10.1021/acs.chemrev.9b00829, doi:10.1021/acs.chemrev.9b00829.
[6] Jacob D Biamonte and Peter J Love. Realizable hamiltonians for universal adiabatic quantum computers. Physical Review A, 78(1):012352, 2008.
[7] Sergey Bravyi, David DiVincenzo, and Daniel Loss. Schrieffer–Wolff transformation for quantum many-body systems. Annals of physics, 326(10):2793–2826, 2011.
[8] Sergey Bravyi and Matthew Hastings. On complexity of the quantum ising model. Communications in Mathematical Physics, 349(1):1–45, 2017.
[9] Marco Cerezo, Andrew Arrasmith, Ryan Babbush, Simon C. Benjamin, Suguru Endo, Keisuke Fujii, Jarrod R. McClean, Kosuke Mitarai, Xiao Yuan, Lukasz Cincio, and Patrick J. Coles. Variational quantum algorithms. Nature Reviews Physics, 3:625–644, 2021. doi:s42254-021-00348-9.
[10] Toby Cubitt and Ashley Montanaro. Complexity classification of local hamiltonian problems. SIAM Journal on Computing, 45(2):268–316, 2016.
[11] Toby Cubitt, Ashley Montanaro, and Stephen Piddock. Universal quantum hamiltonians. Proceedings of the National Academy of Sciences, 115(38):9497–9502, 2018.
[12] Richard Feynman. Simulating physics with computers. International Journal of Theoretical Physics, 21(6–7):467–488, 1982.
[13] Richard Feynman. Quantum mechanical computers. Optics News, 11:11, 1985.
[14] Sevag Gharibian and Julia Kempe. Hardness of approximation for quantum problems. In Proceedings of the 39th International Colloquium on Automata, Languages and Programming (ICALP 2012), pages 387–398, 2012.
[15] Sevag Gharibian and François Le Gall. Dequantizing the quantum singular value transformation: hardness and applications to quantum chemistry and the quantum PCP conjecture. In Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing, pages 19–32, 2022. Full version available as ArXiv:2111.09079. doi:10.1145/3519935.3519991.
[16] Sevag Gharibian and Ojas Parekh. Almost Optimal Classical Approximation Algorithms for a Quantum Generalization of Max-Cut. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019), volume 145, pages 31:1–31:17, 2019.
[17] Sevag Gharibian and Justin Yirka. The complexity of simulating local measurements on quantum systems. Quantum, 3:189, 2019. doi:10.22331/q-2019-09-30-189.
[18] Alex Bredariol Grilo, Iordanis Kerenidis, and Jamie Sikora. QMA with subset state witnesses. In International Symposium on Mathematical Foundations of Computer Science, pages 163–174. Springer, 2015.
[19] Aram W. Harrow, Avinatan Hassadim, and Seth Lloyd. Quantum algorithm for solving linear systems of equations. Physical Review Letters, 15(103):150502, 2009.
[20] Stephen P. Jordan, David Gosset, and Peter J. Love. Quantum-Merlin-Arthur–complete problems for stoquastic hamiltonians and markov matrices. Phys. Rev. A, 81:032331, Mar 2010. arXiv:0905.4755. URL: https://link.aps.org/doi/10.1103/PhysRevA.81.032331, doi:10.1103/PhysRevA.81.032331.
[21] Julia Kempe, Alexei Yu. Kitaev, and Oded Regev. The complexity of the local Hamiltonian problem. SIAM journal on Computing, 35(5):1070--1097, 2006.
[22] Alexei Yu. Kitaev. Quantum measurements and the Abelian Stabilizer Problem. arXiv:quant-ph/9511026, 1995.
[23] Alexei Yu. Kitaev, Alexander H. Shen, and Mikhail N. Vyalyi. Classical and Quantum Computation. American Mathematical Society, 2002.
[24] Joonho Lee, Dominic W. Berry, Craig Gidney, William J. Huggins, Jarrod R. McClean, Nathan Wiebe, and Ryan Babbush. Even more efficient quantum computations of chemistry through tensor hypercontraction. PRX Quantum, 2:030305, 2021. URL: https://link.aps.org/doi/10.1103/PRXQuantum.2.030305, doi:10.1103/PRXQuantum.2.030305.
[25] Seunghoon Lee, Joonho Lee, Huanchen Zhai, Yu Tong, Alexander M Dalzell, Ashutosh Kumar, Phillip Helms, Johnnie Gray, Zhi-Hao Cui, Wenyuan Liu, et al. Is there evidence for exponential quantum advantage in quantum chemistry? arXiv preprint arXiv:2208.02199, 2022.
[26] Lin Lin and Yu Tong. Near-optimal ground state preparation. Quantum, 4:372, 2020.
[27] Roberto Oliveira and Barbara M. Terhal. The complexity of quantum spin systems on a two-dimensional square lattice. Quantum Information and Computation, 8(10):0900--0924, 2008.
[28] Stephen Piddock and Ashley Montanaro. The complexity of antiferromagnetic interactions and 2d lattices. Quantum Information & Computation, 17(7-8):636--672, 2017.
[29] Markus Reiher, Nathan Wiebe, Krysta M. Svore, Dave Wecker, and Matthias Troyer. Elucidating reaction mechanisms on quantum computers. Proceedings of the National Academy of Sciences, 114(29):7555--7560, 2017. URL: https://www.pnas.org/content/114/29/7555, arXiv:https://www.pnas.org/content/114/29/7555.full.pdf, doi:10.1073/pnas.1619152114.
[30] Norbert Schuch and Frank Verstraete. Computational complexity of interacting electrons and fundamental limitations of density functional theory. Nature Physics, 5:732--735, 2009.
[31] Yuan Su, Dominic W. Berry, Nathan Wiebe, Nicholas Rubin, and Ryan Babbush. Fault-tolerant quantum simulations of chemistry in first quantization. PRX Quantum, 2:040332, Nov 2021. URL: https://link.aps.org/doi/10.1103/PRXQuantum.2.040332, doi:10.1103/PRXQuantum.2.040332.
[32] Tzu-Chieh Wei, Michele Mosca, and Ashwin Nayak. Interacting boson problems can be QMA hard. Physical Review Letters, 104:040501, 2010.
[33] Leo Zhou and Dorit Aharonov. Strongly universal Hamiltonian simulators. arXiv preprint arXiv:2102.02991, 2021.

Appendix A Approximate Hamiltonian simulation

A.1 Introduction of approximate Hamiltonian simulation

While in the QMA-hardness reduction it suffices to focus only on the eigenvalues in the simulation, in the reduction of GLH it is also important to know how the eigenvectors change in the perturbative simulation. It is convenient to introduce the notion of approximate Hamiltonian simulation to show the reduction of GLH.

Definition A.1 (Approximate Hamiltonian simulation [11], [33]).

We say that an $m$ -qubit Hamiltonian $H^{\prime}$ is a $(\Delta,\eta,\epsilon)$ -simulation of an $n$ -qubit Hamiltonian $H$ if there exists a local encoding $\mathcal{E}(M)=V(M\otimes P+\bar{M}\otimes Q)V^{\dagger}$ such that

1.

There exists an encoding $\tilde{\mathcal{E}}(M)=\tilde{V}(M\otimes P+\bar{M}\otimes Q)\tilde{V}^{\dagger}$ such that $\tilde{\mathcal{E}}(\mathbbm{1})=P_{\leq\Delta(H^{\prime})}$ and $\|\tilde{V}-V\|\leq\eta$ , where $P_{\leq\Delta(H^{\prime})}$ is the projector onto the subspace spanned by eigenvectors of $H^{\prime}$ with eigenvalue below $\Delta$ ,
2.

$\|H^{\prime}_{\leq\Delta}-\tilde{\mathcal{E}}(H)\|\leq\epsilon$ , where $H^{\prime}_{\leq\Delta}\coloneqq P_{\leq\Delta(H^{\prime})}H^{\prime}$ .

Here, $V$ is a local isometry that can be written as $V=\bigotimes_{i}V_{i}$ where each $V_{i}$ is an isometry acting on at most 1 qubit, and $P$ and $Q$ are locally orthogonal projectors (i.e. for all $i$ there exist orthogonal projectors $P_{i}$ and $Q_{i}$ acting on the same subsystem as $V_{i}$ such that $P_{i}Q_{i}=0$ , $P_{i}P=P$ and $Q_{i}Q=Q$ ) such that $P+Q=I$ , and $\bar{M}$ is the complex conjugate of $M$ . Moreover, we say that the simulation is efficient if $m$ and $\|H^{\prime}\|$ are at most $\mathcal{O}(\mathrm{poly}(n,\eta^{-1},\epsilon^{-1},\Delta))$ , and the description of $H^{\prime}$ can be computable in $\mathrm{poly}(n)$ time given the description of $H$ .

We approximately simulate the original Hamiltonian $H$ in the low-energy subspace of $H^{\prime}$ . There is a corresponding encoding of a state which can be taken as

\mathcal{E}_{\textup{state}}(\rho)=V(\rho\otimes\sigma)V^{\dagger}

for $\sigma$ such that $P\sigma=\sigma$ (if $P\neq 0$ ). If $\rho$ is the eigenvector of $H$ with eigenvalue $\alpha$ , then $\mathcal{E}_{\textup{state}}(\rho)$ is approximately the eigenvector of $H^{\prime}$ with eigenvalue $\alpha^{\prime}\in[\alpha-\epsilon,\alpha+\epsilon]$ .

In [33], it is shown that there exist families of Hamiltonians that can efficiently simulate any $\mathcal{O}(1)$ -local Hamiltonians. They call such families of Hamiltonians strongly universal Hamiltonians.⁷⁷7 It would be possible to show Theorem 1.1 by modifying the verifier circuit $\tilde{U}_{x}$ following [27] to make the constructed Hamiltonian spatially sparse. We believe Proposition 3.6 is interesting because the reduction holds for arbitrary $\mathcal{O}(1)$ -local Hamiltonian even if it is not originally spatially sparse. We use the construction of strongly universal Hamiltonians of [33] to show Proposition 3.6. Formally, the strong (and weak) universality is defined as follows:

Definition A.2 (Strong and weak universality [33]).

A family of Hamiltonians $\mathcal{H}=\{H_{m}\}$ is weakly universal if given any $\Delta,\eta,\epsilon>0$ , any $\mathcal{O}(1)$ -local, $n$ -qubit Hamiltonian can be $(\Delta,\eta,\epsilon)$ -simulated. Such a family is strongly universal if the simulation is always efficient.

The following result is shown in [33]:

Theorem A.3 ([33]).

Any non- $2SLD$ $\mathcal{S}$ -Hamiltonian on a $2D$ -square lattice is strongly universal.

Appendix B Schrieffer-Wolf transformation for 1-dimensional gapped ground space

Let us introduce the Schrieffer-Wolf transformation and its approximation [7] which we use in the proof. We only consider the case when the unperturbed Hamiltonian has 1-dimensional ground space.

Let $H_{0}$ be a Hamiltonian that has 1-dimensional ground space spanned by $\ket{g_{0}}$ whose energy is 0. Let us assume that the smallest non-zero eigenvalue of $H_{0}$ is larger than one. Consider the following (perturbed) Hamiltonian: $H=\Delta H_{0}+V$ . We shall always assume that $\|V\|\leq\Delta/2$ in the following. Then, there is only one eigenvector (which we denote $\ket{g}$ ) of $H$ with eigenvalue lying in the interval of $[-\Delta/2,\Delta/2]$ (Lemma 3.1 of [7]).

Then, the Schrieffer-Wolf (SW) transformation is defined as a unitary $U_{\rm SW}$ that maps the ground space of $H$ to that of $H_{0}$ . That is, $U_{\rm SW}\ket{g}=\ket{g_{0}}$ . The Hamiltonian

H_{\rm eff}=\Pi_{0}U_{\rm SW}(\Delta H_{0}+V)U_{\rm SW}^{\dagger}\Pi_{0}

is called the effective low-energy Hamiltonian. Here, $\Pi_{0}$ is the projector onto the ground space of $H_{0}$ . The eigenvector of $H_{\rm eff}$ is $\ket{g_{0}}$ and the eigenvalue is the same as the eigenvalue of $\ket{g}$ with respect to $H$ .

Next, we show how to approximate $U_{\rm SW}$ and $H_{\rm eff}$ . We only need the simplest first-order approximation in the proof of Proposition 3.2. In the following, we further assume $\|V\|\leq\Delta/16$ . Then, it is known that

\|I-U_{\rm SW}\|\in\mathcal{O}(\Delta^{-1}\|V\|)

(10)

and

\|H_{\rm eff}-\Pi_{0}V\Pi_{0}\|\in\mathcal{O}(\Delta^{-1}\|V\|^{2})

(11)

hold (Lemma 3.4 [7], Lemma 4 [8]). This means that $I$ and $\Pi_{0}V\Pi_{0}$ work as the first-order approximation of $U_{\rm SW}$ and $H_{\rm eff}$ , respectively. The derivation and the forms of the higher-order terms can be found in [7]. From eq. (10), it follows that

\big{\|}\ket{g}-\ket{g_{0}}\big{\|}=\left\|(I-U_{\rm SW}^{\dagger})\ket{g_{0}}\right\|\in\mathcal{O}(\Delta^{-1}\|V\|).

(12)

It follows from eq. (11) that the ground state energy of $H$ differs at most $\mathcal{O}(\Delta^{-1}\|V\|^{2})$ from the eigenvalue of $H_{\rm{eff},1}\coloneqq\Pi_{0}V\Pi_{0}$ (restricted to the space spanned by $\ket{g_{0}}$ ).

Appendix C Encoding of states for strong Hamiltonian simulation

We sketch the construction of the strong Hamiltonian simulation introduced in [33]. The simulation mainly consists of two parts. First, they construct spatially sparse 5-local Hamiltonian [27] using a quantum phase estimation circuit and its modification. This procedure may be thought of as a “Hamiltonian-to-circuit” (then goes back to Hamiltonian by circuit-to-Hamiltonian) construction. Then, they perturbatively simulate the spatially sparse Hamiltonian with known techniques in the literature [27, 11, 28]. In the following, we overview their construction.

(1) Arbitrary $k$ -local Hamiltonian $\rightarrow$ spatially sparse $5$ -local Hamiltonian ([33]).

Let $H$ be a target $\mathcal{O}(1)$ -local Hamiltonian. Assume that $H$ can be written as $H=\sum_{i}E_{i}\ket{\psi_{i}}\bra{\psi_{i}}$ where $\{E_{i}\}$ and $\{\ket{\psi_{i}}\}$ are the eigenvalues and eigenvectors of $H$ . In [33], they showed that there is a spatially sparse quantum circuit $U^{\rm sparse}_{\rm PE}$ that approximately estimates the energy of $H$ , i.e.

U^{\rm sparse}_{\rm PE}\sum_{i}c_{i}\ket{\psi_{i}}\ket{0^{m}}\approx\sum_{i}c_{i}\ket{\psi_{i}}\ket{\tilde{E}_{i}}\ket{other},

where $\{c_{i}\}$ are arbitrary coefficients and $\{|\tilde{E}_{i}\rangle\}$ are approximations of $\{E_{i}\}$ .

The circuit $U^{\rm sparse}_{\rm PE}$ is implemented first by constructing $U^{\rm sparse}_{\rm NN}$ that consists of 1D nearest-neighborhood interaction. Then, $U^{\rm sparse}_{\rm NN}$ is converted into a spatially sparse circuit using ancilla qubits and swap gates.

Then they combine uncomputation and idling to construct

U=({\rm Idling})(U^{\rm sparse}_{\rm PE})^{\dagger}({\rm Idling})U^{\rm sparse}_{\rm PE}.

They apply circuit-to-Hamiltonian construction for this $U$ to construct spatially sparse 5-local Hamiltonian $H_{\rm circuit}$ . They use first-order perturbation theory to show that $H_{\rm circuit}$ simulates $H$ in its low-energy subspace. The encoding of $H_{\rm circuit}$ to the low energy subspace of $H$ is approximated by the map: $H\rightarrow H\otimes\ket{\alpha}\bra{\alpha}$ . Here, $\ket{\alpha}$ is a subset state with $\mathrm{poly}(n)$ -size subset $S^{\prime}$ that is related to the history state of the idling steps after uncomputation. For detail, see the proof of Proposition 2 of [33]. Then, the corresponding encoding of the state is

\ket{u}\rightarrow\ket{u}\otimes\ket{\alpha}.

The encoded state is also a semi-classical subset state if $\ket{u}$ is a semi-classical subset state.

(2) Spatially sparse $5$ -local Hamiltonian $\rightarrow$ Spatially sparse $10$ -local real Hamiltonian (Lemma 22 of [11]).

In this simulation, the state is encoded by attaching polynomially many $\ket{+_{y}}$ where $\ket{+_{y}}$ is the $+1$ eigenvector of Pauli $Y$ matrix:

\ket{u}\rightarrow\ket{u}\otimes\ket{+_{y}}\otimes\cdots\otimes\ket{+_{y}}.

(13)

This encoding does not map a semi-classical subset state into a semi-classical state but maps into a semi-classical encoded state. The reason is as follows. Let $V_{y}$ be a unitary such that $\ket{+_{y}}=V_{y}\ket{0}$ , and $\ket{u}=1/\sqrt{|S|}\sum_{x\in S}\ket{x}$ . Then, the right side of eq. (13) can be written as

\ket{u}\otimes\ket{+_{y}}\otimes\cdots\otimes\ket{+_{y}}=\frac{1}{\sqrt{|S|}}\sum_{x\in S\times\{0...0\}}I\otimes\cdots\otimes I\otimes V_{y}\otimes\cdots\otimes V_{y}\ket{x}.

This is a semi-classical encoded state with a subset $S\times\{0...0\}$ and a local isometry (this is indeed a local unitary) $I\otimes\cdots\otimes I\otimes V_{y}\otimes\cdots\otimes V_{y}$ .

(3) Spatially sparse $10$ -local real Hamiltonian $\rightarrow$ Spatially sparse $2$ -local Pauli interactions with no $Y$ -terms ([27, 10]).

This can be done first by simulating the $10$ -local real Hamiltonian with $11$ -local Hamiltonian whose Pauli decomposition does not contain any Pauli $Y$ terms [11, Lemma 40]. In the corresponding encoding, $\ket{1}$ states are attached for the polynomially many mediator qubits introduced in the simulation. Then, we can use subdivision gadgets and 3-to-2 gadgets [27]. In this simulation, polynomially many mediator qubits are introduced, and the encoding of states is just to add $\ket{0}$ states for each of the mediator qubits. The resulting Hamiltonian can be written in the form $\sum_{i<j}\alpha_{ij}A_{ij}+\sum_{k}(\beta_{k}X_{k}+\gamma_{k}Z_{k})$ , where $A_{ij}$ is one of the interactions of $X_{i}X_{j}$ , $X_{i}Z_{j}$ , $Z_{i}X_{j}$ or $Z_{i}Z_{j}$ .

(4) Subspace encoding for spatially sparse $\mathcal{S}_{0}=\{XX+YY+ZZ\}$ or $\{XX+YY\}$ Hamiltonian (Theorem 42 of [11]).

We have already obtained 2-local Hamiltonian in the form $\sum_{i<j}\alpha_{ij}A_{ij}+\sum_{k}(\beta_{k}X_{k}+\gamma_{k}Z_{k})$ . Then we show how to simulate this Hamiltonian with arbitrary non-2SLD $\mathcal{S}$ -Hamiltonians. We first consider $\mathcal{S}_{0}$ Hamiltonian, where $\mathcal{S}_{0}=\{XX+YY+ZZ\}$ or $\mathcal{S}_{0}=\{XX+YY\}$ . In this simulation, we use subspace encoding in which the logical qubit of the original Hamiltonian is encoded into four physical qubits. Consider the simulation by Heisenberg interaction $\{XX+YY+ZZ\}$ for example. Each logical qubit is encoded into 4 qubit state by an isometry that is defined as

		$\displaystyle V\ket{0}=\ket{0_{L}}=\ket{\Psi_{-}}_{13}\ket{\Psi_{-}}_{24}$		(14)
		$\displaystyle V\ket{1}=\ket{1_{L}}=\frac{2}{\sqrt{3}}\ket{\Psi_{-}}_{12}\ket{\Psi_{-}}_{34}-\frac{1}{\sqrt{3}}\ket{\Psi_{-}}_{13}\ket{\Psi_{-}}_{24},$		(15)

where $\ket{\Psi_{-}}=(\ket{01}-\ket{10})/\sqrt{2}$ . For details, see [11, Theorem 42]. The encoding of states for XX+YY interaction is the same. A semi-classical encoded state is clearly mapped to a semi-classical encoded state by applying a local isometry of the corresponding subspace encoding.

(5) Spatially sparse $\mathcal{S}_{0}$ -Hamiltonian $\rightarrow$ $\mathcal{S}_{0}$ -Hamiltonians on a 2D square lattice (Lemma 47 of [11]).

This simulation can be done using three perturbative gadgets called subdivision, fork, and crossing gadgets. All of these gadgets attach a mediator qubit for each use of the gadgets. $\mathcal{O}(1)$ rounds of parallel use of perturbative gadgets are sufficient to simulate a spatially sparse $\mathcal{S}_{0}$ -Hamiltonian by a $\mathcal{S}_{0}$ -Hamiltonians on a 2D square lattice, which prevents the interaction strength to grow exponentially. (For general interaction graphs, $\mathcal{O}(\log{n})$ rounds of perturbative simulations are necessary.)

(6) $\mathcal{S}_{0}$ -Hamiltonian on 2D square lattice $\rightarrow$ Arbitrary non-SLD $\mathcal{S}$ -Hamiltonian on a 2D square lattice (Theorem 43 of [11]).

Finally, this simulation is similarly done by using variants of mediator qubit gadgets or subspace encoding gadgets as well as applying local unitaries.⁸⁸8Applying local unitaries means to simulate $H$ by $U^{\otimes n}H(U^{\dagger})^{\otimes n}$ where $U$ acts on one qubit. The corresponding encoding of state is $\mathcal{E}_{state}(\ket{\psi})=U^{\otimes n}\ket{\psi}$ .

	$\displaystyle\ket{u}=\frac{1}{\sqrt{\|S\|}}\sum_{x\in S}\ket{x}\rightarrow$	$\displaystyle\frac{1}{\sqrt{\|S\|}}\sum_{x\in S}\ket{x}\otimes\frac{1}{\sqrt{\|S^{\prime}\|}}\sum_{x^{\prime}\in S^{\prime}}\ket{x^{\prime}}$
		$\displaystyle=\frac{1}{\sqrt{\|S\|\|S^{\prime}\|}}\sum_{x\in S\times S^{\prime}}\ket{x}.$		(9)