Analytic and Stochastic Approach to Quantum Advantages in Ground State and Quantum State Preparation Problems

Taehee Ko Affiliation: School of Computational Sciences, KIAS Sungbin Lim Affiliation: kthmomo@kias.re.kr, sungbin@korea.ac.kr Affiliation: Department of Statistics, Korea University Affiliation: LG AI Research

Abstract

We study the problems of state preparation, ground state preparation and quantum state preparation. We propose an analytic approach to a stochastic quantum algorithm which prepares the ground state for $n$ -qubit Hamiltonian that is represented by $\text{poly}(n)$ Pauli operators and has an inverse-polynomial gap, requiring only $\text{poly}(n)$ Pauli rotations, measurements, and classical time complexity when $n$ exceeds a threshold, to inverse-polynomial precision given the initial overlap being lower bounded by $\frac{1}{2^{n}}$ . Extending this result, we prove that any $n$ -qubit quantum state can be prepared in two regimes: (1) with a constant number of Pauli rotations to constant precision, or (2) with a polynomial number of rotations to inverse-polynomial precision. Our results improve over previous approaches to quantum state preparation in terms of gate complexity, thereby yielding quantum space advantage. As an application, we identify a practical condition under which quadratic unconstrained binary optimization (QUBO) problems can be solved with exponential quantum speedups.

1 Introduction

The task of state preparation is central to quantum algorithms and their applications dalzell2023quantum. In quantum optimization applications, one encodes the problem as an $n$ -qubit Hamiltonian whose ground state corresponds to the target solution. This simple framework has been extensively explored through variational approaches peruzzo2014variational; farhi2014quantum in recent years, encouraging a wide range of applications with the hope of quantum advantage, such as quantum simulation cerezo2021variational, combinatorial optimization amaro2022filtering, material design kang2025quantum; bauer2020quantum, drug discovery ghazi2025quantum; santagati2024drug, and finance orus2019quantum. Yet complexity-theoretical studies place these variational approaches on uncertain footing, showing fundamental obstacles from optimization perspectives bittel2021training; mcclean2018barren; larocca2023theory; anschuetz2022quantum. This trajectory of research highlights the importance of a rigorous foundation of quantum advantages in many optimization tasks, especially for ground state preparation, which is known to be difficult even for quantum computers kempe2006complexity.

To clarify the class of Hamiltonians for which the ground state can be prepared in a polynomial sized circuit, which is connected to the quantum space advantage, a necessary condition may be that the relative spectral gap of Hamiltonian scales $\Omega\left(\frac{1}{\text{poly}(n)}\right)$ , as inferred from all existing frameworks including adiabatic quantum algorithm albash2018adiabatic, filtering-based lin2020near; dong2022ground; chakraborty2025quantum; gilyen2019quantum, quantum imaginary time mcmahon2025equating; gluza2024double, and Lindblad-based algorithms ding2025end; ding2024single, while it is conjectured as a sufficient condition from a complexity theoretic viewpoint deshpande2022importance. Together, the set of Hamiltonians with an inverse-polynomial gap is regarded as the largest class to consider, and complexity-theoretic results mcmahon2025equating; chakraborty2025quantum are applicable without circuit oracular assumption lin2020near; ding2024single; dong2022ground; gluza2024double. According to mcmahon2025equating, the presence of a factor of $16^{n}$ appears in the bounds for both circuit depth and the number of measurements. On the other hand, chakraborty2025quantum; dong2022ground guarantee a $\mathcal{O}(\text{poly}(n))$ circuit depth, but the ground state is prepared with post-selection. In fact, such filtering-based or QPE-based methods face the well-known issue of initial overlap berry2025rapid; fomichev2024initial; lee2023evaluating; dong2022ground. These observations lead us to the following question.

Is there an algorithm applicable for any Hamiltonian with an inverse-polynomial gap, such that prepares the ground state in a $\mathcal{O}(\text{poly}(n))$ circuit depth using few or no ancilla qubits, with $\mathcal{O}(\text{poly}(n))$ measurements, and $\mathcal{O}(\text{poly}(n))$ classical processing time?

Results	Initial overlap	Circuit depth	Circuit measurement	Hamiltonian
mcmahon2025equating	non-zero overlap^†	$\mathcal{O}\left(16^{n}\text{poly}(n)e^{\text{poly}(n)}\right)$	$\mathcal{O}\left(16^{n}\text{poly}(n)e^{\text{poly}(n)}\right)$	not-specified
chakraborty2025quantum	non-zero overlap^†	$\mathcal{O}(\text{poly}(n))$	$\mathcal{O}\left(4^{n}\log\text{poly}(n)\right)$	not-specified
Ours	non-zero overlap (3)	$\mathcal{O}(\text{poly}(n))$	$\mathcal{O}\left(\text{poly}(n)\right)$	any system

Table 1: Comparison between existing results and ours for ground state preparation. Hamiltonian refers to a Pauli-sparse model (e.g.

m=\mathcal{O}(\text{poly}(n))

in (1)) with a

\Omega\left(\frac{1}{\text{poly}(n)}\right)

gap, for which a corresponding ground state preparation incurs

\mathcal{O}(\text{poly}(n))

costs in terms of circuit depth and the number of circuit measurements. ^†As results rely on an arbitrarily small non-zero initial overlap, we use (3) to derive complexities for a fair comparison, and further assume that the chosen initial state does not affect the circuit depth.

We answer the above question in the affirmative by assuming the overlap of an initial state with the ground state is no less than $\frac{1}{2^{n}}$ and an inverse-polynomial lower bound for the gap is known. We prove that for any $n$ -qubit Hamiltonian with an inverse-polynomial gap, the ground state can be prepared within a polynomial sized circuit and in polynomial time, using a proposed stochastic iterative quantum algorithm inspired by the Riemannian gradient flow wiersema2023optimizing, when $n$ is larger than a threshold. As an application, we show that two NP-hard problems by Barahona barahona1982computational are solvable in polynomial time, with probability close to one. Assuming that the overlap of an initial state with the target state is no less than $\frac{1}{2^{n}}$ , we also present a result on the quantum state preparation by proving that any $n$ -qubit state can be represented by a polynomial sized circuit, to within constant (shorter circuit) or inverse-polynomial precision (longer circuit), without ancilla qubit, when $n$ is larger than a threshold. This result guarantees a quantum space advantage.

The assumption on initial state in both state preparation problems is validated by the fact that such an initial state always exists. Moreover, the assumption on the spectral gap in the problem of ground state preparation is typically used in the analysis of algorithm, for instance, when choosing a proper step size mcmahon2025equating; gluza2024double; ding2025end, and constructing a filtering polynomial chakraborty2025quantum; dong2022ground. While at least QMA-hard ambainis2014physical, estimating a spectral gap is analytically tractable for some structured systems (e.g. 2D Hamiltonians chen2024local and Ising models barahona1982computational as will be discussed in Section 4). Thus, our results exponentially improve over the existing algorithms mcmahon2025equating; chakraborty2025quantum, as summarized in Table 1 in terms of circuit depth and/or the number of measurements. Additionally, contrary to chakraborty2025quantum, our circuit prepares the ground state deterministically, once successfully constructed. For the task of quantum state preparation, our result exponentially improves the circuit complexity over all known results, by introducing a notion of approximation. This is summarized in Table 2.

Results	Gate complexity	Circuit depth	Ancilla qubit	Precision
yuan2023optimal	$\mathcal{O}(2^{n})$	$\mathcal{O}(2^{n}/n)$	-	1
sun2023asymptotically		$\mathcal{O}(n)$	$\mathcal{O}(2^{n})$
zhang2022quantum		$\mathcal{O}(n)$	$\mathcal{O}(2^{n})$
gui2023spacetime		$\mathcal{O}(n)$	$\mathcal{O}(2^{n})$
Ours	$\mathcal{O}(n/\epsilon)$	$\mathcal{O}(\log n^{1/\epsilon})$	-	$1-\epsilon$

Table 2: Comparison between existing results and ours for quantum state preparation. Gate complexity refers to the total number of single-qubit gates and CNOT gates and Precision indicates the overlap of a prepared state with the target state. For ours, Theorem 3.3 guarantees that for any

\epsilon\in(0,1)

, either

\epsilon=\Theta(1)

\epsilon=\Theta(\frac{1}{\text{poly}(n)})

, the tolerance set by a user.

2 Related works

2.1 Ground state preparation

We discuss recent frameworks for the task of ground state preparation from technical perspectives, focusing on underlying theoretical challenges.

Variational Quantum Eigensolver (VQE) and Adaptive Variants

To date, no clear theoretical result has shown the convergence of VQE peruzzo2014variational to ground state. From an optimization perspective, vanilla VQE face critical challenges, such as the presence of barren plateau anschuetz2022quantum; mcclean2018barren; park2023hamiltonian and the necessity of over-parametrization for sufficient expressivity larocca2023theory. Alternatively, adaptive VQEs have been proposed to improve numerical results with a strategy of growing circuit construction grimsley2023adaptive; yordanov2021qubit; tang2021qubit without rigorous guarantees. The recent studies magann2023randomized; malvetti2024randomized; mcmahon2025equating focus on the convergence of randomized adaptive methods. In particular, analytic results in malvetti2024randomized; mcmahon2025equating show the existence of a circuit for ground state preparation, but without efficient circuit complexity guarantee.

Adiabatic State Preparation (ASP)

In ASP, finding a good initial state is not a problem, as the approach often starts with the ground state of an easy initial Hamiltonian. However, a significant challenge is to identify an adiabatic path where the minimum of spectral gaps along an adiabatic path is guaranteed to scale inverse-polynomial. Moreover, it is also non-trivial to identify a class of Hamiltonians that guarantees such an adiabatic path albash2018adiabatic.

Filtering-based Quantum Algorithms with Post-selection

Filtering-based algorithms, which are motivated by the quantum phase estimation nielsen2010quantum or the quantum singular value transformation gilyen2019quantum, enable preparing the ground state based on measurement outcomes lin2020near; dong2022ground; chakraborty2025quantum. When the desired measurement is successfully obtained, the ground state is prepared. However, since the success probability scales linearly or quadratically with the inverse of the initial overlap, these approaches typically require an inverse-polynomially large overlap, which is recognized as a significant challenge lee2023evaluating; berry2025rapid; fomichev2024initial.

Quantum Imaginary Time Evolution (QITE)

Existing QITE-based approaches incur an exponential circuit depth in general gluza2024double; motta2020determining, due to the circuit construction of non-unitary step. The method motta2020determining is heuristic due to errors in compiling the non-unitary QITE step, which arise from the step of solving linear systems. While global convergence guarantee is shown in gluza2024double, their approach requires a good initial state, since the rate of convergence scales linearly with the initial overlap when it is small, thereby involving a similar issue as the filtering-based methods.

Lindblad-type Algorithms

As has emerged recently, Lindblad-based approaches have the advantage that they require no initial condition (e.g., zero initial overlap) chen2024local; ding2024single; lloyd2025quasiparticle; zhan2025rapid; ding2025end, but face following challenges: constructing jump operators with efficient circuits, and identifying a class of Hamiltonians that feature efficient mixing time and simulation time, both of which remain difficult and strongly depend on quantum systems. Thus far, clear complexity-theoretic results with efficient circuit constructions have been obtained only for toy models, such as a single-qubit Hamiltonian and non-interacting fermionic systems ding2025end.

Regime of Quantum Computing

Variational approaches are categorized into the regime of Noisy Intermediate-Scale Quantum computing (NISQ) peruzzo2014variational; grimsley2019adaptive; malvetti2024randomized. Several algorithms including our algorithm may be implemented faithfully in the regime of Early Fault-Tolerant Quantum Computing (EFTQC). For instance, ASP albash2018adiabatic, a filtering-based algorithm dong2022ground and Lindblad-based algorithm ding2025end require Hamiltonian simulation, and a Trotterized filtering-based algorithm chakraborty2025quantum uses Pauli rotations. Essentially, these algorithms require Pauli rotations with small angles, since Hamiltonian simulation can be implemented using the Trotter formula with small step sizes. Implementing Pauli rotations with small angles may be considered as EFTQC toshio2025practical. lin2020near; chen2024local rely on block encodings of matrices, and gluza2024double demands non-trivial circuit constructions of reflectors, and the circuit depth increases exponentially (base-3) with respect to the number of iterations. Similarly, mcmahon2025equating requires an exponential circuit depth. Therefore, these three algorithms are regarded as FTQC.

2.2 Quantum state preparation

A lower bound of $\mathcal{O}(2^{n})$ gate complexity is shown for exact quantum state preparation plesch2011quantum. Since this work, the circuit depth has been improved at the cost of ancilla qubits (e.g. from $\mathcal{O}(2^{n})$ depth to $\mathcal{O}(n)$ depth with $\mathcal{O}(2^{n})$ ancilla qubits sun2023asymptotically; zhang2022quantum; gui2023spacetime). Similarly, araujo2021divide achieves a linear circuit depth, but their approach cannot be directly applied to standard quantum state preparation due to entangled garbage states in the ancilla register. Exceptionally, the method yuan2023optimal achieves $\mathcal{O}(\frac{2^{n}}{n})$ depth without ancilla qubit. Nonetheless, all of these approaches incur an exponential gate complexity. On the other hand, A notion of approximation error is introduced to effectively reduce circuits for certain structured quantum states, such as tensor network techniques ben2024approximate; melnikov2023quantum. function approximations moosa2023linear; zylberman2024efficient, and sparse quantum state preparation gleinig2021efficient; feniou2024sparse.

3 Main Results

3.1 Formulation

We first formulate two problems in quantum state preparation and present our main results on their theoretical complexity. The first problem, Ground State Preparation, is whether the ground state can be prepared within a polynomial sized circuit, for any Hamiltonian whose relative spectral gap scales inverse-polynomial. The second one, arbitrary Quantum State Preparation, concerns more general case, whether any quantum state can be prepared with quantum space advantages.

Problem 1 (Ground State Preparation).

Let $n\in\mathbb{N}$ and $H$ be an $n$ -qubit Hamiltonian of the form,

\displaystyle H=\sum_{k=1}^{m}a_{k}P_{k},

(1)

where each $P_{k}$ is a Pauli string and $m\in[4^{n}]$ . Assume that the relative spectral gap of $H$ decays inverse-polynomially, that is,

\displaystyle\frac{\Delta}{\norm{H}_{2}}=\Omega\left(\frac{1}{\text{poly}(n)}\right).

(2)

We further assume an initial state $\ket{\psi_{1}}$ with an exponentially small (base-2) overlap with the ground state $\ket{\lambda_{1}}$ of $H$ , i.e.,

\displaystyle\absolutevalue{\bra{\lambda_1}\ket{\psi_1}}\ket{\psi_{1}}^{2}\geq\frac{1}{2^{n}}.

(3)

The ground state preparation problem asks for any $\epsilon\geq\epsilon_{f}$ with a tolerance $\epsilon_{f}>0$ depending only on $n$ , we can find a circuit $U$ , represented by a product of $S$ $n$ -qubit Pauli rotations without ancilla qubits, satisfying

\displaystyle\mathbb{P}\left(\absolutevalue{\bra{\lambda_1}U\ket{\psi_{1}}}U\ket{\psi_{1}}^{2}\geq 1-\epsilon\right)\geq 1-\eta,

(4)

where $S$ and $\eta$ depend on $\epsilon,n$ , and $\frac{\Delta}{\|H\|_{2}}$ .

Theorem 3.1.

There exists $N_{0}\in\mathbb{N}$ such that for any $n\geq N_{0}$ , we can solve the Problem 1 with

\displaystyle\epsilon_{f}=\Omega\left(\frac{1}{\text{poly}(n)}\right),\ S=\mathcal{O}(\text{poly}(n)),\ \eta=\mathcal{O}\left(\frac{1}{\text{poly}(n)}\right).

(5)

Precisely, we can find a tunable parameter $C=\Omega\left(\frac{1}{\text{poly}(n)}\right)$ which controls $S$ and $\eta$ as follows

\displaystyle S=\mathcal{O}\left(\frac{\norm{H}_{2}}{C\Delta}\right),\quad\eta=\Theta\left(\frac{C\Delta}{\epsilon\norm{H}_{2}}\right),

(6)

with $0<C\leq C_{0}\leq 1$ where $C_{0}$ depends on $\epsilon,n$ , and $\frac{\Delta}{\|H\|_{2}}$ .

Corollary 3.2.

Suppose $m=\mathcal{O}(\text{poly}(n))$ in the Hamiltonian model (1) and an inverse-polynomial lower bound for the relative spectral gap is given a priori. Then we can construct a circuit by spending $\mathcal{O}(\text{poly}(n))$ classical time and performing $\mathcal{O}(\text{poly}(n))$ measurements.

Problem 2 (Quantum State Preparation).

Let an arbitrary $n$ -qubit quantum state $\ket{\phi}\in\mathbb{C}^{2^{n}}$ , and assume a computational basis state $\ket{j_{\phi}}$ with an exponentially small (base-2) overlap with $\ket{\phi}$ ,

\displaystyle\absolutevalue{\bra{\phi}\ket{j_\phi}}\ket{j_{\phi}}^{2}\geq\frac{1}{2^{n}}.

(7)

The quantum state preparation problem asks for any $\epsilon\geq\epsilon_{f}>0$ with a tolerance $\epsilon_{f}$ depending only on $n$ , we can find a circuit $U$ , represented by a product of $S$ $n$ -qubit Pauli rotations without ancilla qubits, satisfying

\displaystyle\mathbb{P}\left(\absolutevalue{\bra{\phi}U\ket{j_{\phi}}}U\ket{j_{\phi}}^{2}\geq 1-\epsilon\right)\geq 1-\eta,

(8)

where $S$ and $\eta$ depend on $\epsilon$ and $n$ .

Theorem 3.3.

There exists $N_{0}\in\mathbb{N}$ such that for any $n\geq N_{0}$ , we can solve the Problem 2 depending on the following two regimes:

1.

(constant precision regime)

$\displaystyle\epsilon_{f}=\Theta(1),\quad S=\mathcal{O}(1),\quad\eta=\mathcal{O}(1).$ (9)

(inverse-polynomial precision regime)

\displaystyle\epsilon_{f}=\Theta\left(\frac{1}{\text{poly}(n)}\right),\ S=\mathcal{O}(\text{poly}(n)),\ \eta=\mathcal{O}\left(\frac{1}{\text{poly}(n)}\right).

(10)

Precisely, we can find a tunable parameter $C=\Omega(1)$ for the constant precision and $C=\Omega\left(\frac{1}{\text{poly}(n)}\right)$ for the inverse-polynomial precision, respectively, which controls $S$ and $\eta$ as follows

\displaystyle S=\mathcal{O}\left(\frac{1}{C}\right),\quad\eta=\Theta\left(\frac{C}{\epsilon}\right),

(11)

with $0<C\leq C_{0}\leq 1$ where $C_{0}$ depends on $\epsilon$ and $n$ .

We remark that the only component of circuit construction in Theorems 3.1 and 3.3 is the Pauli rotation, which leads to explicit evaluation of circuit complexity. The circuit complexity of a Pauli rotation is determined in terms of circuit depth and gate complexity as follows haah2024efficient; baumer2025measurement,

(a)

(1D connectivity): $\mathcal{O}(n)$ depth, $\mathcal{O}(n)$ gates, and no ancilla qubit.
(b)

(all-to-all connectivity): $\mathcal{O}(\log n)$ depth, $\mathcal{O}(n)$ gates, and no ancilla qubit.
(c)

(measurement-based dynamic circuit): $\mathcal{O}(1)$ depth, $\mathcal{O}(n)$ gates, and $\mathcal{O}(n)$ ancilla qubits.

For a ground state preparation (Problem 1), the circuit is constructed with (a), (b) $\mathcal{O}(\text{poly}(n))$ single-qubit and CNOT gates without ancilla qubit, and (c) a shorter circuit depth with $\mathcal{O}(n)$ ancilla qubits. For a quantum state preparation (Problem 2), in the constant precision regime, the circuit is constructed with (a) $\mathcal{O}(n)$ single-qubit, CNOT gates, and $\mathcal{O}(n)$ depth, (b) $\mathcal{O}(\log n)$ depth without ancilla qubit, and (c) $\mathcal{O}(1)$ depth with $\mathcal{O}(n)$ ancilla qubits. In the inverse-polynomial precision regime, the circuit complexity scales as (a), (b) $\mathcal{O}(\text{poly}(n))$ without ancilla qubit, and (c) a shorter circuit depth with $\mathcal{O}(n)$ ancilla qubits.

3.2 Algorithm: Stochastic Riemannian Gradient Flow

We introduce our algorithm to achieve Theorems 3.1 and 3.3. Motivated by the Riemannian gradient flow wiersema2023optimizing, we propose a randomized version, Stochastic Riemannian Gradient Flow (SRGF). The algorithm aims to solve the ground state problem,

\min_{U\in\text{SU}(2^{n})}\bra{\psi}U^{\dagger}HU\ket{\psi},

(12)

for a given initial state $\ket{\psi_{1}}$ by finding a unitary corresponding to the minimum in the specialized unitary group $\text{SU}(2^{n})$ through a continuous dynamical system,

\frac{\text{d}U_{t}}{\text{d}t}=\mathcal{M}_{t}(\psi)U_{t},\quad\mathcal{M}_{t}(\psi):=[U_{t}\outerproduct{\psi}{\psi}U_{t}^{\dagger},H].

(13)

A discretization of dynamical system (13) allows a systematic way of compiling unitaries to the given quantum state $\ket{\psi}$ for approximating the ground state wiersema2023optimizing. Due to the Euler method, for a time step size $\delta t>0$ , we obtain a discrete version of the continuous dynamics (13),

\displaystyle U_{t+\delta t}\approx(I+\delta t\mathcal{M}_{t}(\psi))U_{t}\approx\exp( \delta t \mathcal{M}_{t}(\psi))U_{t}.

(14)

Since the commutator of Hermitians is skew-Hermitian, the image of exponential mapping in (14) is unitary. Hence we obtain a discrete recursive relation between unitaries. However, the exact implementation on a quantum computer may be infeasible since the commutator can be arbitrary, and so can the resulting unitary. Instead, several approaches have been proposed by approximately computing the commutator term. For example, the term is approximated by considering only local Pauli rotations wiersema2023optimizing, randomly sampling from the Haar measure magann2023randomized, and a group commutator formula gluza2024double. Algorithm 1 samples multiple distinct Pauli rotations at each iteration and apply the first-order Trotter formula to approximate the commutator term.

Algorithm 1 Stochastic Riemannian Gradient Flow (SRGF)

Data: Initial state

\ket{\psi_{1}}

, step size

\delta t

, batch size

J

, maximal iteration step

T

Result: Circuit

U

such that

U\ket{\psi_{1}}

approximates the ground state.

Define

U_{0}=I

for $t=0:T-1$ do

Sample a pool of distinct Paulis

\{P_{t}^{(j)}\}_{j=1}^{J}

Compute

c_{t}^{(j)}=\frac{1}{2^{n}}\bra{\psi_{1}}U_{t}^{\dagger}[H,P_{t}^{(j)}]U_{t}\ket{\psi_{1}}

Set

U_{t+1}=\prod_{j=1}^{J}\exp\left(c_{t}^{(j)}P_{t}^{(j)}\delta t\right)U_{t}

end for

Output

U=U_{T}

In the first step of Algorithm 1, we sample $J$ distinct Paulis in a uniform manner. The naive strategy of sampling directly on the entire set of $4^{n}$ Pauli operators may require an exponential time. As an alternative, we suggest an efficient strategy as follows, which requires $\mathcal{O}(n)$ time.

Remark 3.4 (Efficient sampling distinct Pauli operators).

We consider the quaternary representations of $n$ -qubit Paulis where we define a one-to-one correspondence,

X\longleftrightarrow 0,\;Y\longleftrightarrow 1,\;Z\longleftrightarrow 2,\;I\longleftrightarrow 3.

(15)

Fix an integer $k\leq n$ . Then, for the first $k$ digits, we perform the uniform sampling without repetitions on the set of $4^{k}$ Paulis, and for the last $n-k$ digits, the uniform sampling on the set of $4^{n-k}$ Paulis. Since $k=\mathcal{O}(1)$ , sampling distinct $J$ $k$ -qubit Paulis from the $4^{k}$ possible outcomes takes $\mathcal{O}(1)$ classical time. The other sampling can be merely done by picking an element from $\{0,1,2,3\}$ uniformly and repeating this $n-k$ times in $\mathcal{O}(n)$ time (sequential) or $\mathcal{O}(1)$ time (parallel). Thus, sampling distinct Paulis is efficiently done, the number of total outcomes is ${4^{k}\choose J}4^{n-k}$ and the probability of sampling one outcome is $J/4^{n}$ .

At each iteration, SRGF algorithm compiles the unitary $U_{t}$ with respect to the initial state $\ket{\psi_{1}}$ by performing measurements for the corresponding observables to compute the coefficient $c_{t}^{(j)}$ . Notice that the coefficient is derived from the Pauli expansion of the commutator,

[U_{t}\outerproduct{\psi}{\psi}U_{t}^{\dagger},H]=\sum_{j=1}^{4^{n}}\frac{\bra{\psi}U_{t}^{\dagger}[H,P_{j}]U_{t}\ket{\psi}}{2^{n}}P_{j},

(16)

due to the identity $\tr\left([U_{t}\outerproduct{\psi}{\psi}U_{t}^{\dagger},H]P_{j}\right)=\bra{\psi}U_{t}^{\dagger}[H,P_{j}]U_{t}\ket{\psi}$ . Once the algorithm has computed the coefficient, it appends the corresponding Pauli rotations. Let $T$ denote the maximal iteration step. After $T$ iterations, the resulting circuit consists of $JT$ Pauli rotations. The total classical and quantum complexity for the implementation of Algorithm 1 is summarized as:

•

Classical time complexity for sampling Pauli operators: Due to the sampling strategy in Remark 3.4, we have $\mathcal{O}(n)$ classical time sequentially and $\mathcal{O}(1)$ classical time in parallel.
•

Total circuit sampling complexity: Let $N_{shots}$ indicate the number of circuit sampling at each iteration to estimate the coefficients $\{c_{t}^{(j)}\}_{j=1}^{J}$ . We have $\mathcal{O}(N_{shots}T)$ circuit sampling complexity in total. The cost depends linearly on the number of sampled Pauli operators $J$ and that of Pauli operators constituting the Hamiltonian $H$ , i.e., $\mathcal{O}(\text{poly}(n))$ .
•

Circuit complexity or iteration complexity: The resulting circuit is a product of $JT$ Pauli rotations since $J$ Pauli rotations are appended at each iteration.

3.3 Proof of Theorems 3.1 and 3.3

Now we present our proof strategy for main results. We first describe key ideas to prove Theorem 3.1. Then we explain how similar ideas can be applied to Theorem 3.3. Details are shown in Section A.4.

3.3.1 Decomposition of Recursive Unitary Compiling

The first step is to decompose the unitary compiling in Algorithm 1 and characterize systematic errors. To understand by comparison, let us consider the case of non-unitary relation in (14). Without considering quantum device error, the recursive unitary compiling in Algorithm 1 involves four types of analytic error: (1) the first-order Trotter error, (2) the approximation error due to a Taylor-series expansion, (3) the sampling error of Pauli operators $\{P_{t}^{(j)}\}_{j=1}^{J}$ , and (4) the circuit sampling error from measurements by the Born rule when computing the coefficient $c_{t}^{(j)}$ . Let us incorporate the first three errors into the recursive unitary compiling in Algorithm 1. Observe that,

\displaystyle\begin{split}U_{t+1}&=\prod_{j=1}^{J}\exp(c_{t}^{(j)}P_{t}^{(j)}\delta t)U_{t}=\left(\exp\left(\delta t\sum_{j=1}^{J}c_{t}^{(j)}P_{t}^{(j)}\right)+E_{t}^{(1)}\right)U_{t},\end{split}

(17)

where $E_{t}^{(1)}$ accounts for the first-order Trotter error. Due to the Taylor approximation and the sampling step of Pauli operators in Algorithm 1, we obtain (we write $\mathcal{M}_{t}:=\mathcal{M}_{t}(\psi_{1})$ ),

\displaystyle U_{t+1}=\Big(\exp\Big(\delta t\sum_{j=1}^Jc_{t}^{(j)}P_{t}^{(j)}\Big)+E_{t}^{(1)}\Big)U_{t}=\left(I+\delta t\mathcal{M}_{t}+E_{t}^{(1)}+E_{t}^{(2)}+E_{t}^{(3)}\right)U_{t},

(18)

where the error $E_{t}^{(2)}$ involves the high-order terms in the Taylor-series approximation. The error $E_{t}^{(3)}$ occurs due to the step of sampling Pauli operators in Algorithm 1, which is defined by

E_{t}^{(3)}=\delta t\left(\sum_{j=1}^{J}c_{t}^{(j)}P_{t}^{(j)}-\mathcal{M}_{t}\right).

(19)

Recall that Algorithm 1 utilizes only a constant number $J$ of Pauli operators to approximate the commutator term, which constitutes a sum of exponentially many Pauli operators. Surprisingly, our result shows that the systematic errors scale inverse-exponentially or constantly with respect to the number of qubits $n$ . This is attributed to the presence of factor $\frac{1}{2^{n}}$ in the coefficient $c_{t}^{(j)}$ .

For simplicity, we focus on the case without circuit sampling error in this section. The following lemma provides estimates of errors which are keys in our analysis. We refer the reader to Section A.2 for the proof. We cover the case with circuit sampling error in Section A.5.

Lemma 3.5.

The errors $E_{t}^{(1)}$ , $E_{t}^{(2)}$ , and $E_{t}^{(3)}$ are bounded as follows

\begin{split}\|E_{t}^{(1)}\|_{2}&\leq\left(\frac{J\norm{H}_{2}}{2^{n-1}}\right)^{2}(\delta t)^{2},\\ \|E_{t}^{(2)}\|_{2}&\leq\frac{(\delta t)^{2}}{2}\exp\left(\frac{J\norm{H}_{2}}{2^{n-1}}\delta t\right)\left(\frac{J\norm{H}_{2}}{2^{n-1}}\right)^{2},\\ \|E_{t}^{(3)}\|_{2}&\leq 2\delta t\norm{H}_{2}.\end{split}

(20)

Additionally, it holds

\displaystyle\mathbb{E}[E_{t}^{(3)}|\mathcal{F}_{t}]=\delta t\left(\frac{J}{4^{n}}-1\right)\mathcal{M}_{t}.

(21)

3.3.2 Properties and Behavior of Overlap Process

The decomposition (18) immediately admits a recursive relation of the overlap with the ground state of Hamiltonian, since it is directly linked to the definition of overlap,

F_{t}:=\absolutevalue{\bra{\lambda_1}U_t\ket{\psi_1}}U_{t}\ket{\psi_{1}}^{2},\quad t\in\mathbb{N}

(22)

where $\ket{\lambda_{1}}$ denotes the ground state, $U_{t}$ is the circuit obtained at the $t$ -th iteration step, and $\ket{\psi_{1}}$ is the initial state chosen. A sequence of overlap $(F_{t})_{t\in\mathbb{N}}$ defines a stochastic process with a filtration $(\mathcal{F}_{t})_{t\in\mathbb{N}}$ , since the circuit compiling through Algorithm 1 involves randomness in sampling $J$ Pauli operators at each step. We present important properties and behavior of $F_{t}$ to show the iteration complexity of Algorithm 1.

Let us consider a case of deterministic process where there are no errors in (18). Then

\displaystyle\bra{\psi_{1}}U_{t}^{\dagger}HU_{t}\ket{\psi_{1}}-\lambda_{1}=\sum_{i=1}^{2^{n}}\lambda_{i}\absolutevalue{\bra{\lambda_i}U_t\ket{\psi}}U_{t}\ket{\psi}^{2}-\lambda_{1}\geq\lambda_{1}F_{t}+\lambda_{2}(1-F_{t})-\lambda_{1}=(1-F_{t})\Delta.

(23)

Here $\Delta:=\lambda_{2}-\lambda_{1}\geq 0$ denotes the spectral gap. Therefore, it holds that

\displaystyle F_{t+1}

\displaystyle=\left(1+\delta t(\bra{\psi_{1}}U_{t}^{\dagger}HU_{t}\ket{\psi_{1}}-\lambda_{1})\right)^{2}F_{t}\geq\left(1+\delta t(1-F_{t})\Delta\right)^{2}F_{t}.

(24)

Hence a deterministic overlap process $(F_{t})_{t\in\mathbb{N}}$ is lower bounded by a logistic function. For a case of stochastic overlap process, by Lemma 3.5, (20) shows errors scale inverse-exponentially or constantly with respect to the number of qubits $n$ . Thus, for sufficiently large $n$ , the errors are negligible. With a constraint on the step size $\delta t$ , by taking the conditional expectation, we can obtain the similar behavior to the deterministic counterpart in (24) as follows

\mathbb{E}[F_{t+1}|\mathcal{F}_{t}]\geq\left(1+\frac{\delta t}{2}(1-F_{t})\Delta\right)F_{t}.

(25)

Furthermore, using the error bounds in Lemma 3.5, we can show the following inequality

\displaystyle\sqrt{F_{t+1}}\leq\sqrt{F_{t}}+\frac{C_{1}\delta t}{2^{n}},

(26)

for some constant $C_{1}>0$ which can be controlled by a quantity depending on $J$ and $\norm{H}_{2}$ . We refer the reader to Theorem A.7 for the proof. We remark behaviors (25) and (26) of overlap process $(F_{t})_{t\in\mathbb{N}}$ are crucial to our analysis, by providing a scaling of the growing rate $\delta t(1-F_{t})\Delta/2$ in average and an upper bound of the next overlap up to an additive factor.

3.3.3 Derivation of Iteration Complexity with a Relative Spectral Gap

Let us write $\mathcal{T}:=\frac{\norm{H}_{2}}{C\Delta}$ with $\mathcal{T}=\mathcal{O}(\text{poly}(n))$ and $C=\Omega\left(\frac{1}{\text{poly}(n)}\right)$ . Based on (25) and (26), we can set a step size $\delta t=\mathcal{O}(2^{n}/\mathcal{T})$ and the maximal iteration time $T=\Theta(\mathcal{T})$ satisfying

\displaystyle\frac{\delta t}{2}(1-F_{t})\frac{\Delta}{\norm{H}_{2}}\geq\frac{2^{n}}{\mathcal{T}^{2}}\geq 2^{\frac{n}{T}},\quad n\geq N_{0},\ t\leq T+1,

(27)

where the threshold $N_{0}$ is determined only by $J$ , $F_{1}$ , and $\frac{\Delta}{\norm{H}_{2}}$ . By using (25) and (27), we get

\displaystyle F_{t}\leq 1-\frac{\epsilon}{2}+\frac{C_{\eta}}{2\mathcal{T}},\quad\mathbb{E}[F_{t+1}|\mathcal{F}_{t}]\geq 2^{\frac{n}{T}}F_{t},\quad t\leq T+1.

(28)

on the event $\{F_{t}\geq\frac{1}{2^{n+1}}(1-\frac{\epsilon}{2})\}$ for $\epsilon\geq\epsilon_{f}=\Omega\left(\frac{1}{\text{ploy}(n)}\right)$ and constant $C_{\eta}>0$ . To investigate a lower bound for the expectation of $F_{T+1}$ on this event, let us define a stopping time $\tau:=\min\{t:F_{t}<\frac{1}{2^{n+1}}(1-\frac{\epsilon}{2})\}$ and set $A:=\{\tau<T+1\}$ . By Doob’s Optional Stopping Theorem (williams1991probability, Theorem 10.10), we get the following

\displaystyle\mathbb{E}[F_{T+1}\mathds{1}_{A^{c}}]\geq 1-\frac{\epsilon}{2}.

(29)

Now we can apply the reverse Markov inequality to tighten a lower bound of $\mathbb{P}(F_{T+1}\geq 1-\epsilon)$ ,

\displaystyle\mathbb{P}(F_{T+1}\geq 1-\epsilon)\geq\mathbb{P}(F_{T+1}\mathds{1}_{A^{c}}\geq 1-\epsilon)\geq\frac{\mathbb{E}[F_{T+1}\mathds{1}_{A^{c}}]-(1-\epsilon)}{1-\frac{\epsilon}{2}+\frac{C_{\eta}}{2\mathcal{T}}-(1-\epsilon)}\geq 1-\frac{1}{1+\frac{\epsilon\mathcal{T}}{C_{\eta}}}.

(30)

Hence Theorem 3.1 is proved with $\eta=\mathcal{O}\left(\frac{1}{\epsilon\mathcal{T}}\right)$ . The key idea of the proof for Theorem 3.3 is that for any state $\ket{\phi}$ , we set the Hamiltonian, $H_{\ket{\phi}}=-\outerproduct{\phi}{\phi}$ , whose ground state is $\ket{\phi}$ and the relative spectral gap is one. Following the proof of Theorem 3.1, we obtain the desired result. See Section A.4 for details.

4 Applications to Combinatorial Optimization

Algorithms	Exponential speedup?	Regimes
QAA	✗	EFTQC
QAOA	✗	NISQ
Grover’s algorithm	✗	FTQC
pirnay2024principle	✗	FTQC
Ours	any NP-hard model satisfying (32)	EFTQC

Table 3: Comparison between existing algorithms and ours for combinatorial optimization.

Numerous NP optimization problems reduce to the classical Ising model lucas2014ising,

H=\sum_{i=1}^{n}h_{i}Z_{i}+\sum_{1\leq i<j\leq n}J_{ij}Z_{i}Z_{j}.

(31)

A ground state of the model (31) is essentially a computational basis state as the matrix $H$ is diagonal. Equivalent to QUBO abbas2024challenges, this problem arises in a wide range of applications kochenberger2014unconstrained; lucas2014ising. To the best of our knowledge, three quantum algorithms have been extensively explored, Quantum Annealing Algorithm (QAA) kadowaki1998quantum, Quantum Approximate Optimization Algorithm (QAOA) farhi2014quantum, and Grover’s algorithm grover1996fast. While QAAs are theoretically guaranteed similar to the adiabatic quantum computing, the required evolution time is expected to be exponential in general abbas2024challenges. Meanwhile, QAOA optimizes parametrized quantum circuits but lacks rigorous guarantee, much like VQE. Although Grover’s algorithm has been applied to combinatorial optimization problems dalzell2023quantum; gilliam2021grover, the widely-believed quadratic speedups remain uncertain due to the recent dequantization result stoudenmire2024opening. The recent work pirnay2024principle presents special integer programming instances and proves a super-polynomial speedup borrowed from Shor’s algorithm. See Table 3 for a summary.

Algorithm 1 provides exponential speedups for a class of NP-hard Ising models (31). This class of Ising models is clearly characterized by the non-zero coefficients in (31) that satisfying

\displaystyle\frac{\absolutevalue{J_{ij}}}{\sum_{i^{\prime}j^{\prime}}\absolutevalue{J_{i'j'}}+\sum_{i^{\prime}}\absolutevalue{h_{i'}}}=\Omega\left(\frac{1}{\text{poly}(n)}\right),\quad\frac{\absolutevalue{h_i}}{\sum_{i^{\prime}j^{\prime}}\absolutevalue{J_{i'j'}}+\sum_{i^{\prime}}\absolutevalue{h_{i'}}}=\Omega\left(\frac{1}{\text{poly}(n)}\right),

(32)

for $J_{ij}\neq 0$ and $h_{i}\neq 0$ . Note that (32) is a sufficient condition for the relative spectral gap of the Ising Hamiltonian to scale as $\Omega\left(\frac{1}{\text{poly}(n)}\right)$ because

\frac{\Delta}{\norm{H}_{2}}\geq\min_{C\neq 0,\;C\in\{\absolutevalue{J_{ij}},\absolutevalue{h_i}\}}\frac{2C}{\sum_{ij}\absolutevalue{J_{ij}}+\sum_{i}\absolutevalue{h_i}}.

(33)

Computing the lower bound of the relative spectral gap (33) takes $\mathcal{O}(n^{2})$ time. In addition, the initial state with uniform amplitudes $\ket{+}^{\otimes n}$ has an overlap probability of $\frac{1}{2^{n}}$ with the ground state. Therefore, by selecting this initial state and a step size scaling as the lower bound in (33) (e.g. see detail (99)), Algorithm 1 can find a ground state of the Ising model satisfying (32), with the probability close to one, and within polynomial time. Formally, we state this observation in Theorem A.11 with an application in Corollary A.12.

5 Conclusion and Discussion

Practical quantum advantages are believed to first emerge from optimization applications. These include ground state preparation for computational science and quantum state preparation for data science. For the past two decades, a large body of research has been developed, but rigorous and efficient general-purpose results remain scarce, despite the strong current interest within the community huang2025vast; preskill2018quantum; aaronson2025future; eisert2025mind. In this paper, we have shown positive results for both state preparation problems. We prove that these problems are solvable with quantum advantages by a quantum optimization algorithm, the stochastic Riemannian gradient flow. The proposed algorithm provides explicit and simple circuit constructions using only Pauli rotations. For the ground state preparation, we show that a class of NP-hard QUBO problems is solvable in polynomial time using both classical and quantum computers (exponential quantum speedups). For the quantum state preparation, we prove that any $n$ -qubit state can be encoded using only polynomial gate complexity to inverse-polynomial precision, when $n$ is larger than a threshold.

Our result can be immediately connected to end-to-end applications. For example, simulating dynamical correlation functions on quantum devices is regarded as a promising direction for quantum many-body physics kokcu2024linear, but requires a subroutine of preparing many-body states such as ground state in the Green’s function. Our result for ground state preparation can be used to provide rigorous circuit constructions for large-scale correlation function calculations, which is of practical interest. For the quantum state preparation, our strategy is the following. For any given state $\ket{\phi}$ , we apply the ground state preparation to the Hamiltonian $H=-\outerproduct{\phi}{\phi}$ , and implement Algorithm 1. This process involves considering the Pauli expansion of the Hamiltonian, and representing the expansion may require $\mathcal{O}(4^{n})$ computational cost. On the other hand, we may be able to exploit a classical randomized technique when estimating the inner product of two states huang2025vast. This would be required when computing the commutator terms in Algorithm 1. We expect that this approach would reduce $\mathcal{O}(4^{n})$ to $\mathcal{O}(2^{n})$ or better. Notably, this already improves upon standard amplitude-encoding methods which require at least $\mathcal{O}(8^{n})$ cost moosa2023linear. Another application to consider is the optimization of higher-order Ising models that capture further interactions and may yield computational gains bybee2023efficient. Beyond QUBO, we expect that our approach achieves quantum advantages for the high-order Ising models. In addition to simulations, learning quantum states is of significant importance in quantum information science. For the recent years, the advance of learning algorithms have been made theoretically and experimentally huang2020predicting; bakshi2025learning; rocchetto2019experimental. In this context, our space advantage result suggests the possibility of substantially more powerful quantum state tomography, compressing an exponential amount of quantum information into only a polynomial sized circuit. This possibility would be important for real-world quantum applications such as quantum linear solvers and quantum ODE/PDE solvers, where a crucial challenge is to extract the classical information of the solution state in polynomial runtime.

There are two major questions for further improving our main result. An immediate question is whether we can extend our result to the non-asymptotic regime. As stated, Theorem 3.1 holds for any Hamiltonian with a $\Omega\left(\frac{1}{\text{poly}(n)}\right)$ relative spectral gap, but the statement is applicable only when the system size is sufficiently large. A crucial factor to determine the system-size threshold is the inverse-polynomial lower bound for the relative spectral gap. For some physical Hamiltonians, the asymptotic result may suffice to capture properties of ground states in the thermodynamic limit, but in many practical simulations in physics and chemistry, which are finite sized, developing an algorithm and a theory for the non-asymptotic regime would be extremely important. This is the same for Theorem 3.3. The second question is whether we can remove the initial condition (3). Lindblad-based algorithms chen2024local; zhan2025rapid avoid this assumption, while their guarantee highly depends on systems. By contrast, Algorithm 1 is generally applicable. We wonder whether these frameworks can be theoretically combined, while preserving their respective advantages. For example, the analysis in malvetti2024randomized considers the randomness arising from a randomized Riemannian gradient descent algorithm, which can be interpreted as the system-bath interaction term in the Lindbladian-based algorithms. On the algorithmic side, a practical direction is the incorporation of algebraic techniques for circuit constructions kokcu2022algebraic. Since the order of Pauli rotations in our algorithm is unimportant, algebraic simplifications may significantly reduce circuit complexity by leading to more compact circuits.

Acknowledgments

This Research was supported by the Korea Institute of Science and Technology Information (KISTI)(No.P25012).

Appendix A Appendix

A.1 Preliminaries

We briefly review several standard notions from a theory of stochastic processes and martingale williams1991probability; durrett2019probability Let $(\Omega,\mathcal{F},\mathbb{P})$ be a probability space and $\mathbb{N}_{0}:=\mathbb{N}\cup\{0\}$ . A filtration is a nondecreasing family of $\sigma$ -algebras $\{\mathcal{F}_{t}\}_{t\in\mathbb{N}_{0}}$ with $\mathcal{F}_{s}\subseteq\mathcal{F}_{t}\subseteq\mathcal{F}$ for $s\leq t$ . A stochastic process $\{X_{t}\}_{t\in\mathbb{N}_{0}}$ is adapted to $\mathcal{F}_{t}$ if $X_{t}$ is $\mathcal{F}_{t}$ -measurable for all $t\in\mathbb{N}_{0}$ .

Definition A.1.

Let $\{X_{t}\}_{t\in\mathbb{N}_{0}}$ be an integrable, adapted process with respect to a filtration $\{\mathcal{F}_{t}\}$ .

1.

$X$ is said to be a martingale with respect to $\{\mathcal{F}_{t}\}$ if

$\mathbb{E}[X_{t}|\mathcal{F}_{s}]=X_{s},\quad\forall s\leq t.$ (34)
2.

$X$ is said to be a submartingale with respect to $\{\mathcal{F}_{t}\}$ if

$\mathbb{E}[X_{t}|\mathcal{F}_{s}]\geq X_{s},\quad\forall s\leq t.$ (35)
3.

$X$ is said to be a supermartingale with respect to $\{\mathcal{F}_{t}\}$ if

$\mathbb{E}[X_{t}|\mathcal{F}_{s}]\leq X_{s},\quad\forall s\leq t.$ (36)

Definition A.2 (Stopping Time).

A random variable $\tau:\Omega\to[0,\infty]$ is called a stopping time with respect to a filtration $\{\mathcal{F}_{t}\}$ if

\{\tau\leq t\}\in\mathcal{F}_{t},\quad t\in\mathbb{N}_{0}.

(37)

Definition A.3 (Stopped Process).

Given a stochastic process $\{X_{t}\}_{t\in\mathbb{N}_{0}}$ adapted to $\mathcal{F}_{t}$ and a stopping time $\tau$ with respect to $\mathcal{F}_{t}$ , the stopped process $X_{t\wedge\tau}:=X_{\min\{t,\tau\}}$ is defined by

X_{t\wedge\tau}=\begin{cases}X_{t},&t\leq\tau,\\ X_{\tau},&t>\tau.\end{cases}

(38)

Lemma A.4 (Doob’s Optional Stopping Theorem).

Let $\{X_{t}\}_{t\in\mathbb{N}_{0}}$ be an adapted stochastic process and $\tau$ a stopping time, both with respect to a filtration $\mathcal{F}_{t}$ . Assume that one of the following conditions holds:

1.

The stopping time $\tau$ is almost surely bounded, i.e., there exists a constant $c\in\mathbb{N}$ such that

$\mathbb{P}(\tau\leq c)=1.$ (39)
2.

The stopping time $\tau$ is integrable and the conditional expectations of the absolute value of the increments are almost surely bounded, i.e., $\mathbb{E}[\tau]<\infty$ and there exists a constant $c$ such that

$\mathbb{E}\left[\absolutevalue{X_{t+1} - X_{t}}|\mathcal{F}_{t}\right]\leq c$ (40)

almost surely on the event $\{\tau>t\}$ for all $t\in\mathbb{N}_{0}$ .
3.

There exists a constant $c$ such that

$|X_{t\wedge\tau}|\leq c$

almost surely for all $t\in\mathbb{N}_{0}$ .

Then $X_{\tau}$ is an almost surely well-defined random variable. Additionally,

1.

if $X_{t}$ is a martingale, then $\mathbb{E}[X_{\tau}]=\mathbb{E}[X_{0}]$ .
2.

if $X_{t}$ is a submartingale, then $\mathbb{E}[X_{\tau}]\geq\mathbb{E}[X_{0}]$ .
3.

if $X_{t}$ is a supermartingale, then $\mathbb{E}[X_{\tau}]\leq\mathbb{E}[X_{0}]$ .

Proof.

See (williams1991probability, Theorem 10.10). ∎

Lemma A.5 (Reverse Markov Inequality).

Let $X$ be a nonnegative random variable and $X\leq b$ holds almost surely for some $b>0$ . Then

\mathbb{P}(X\geq a)\geq\frac{\mathbb{E}[X]-a}{b-a},\quad 0\leq a<b.

(41)

Proof.

By the assumption, observe that

\begin{split}\mathbb{E}[X]&=\mathbb{E}\left[X\mathds{1}_{\{X<a\}}\right]+\mathbb{E}\left[X\mathds{I}_{\{X\geq a\}}\right]\leq a\mathbb{E}\left[\mathds{1}_{\{X<a\}}\right]+b\mathbb{E}\left[\mathds{1}_{\{X\geq a\}}\right]\\ &=a\mathbb{P}(X<a)+b\mathbb{P}(X\geq a)=(b-a)\mathbb{P}(X\geq a)+a.\end{split}

(42)

Thus, we get the desired result. The lemma is proved. ∎

A.2 Proof of Lemma 3.5

In this section, we prove Lemma 3.5 in Section 3.3.1 to analyze systematic errors that are involved in the stochastic Riemannian gradient flow (Algorithm 1). We firstly decompose $U_{t+1}$ as a single exponential form using the first-order Trotter formula,

U_{t+1}=\prod_{j=1}^{J}\exp(c_{t}^{(j)}\delta tP_{t}^{(j)})U_{t}=\left(\exp\left(\delta t\sum_{j=1}^{J}c_{t}^{(j)}P_{t}^{(j)}\right)+E_{t}^{(1)}\right)U_{t},

(43)

where the first-order Trotter error $E_{t}^{(1)}$ childs2021theory is dominated by

\|E_{t}^{(1)}\|_{2}\leq\frac{(\delta t)^{2}}{2}\sum_{j_{1}=1}^{J}\norm{\left[\sum_{j_2=j_1+1}^Jc_{t}^{(j_2)}P_{t}^{(j_2)},c_{t}^{(j_1)}P_{t}^{(j_1)}\right]}_{2}.

(44)

Second, we consider the Taylor series of the exponential term in (43),

\begin{split}U_{t+1}=\left(\exp\left(\delta t\sum_{j=1}^{J}c_{t}^{(j)}P_{t}^{(j)}\right)+E_{t}^{(1)}\right)U_{t}=\left(I+\delta t\sum_{j=1}^{J}c_{t}^{(j)}P_{t}^{(j)}+E_{t}^{(1)}+E_{t}^{(2)}\right)U_{t},\end{split}

(45)

where the Taylor-series approximation error $E_{t}^{(2)}$ is defined as

\begin{split}E_{t}^{(2)}=\sum_{j\geq 2}\frac{1}{j!}\left(\delta t\sum_{j=1}^{J}c_{t}^{(j)}P_{t}^{(j)}\right)^{j}.\end{split}

(46)

Lastly, we decompose (45) by estimating the commutator term $\mathcal{M}_{t}:=[U_{t}\outerproduct{\psi_1}{\psi_1}U_{t}^{\dagger},H]$ in Algorithm 1,

U_{t+1}=\left(I+\delta t\sum_{j=1}^{J}c_{t}^{(j)}P_{t}^{(j)}+E_{t}^{(1)}+E_{t}^{(2)}\right)U_{t}=\left(I+\delta t\mathcal{M}_{t}+E_{t}^{(1)}+E_{t}^{(2)}+E_{t}^{(3)}\right)U_{t},

(47)

where the estimation error $E_{t}^{(3)}$ accounts for the sampling of Pauli operators as follows

E_{t}^{(3)}=\delta t\left(\sum_{j=1}^{J}c_{t}^{(j)}P_{t}^{(j)}-\mathcal{M}_{t}\right).

(48)

To control the coefficients $c_{t}^{(j)}$ in $E_{t}^{(1)}$ , $E_{t}^{(2)}$ , and $E_{t}^{(3)}$ , we prove the following inequality.

Lemma A.6.

Recall $c_{t}^{(j)}=\frac{1}{2^{n}}\bra{\psi_{1}}U_{t}^{\dagger}[H,P_{t}^{(j)}]U_{t}\ket{\psi_{1}}$ in Algorithm 1. It holds that

\sum_{j=1}^{J}\absolutevalue{c_{t}^{(j)}}\leq\frac{J\norm{H}_{2}}{2^{n-1}}.

(49)

Proof.

Since $\norm{P}_{2}=1$ for any Pauli operator $P$ ,

|\bra{\psi_{1}}U_{t}^{\dagger}[H,P_{t}^{(j)}]U_{t}\ket{\psi_{1}}|\leq 2\norm{H}_{2},

(50)

by the triangle inequality. Therefore,

\sum_{j=1}^{J}\absolutevalue{c_{t}^{(j)}}=\frac{1}{2^{n}}\sum_{j=1}^{J}\absolutevalue{\bra{\psi_1}U_t^\dagger[H,P_{t}^{(j)}]U_t\ket{\psi_1}}U_{t}^{\dagger}[H,P_{t}^{(j)}]U_{t}\ket{\psi_{1}}\leq\frac{J\norm{H}_{2}}{2^{n-1}}.

(51)

The lemma is proved. ∎

Proof of Lemma 3.5.

We first derive the upper bounds for spectral norm of errors $E_{t}^{(1)}$ , $E_{t}^{(2)}$ , and $E_{t}^{(3)}$ in (20). To get the upper bound for $\|E_{t}^{(1)}\|_{2}$ , by (44) and the triangle inequality, observe that

	$\displaystyle\\|E_{t}^{(1)}\\|_{2}$	$\displaystyle\leq\frac{(\delta t)^{2}}{2}\sum_{j_{1}=1}^{J}\norm{\left[\sum_{j_2=j_1+1}^Jc_{t}^{(j_2)}P_{t}^{(j_2)},c_{t}^{(j_1)}P_{t}^{(j_1)}\right]}_{2}$		(52)
		$\displaystyle\leq\frac{(\delta t)^{2}}{2}\sum_{j_{1}=1}^{J}\absolutevalue{c_{t}^{(j_1)}}\left(\sum_{j_{2}=j_{1}+1}^{J}\absolutevalue{c_{t}^{(j_2)}}\norm{[P_{t}^{(j_2)},P_{t}^{(j_1)}]}_{2}\right).$		(53)

Since $\norm{[P,Q]}_{2}\leq 2$ for any Pauli operators $P$ and $Q$ ,

\displaystyle\frac{(\delta t)^{2}}{2}\sum_{j_{1}=1}^{J}\absolutevalue{c_{t}^{(j_1)}}\left(\sum_{j_{2}=j_{1}+1}^{J}\absolutevalue{c_{t}^{(j_2)}}\norm{[P_{t}^{(j_2)},P_{t}^{(j_1)}]}_{2}\right)\leq(\delta t)^{2}\sum_{j_{1}=1}^{J}\absolutevalue{c_{t}^{(j_1)}}\left(\sum_{j_{2}=j_{1}+1}^{J}\absolutevalue{c_{t}^{(j_2)}}\right).

(54)

Thus, Lemma A.6 implies

\displaystyle(\delta t)^{2}\sum_{j_{1}=1}^{J}\absolutevalue{c_{t}^{(j_1)}}\left(\sum_{j_{2}=j_{1}+1}^{J}\absolutevalue{c_{t}^{(j_2)}}\right)\leq(\delta t)^{2}\sum_{j_{1}=1}^{J}\absolutevalue{c_{t}^{(j_1)}}\left(\frac{J\norm{H}_{2}}{2^{n-1}}\right)\leq\left(\frac{J\norm{H}_{2}}{2^{n-1}}\right)^{2}(\delta t)^{2}.

(55)

Next, we derive the upper bound for $E_{t}^{(2)}$ . By the triangle inequality and Lemma A.6 again,

\norm{\delta t\sum_{j=1}^Jc_{t}^{(j)}P_{t}^{(j)}}_{2}\leq\delta t\sum_{j=1}^{J}\absolutevalue{c_{t}^{(j)}}\leq\frac{J\norm{H}_{2}}{2^{n-1}}\delta t.

(56)

Due to the inequality $\norm{e^A - I - A}_{2}\leq\frac{e^{\norm{A}_{2}}}{2}\norm{A}_{2}^{2}$ for any matrix $A$ , we get

	$\displaystyle\\|E_{t}^{(2)}\\|_{2}$	$\displaystyle\leq\frac{1}{2}\exp\left(\norm{\delta t\sum_{j=1}^Jc_{t}^{(j)}P_{t}^{(j)}}_{2}\right)\norm{\delta t\sum_{j=1}^Jc_{t}^{(j)}P_{t}^{(j)}}_{2}^{2}$		(57)
		$\displaystyle\leq\frac{1}{2}\exp\left(\frac{J\norm{H}_{2}}{2^{n-1}}\delta t\right)\left(\frac{J\norm{H}_{2}}{2^{n-1}}\right)^{2}(\delta t)^{2}.$		(58)

Lastly, to derive the upper bound for $E_{t}^{(3)}$ , observe that

\Bigg\|\sum_{j=1}^{J}c_{t}^{(j)}P_{t}^{(j)}-\mathcal{M}_{t}\Bigg\|_{2}=\Bigg\|\sum_{P\not\in\{P_{t}^{(j)}\}_{j=1}^{J}}\frac{1}{2^{n}}\tr\left(\mathcal{M}_{t}P\right)P\Bigg\|_{2}\leq\|\mathcal{M}_{t}\|_{F}

(59)

By the triangle inequality,

\norm{\mathcal{M}_{t}}_{F}\leq 2\|U_{t}\outerproduct{\psi_1}{\psi_1}U_{t}^{\dagger}H\|_{F}=2\bra{\psi_{1}}U_{t}^{\dagger}H^{2}U_{t}\ket{\psi_{1}}\leq 2\norm{H}_{2}^{2}

(60)

Therefore, we obtain the following results in (20). Finally, we derive the conditional expectation of $E_{t}^{(3)}$ with respect to $\mathcal{F}_{t}$ in (20)

\displaystyle\mathbb{E}\left[E_{t}^{(3)}|\mathcal{F}_{t}\right]=\delta t\left(\frac{J}{4^{n}}-1\right)\mathcal{M}_{t}.

(61)

According to the sampling of Pauli operators in Remark 3.4, observe that

\mathbb{E}\left[\sum_{j=1}^{J}c_{t}^{(j)}P_{t}^{(j)}\Bigg|\mathcal{F}_{t}\right]=\frac{{4^{k}-1\choose J-1}}{{4^{k}\choose J}}\frac{1}{4^{n-k}}\mathcal{M}_{t}=\frac{J}{4^{n}}\mathcal{M}_{t}.

(62)

This implies

\mathbb{E}\left[E_{t}^{(3)}|\mathcal{F}_{t}\right]=\mathbb{E}\left[\delta t\left(\sum_{j=1}^{J}c_{t}^{(j)}P_{t}^{(j)}-\mathcal{M}_{t}\right)\Bigg|\mathcal{F}_{t}\right]=\delta t\left(\frac{J}{4^{n}}-1\right)\mathcal{M}_{t}

(63)

Consequently, we obtain (20) so Lemma 3.5 is proved. ∎

A.3 Properties of Overlap Process

Since the unitary matrix $U_{t}$ constructed by Algorithm 1 involves randomness, we employ a theory of stochastic processes to analyze properties of overlap $\absolutevalue{\bra{\lambda_1}U_t\ket{\psi_1}}U_{t}\ket{\psi_{1}}^{2}$ of the state with the ground state at each iteration step $t$ in Algorithm 1.

Let $F_{t}:=\absolutevalue{\bra{\lambda_1}U_t\ket{\psi_1}}U_{t}\ket{\psi_{1}}^{2}$ denote the overlap process and define $\mathcal{F}_{t}:=\sigma(F_{s}:0\leq s\leq t)$ . Hence $F_{t}$ is an $\mathcal{F}_{t}$ -adapted stochastic process. By (47),

\displaystyle F_{t+1}=\absolutevalue{\bra{\lambda_1}U_{t+1}\ket{\psi_1}}U_{t+1}\ket{\psi_{1}}^{2}=\absolutevalue{\bra{\lambda_1}\left(I + \delta t\mathcal{M}_{t} + E_{t}^{(1)} +E_{t}^{(2)} + E_{t}^{(3)} \right)U_t\ket{\psi_{1}}}\left(I+\delta t\mathcal{M}_{t}+E_{t}^{(1)}+E_{t}^{(2)}+E_{t}^{(3)}\right)U_{t}\ket{\psi_{1}}^{2}=Q_{1}+Q_{2}+Q_{3},

(64)

where

\begin{split}Q_{1}&:=\absolutevalue{\bra{\lambda_1}\left(I + \delta t\mathcal{M}_{t}+E_{t}^{(3)}\right)U_t\ket{\psi_{1}}}\left(I+\delta t\mathcal{M}_{t}+E_{t}^{(3)}\right)U_{t}\ket{\psi_{1}}^{2},\\ Q_{2}&:=2\Re{\bra{\lambda_1}\left(I + \delta t\mathcal{M}_{t}+E_{t}^{(3)}\right)U_t\ketbra{\psi_{1}}\left(E_{t}^{(1)} +E_{t}^{(2)}\right)U_t\ket{\lambda_1}}\left(I+\delta t\mathcal{M}_{t}+E_{t}^{(3)}\right)U_{t}\outerproduct{\psi_{1}}{\psi_{1}}\left(E_{t}^{(1)}+E_{t}^{(2)}\right)U_{t}\ket{\lambda_{1}},\\ Q_{3}&:=\absolutevalue{\bra{\lambda_1}\left(E_{t}^{(1)} +E_{t}^{(2)}\right)U_t\ket{\psi_{1}}}\left(E_{t}^{(1)}+E_{t}^{(2)}\right)U_{t}\ket{\psi_{1}}^{2}.\end{split}

(65)

Estimation of $Q_{1}$ .

We first estimate the quantity $Q_{1}$ . Observe that

	$\displaystyle Q_{1}$	$\displaystyle=\absolutevalue{\bra{\lambda_1}(I+\delta t \mathcal{M}_{t})U_t+E_{t}^{(3)} U_t\ket{\psi_1}}(I+\delta t\mathcal{M}_{t})U_{t}+E_{t}^{(3)}U_{t}\ket{\psi_{1}}^{2}$		(66)
		$\displaystyle\geq\absolutevalue{\bra{\lambda_1}(I+\delta t\mathcal{M}_{t})U_t\ket{\psi_1}}(I+\delta t\mathcal{M}_{t})U_{t}\ket{\psi_{1}}^{2}+2\Re{\bra{\lambda_1}E_{t}^{(3)}U_t\ketbra{\psi_1}U_t^\dagger(I+\delta t\mathcal{M}_t^\dagger)\ket{\lambda_1}}E_{t}^{(3)}U_{t}\outerproduct{\psi_1}{\psi_1}U_{t}^{\dagger}(I+\delta t\mathcal{M}_{t}^{\dagger})\ket{\lambda_{1}}$		(67)

Let us write $\mathcal{D}_{t}=\bra{\psi}U_{t}^{\dagger}HU_{t}\ket{\psi}-\lambda_{1}$ . Then observe that

\bra{\lambda_{1}}\mathcal{M}_{t}U_{t}\ket{\psi_{1}}=\bra{\lambda_{1}}\left[U_{t}\outerproduct{\psi_1}{\psi_1}U_{t}^{\dagger},H\right]U_{t}\ket{\psi_{1}}=\mathcal{D}_{t}\bra{\lambda_{1}}U_{t}\ket{\psi_{1}}.

(68)

Note that

\mathcal{D}_{t}=\sum_{i=1}^{2^{n}}\lambda_{i}\absolutevalue{\bra{\lambda_i}U_t\ket{\psi_1}}U_{t}\ket{\psi_{1}}^{2}-\lambda_{1}\geq\lambda_{1}F_{t}+\lambda_{2}(1-F_{t})-\lambda_{1}\geq(1-F_{t})\Delta,

(69)

where $\Delta:=\lambda_{2}-\lambda_{1}$ denotes the spectral gap so that $\mathcal{D}_{t}\geq 0$ . By (68),

\absolutevalue{\bra{\lambda_1}(I+\delta t\mathcal{M}_{t})U_t\ket{\psi_1}}(I+\delta t\mathcal{M}_{t})U_{t}\ket{\psi_{1}}^{2}=\left(1+\delta t\mathcal{D}_{t}\right)^{2}F_{t}.

(70)

and additionally by Lemma 3.5 (see Eq. 63),

\begin{split}\mathbb{E}&\left[\bra{\lambda_{1}}E_{t}^{(3)}U_{t}\outerproduct{\psi_1}{\psi_1}U_{t}^{\dagger}(I+\delta t\mathcal{M}_{t}^{\dagger})\ket{\lambda_{1}}\Big|\mathcal{F}_{t}\right]\\ &=\delta t\left(\frac{J}{4^{n}}-1\right)\bra{\lambda_{1}}\mathcal{M}_{t}U_{t}\outerproduct{\psi_1}{\psi_1}U_{t}^{\dagger}(I+\delta t\mathcal{M}_{t}^{\dagger})\ket{\lambda_{1}}\\ &=\delta t\left(\frac{J}{4^{n}}-1\right)\mathcal{D}_{t}\left(1+\delta t\mathcal{D}_{t}\right)F_{t}\geq-\delta t\mathcal{D}_{t}\left(1+\delta t\mathcal{D}_{t}\right)F_{t}\end{split}.

(71)

Combining (69), (70), and (71), we get

\begin{split}\mathbb{E}[Q_{1}|\mathcal{F}_{t}]\geq\left(\left(1+\delta t\mathcal{D}_{t}\right)^{2}-2\delta t\mathcal{D}_{t}\left(1+\delta t\mathcal{D}_{t}\right)\right)F_{t}=\left(1+\delta t\mathcal{D}_{t}\right)F_{t}\geq\left(1+\delta t(1-F_{t})\Delta\right)F_{t}.\end{split}

(72)

On the other hand, by the definition of $E_{t}^{(3)}$ and the triangle inequality,

	$\displaystyle Q_{1}$	$\displaystyle=\absolutevalue{\bra{\lambda_1}(I+\delta t\sum_{j=1}^Jc_{j,t}P_j^{(t)})U_t\ket{\psi_1}}(I+\delta t\sum_{j=1}^{J}c_{j,t}P_{j}^{(t)})U_{t}\ket{\psi_{1}}^{2}$		(73)
		$\displaystyle\leq\left(\Big\|\bra{\lambda_{1}}U_{t}\ket{\psi_{1}}\Big\|+\delta t\Big\|\bra{\lambda_{1}}\sum_{j=1}^{J}c_{j,t}P_{j}^{(t)}U_{t}\ket{\psi_{1}}\Big\|\right)^{2}\leq\left(\sqrt{F_{t}}+\delta t\sum_{j=1}^{J}\absolutevalue{c_{j,t}}\right)^{2},$		(74)

where the last inequality holds since $\norm{P}_{2}=1$ for any Pauli operators $P$ . Then by Lemma A.6,

\displaystyle\left(\sqrt{F_{t}}+\delta t\sum_{j=1}^{J}\absolutevalue{c_{t}^{(j)}}\right)^{2}\leq\left(\sqrt{F_{t}}+\frac{J\norm{H}_{2}}{2^{n-1}\delta t}\right)^{2}=F_{t}+\frac{J\norm{H}_{2}}{2^{n-2}}\sqrt{F_{t}}\delta t+\frac{J^{2}\norm{H}_{2}^{2}}{2^{2n-2}}(\delta t)^{2}.

(75)

In summary, we obtain the estimation of $Q_{1}$ as follows

\mathbb{E}[Q_{1}|\mathcal{F}_{t}]\geq\left(1+\delta t(1-F_{t})\Delta\right)F_{t},\quad Q_{1}\leq F_{t}+\frac{J\norm{H}_{2}}{2^{n-2}}\sqrt{F_{t}}\delta t+\frac{J^{2}\norm{H}_{2}^{2}}{2^{2n-2}}(\delta t)^{2}.

(76)

Estimation of $Q_{2}$ and $Q_{3}$

By the definition of $E_{t}^{(3)}$ and the triangle inequality, similar to (75),

	$\displaystyle\absolutevalue{\bra{\lambda_1}\left(I + \delta t\mathcal{M}_{t} + E_{t}^{(3)}\right)U_t\ket{\psi_1}}\left(I+\delta t\mathcal{M}_{t}+E_{t}^{(3)}\right)U_{t}\ket{\psi_{1}}$	$\displaystyle=\Big\|\bra{\lambda_{1}}\Big(I+\delta t\sum_{j=1}^{J}c_{t}^{(j)}P_{t}^{(j)}\Big)U_{t}\ket{\psi_{1}}\Big\|$		(77)
		$\displaystyle\leq\sqrt{F_{t}}+\delta t\sum_{j=1}^{J}\absolutevalue{c_{t}^{(j)}}\leq 1+\frac{J\norm{H}_{2}}{2^{n-1}}\delta t.$		(78)

Applying Lemma 3.5, we obtain the estimation of $Q_{2}$ ,

\begin{split}|Q_{2}|&\leq 2\absolutevalue{\bra{\lambda_1}\left(I + \delta t \mathcal{M}_{t}+E_{t}^{(3)}\right)U_t\ket{\psi_1}}\left(I+\delta t\mathcal{M}_{t}+E_{t}^{(3)}\right)U_{t}\ket{\psi_{1}}\cdot\absolutevalue{\bra{\psi_1}\left(E_{t}^{(1)} +E_{t}^{(2)}\right)U_t\ket{\lambda_1}}\left(E_{t}^{(1)}+E_{t}^{(2)}\right)U_{t}\ket{\lambda_{1}}\\ &\leq 2\left(1+\frac{J\norm{H}_{2}}{2^{n-1}}\delta t\right)\left(1+\frac{1}{2}\exp\left(\frac{J\norm{H}_{2}}{2^{n-1}}\delta t\right)\right)\left(\frac{J\norm{H}_{2}}{2^{n-1}}\right)^{2}(\delta t)^{2}.\end{split}

(79)

Similarly, it follows that

	$\displaystyle Q_{3}$	$\displaystyle\leq\left(\absolutevalue{\bra{\lambda_1}E_{t}^{(1)} U_t\ket{\psi_1}}E_{t}^{(1)}U_{t}\ket{\psi_{1}}+\absolutevalue{\bra{\lambda_1}E_{t}^{(2)}U_t\ket{\psi_1}}E_{t}^{(2)}U_{t}\ket{\psi_{1}}\right)^{2}$		(80)
		$\displaystyle\leq\left(1+\frac{1}{2}\exp\left(\frac{J\norm{H}_{2}}{2^{n-1}}\delta t\right)\right)^{2}\left(\frac{J\norm{H}_{2}}{2^{n-1}}\right)^{4}(\delta t)^{4}.$		(81)

In summary, we obtain the upper bound of $Q_{2}$ and $Q_{3}$ as follows

|Q_{2}|\leq C_{2}\left(\frac{\delta t}{2^{n}}\right)^{2},\quad Q_{3}\leq C_{3}\left(\frac{\delta t}{2^{n}}\right)^{4},

(82)

where $C_{2}$ and $C_{3}$ depend on $n$ , $J$ , $\norm{H}_{2}$ , and $\delta t$ which are defined by

\displaystyle\begin{split}C_{2}&:=8J^{2}\norm{H}_{2}^{2}\left(1+2J\norm{H}_{2}\frac{\delta t}{2^{n}}\right)\left(1+\frac{1}{2}\exp\left(2J\norm{H}_{2}\frac{\delta t}{2^{n}}\right)\right)\\ C_{3}&:=16J^{4}\norm{H}_{2}^{4}\left(1+\frac{1}{2}\exp\left(2J\norm{H}_{2}\frac{\delta t}{2^{n}}\right)\right)^{2}.\end{split}

(83)

Having (83) in mind, we set

\displaystyle\begin{split}C_{2}^{\star}&:=8J^{2}\norm{H}_{2}^{2}\left(1+2J\norm{H}_{2}\right)\left(1+\frac{1}{2}\exp\left(2J\norm{H}_{2}\right)\right),\\ C_{3}^{\star}&:=16J^{4}\norm{H}_{2}^{4}\left(1+\frac{1}{2}\exp\left(2J\norm{H}_{2}\right)\right)^{2}.\end{split}

(84)

Based on the estimations of $Q_{1}$ , $Q_{2}$ , and $Q_{3}$ , we prove the following property of the overlap process.

Theorem A.7.

For a given $n\in\mathbb{N}$ , it holds that on the event $\{\delta t\leq\frac{4^{n}\Delta(1-F_{t})F_{t}}{2C_{2}^{\star}}\wedge 2^{n}\}$ ,

\mathbb{E}[F_{t+1}|\mathcal{F}_{t}]\geq\left(1+\frac{\delta t}{2}(1-F_{t})\Delta\right)F_{t}.

(85)

Furthermore, it holds that for any $\delta t>0$ ,

\displaystyle\sqrt{F_{t+1}}\leq\sqrt{F_{t}}+\frac{\delta t}{2^{n}}\sqrt{4J^{2}\norm{H}_{2}^{2}+C_{2}+C_{3}\left(\frac{\delta t}{2^{n}}\right)^{2}}.

(86)

Proof.

Fix $n\in\mathbb{N}$ . We first prove (85). Observe that there hold $C_{2}\leq C_{2}^{\star}$ and $C_{3}\leq C_{3}^{\star}$ if $\delta t\leq 2^{n}$ . Additionally, if $\delta t\leq\frac{4^{n}\Delta(1-F_{t})F_{t}}{2C_{2}^{\star}}$ ,

\displaystyle C_{2}\left(\frac{\delta t}{2^{n}}\right)^{2}\leq C_{2}\delta t\left(\frac{\delta t}{4^{n}}\right)\leq\frac{C_{2}}{C_{2}^{\star}}\frac{\delta t}{2}\Delta(1-F_{t})F_{t}\leq\frac{\delta t}{2}\Delta(1-F_{t})F_{t}.

(87)

Due to (64), (76), and (82), on the event $\{\delta t\leq\frac{4^{n}\Delta(1-F_{t})F_{t}}{2C_{2}^{\star}}\wedge 2^{n}\}\in\mathcal{F}_{t}$ ,

\displaystyle\mathbb{E}[F_{t+1}|\mathcal{F}_{t}]=\mathbb{E}[Q_{1}+Q_{2}+Q_{3}|\mathcal{F}_{t}]

\displaystyle\geq\left(1+\delta t(1-F_{t})\Delta\right)F_{t}-C_{2}\left(\frac{\delta t}{2^{n}}\right)^{2}\geq\left(1+\frac{\delta t}{2}(1-F_{t})\Delta\right)F_{t}.

(88)

Hence (85) is proved. Again, due to (64), (76), and (82), observe that

		$\displaystyle F_{t+1}=Q_{1}+Q_{2}+Q_{3}$		(89)
		$\displaystyle\leq F_{t}+4J\norm{H}_{2}\sqrt{F_{t}}\left(\frac{\delta t}{2^{n}}\right)+4J^{2}\norm{H}_{2}^{2}\left(\frac{\delta t}{2^{n}}\right)^{2}+C_{2}\left(\frac{\delta t}{2^{n}}\right)^{2}+C_{3}\left(\frac{\delta t}{2^{n}}\right)^{4}$		(90)
		$\displaystyle\leq F_{t}+2\left(\frac{\delta t}{2^{n}}\right)\sqrt{F_{t}}\sqrt{4J^{2}\norm{H}_{2}^{2}+C_{2}+C_{3}\left(\frac{\delta t}{2^{n}}\right)^{2}}+\left(\frac{\delta t}{2^{n}}\right)^{2}\left(4J^{2}\norm{H}_{2}^{2}+C_{2}+C_{3}\left(\frac{\delta t}{2^{n}}\right)^{2}\right)$		(91)
		$\displaystyle=\left(\sqrt{F_{t}}+\frac{\delta t}{2^{n}}\sqrt{4J^{2}\norm{H}_{2}^{2}+C_{2}+C_{3}\left(\frac{\delta t}{2^{n}}\right)^{2}}\right)^{2}.$		(92)

Therefore, we get (86). The theorem is proved. ∎

Remark A.8.

Applying (86) repeatedly, for any $0<\delta t\leq 2^{n}$ , we get

\displaystyle\sqrt{F_{t+1}}\leq\sqrt{F_{1}}+t\cdot\frac{\delta t}{2^{n}}C_{4}^{\star},\quad C_{4}^{\star}:=\sqrt{4J^{2}\norm{H}_{2}^{2}+C_{2}^{\star}+C_{3}^{\star}}.

(93)

A.4 Proof of Main Results

In this section, without the loss of generality, we can set $\norm{H}_{2}=1$ and replace $\Delta$ by $\Delta/\norm{H}_{2}$ through normalizing the Hamiltonian $H$ by its spectral norm. Recall (83) and (84) and the above normalization affects the parameters $C_{1},C_{2},C_{1}^{\star}$ , and $C_{2}^{\star}$ in Theorem A.7. Precisely,

\displaystyle\begin{split}&C_{2}^{\star}=8J^{2}\left(1+2J\right)\left(1+\frac{1}{2}\exp\left(2J\right)\right)\geq 64,\quad C_{3}^{\star}=16J^{4}\left(1+\frac{1}{2}\exp\left(2J\right)\right)^{2}\geq 256,\\ &C_{4}^{\star}=\sqrt{4J^{2}+C_{2}^{\star}+C_{3}^{\star}}\geq 18\quad J\in\mathbb{N}.\end{split}

(94)

Proof of Theorem 3.1.

Due to the assumption (2), there exists a constant $C_{\Delta}>0$ and a polynomial function $\mathcal{P}_{k}=\mathcal{P}_{k}(n)$ with a degree $k$ satisfying

\displaystyle\frac{\Delta}{\norm{H}_{2}}\geq\frac{C_{\Delta}}{\mathcal{P}_{k}}.

(95)

Fix $n\geq N_{0}$ where $N_{0}\in\mathbb{N}$ is specified later. We also set $\epsilon_{f}>0$ satisfying

\displaystyle\epsilon_{f}\geq\frac{C_{f}}{\mathcal{P}_{k}}\geq\frac{2}{2^{n}+1},

(96)

with a constant $C_{f}>0$ . Without the loss of generality, we focus on $\epsilon_{f}\leq\epsilon<\min\{\frac{1}{2},1-\sqrt{F_{1}}\}$ for a given $F_{1}\geq\frac{1}{2^{n}}$ . Set $\epsilon_{\text{tol}}=\frac{1}{2^{n+1}}(1-\frac{\epsilon}{2})$ so it implies $F_{1}\geq 2\epsilon_{\text{tol}}$ and

\displaystyle C_{\epsilon}:=\frac{2^{n}(1-\epsilon_{\text{tol}})\epsilon_{\text{tol}}}{2C_{2}^{\star}}=\frac{(1-\epsilon_{\text{tol}})(1-\frac{\epsilon}{2})}{2C_{2}^{\star}},\quad\frac{9}{32C_{2}^{\star}}\leq C_{\epsilon}\leq\frac{1}{128}.

(97)

Let us write $C_{\eta}:=2C_{\epsilon}C_{4}^{\star}$ . We can choose a tunable parameter $C>0$ satisfying the following,

\displaystyle\frac{C_{\ell}}{\mathcal{P}_{k}}\leq C\leq\min\left\{\frac{\epsilon}{32C_{2}^{\star}},\frac{C_{f}}{2C_{\eta}C_{\Delta}},1\right\},\quad\frac{C\Delta}{\norm{H}_{2}}<\min\left\{\frac{C_{f}}{2C_{\eta}\mathcal{P}_{k}},1\right\},

(98)

for some constant $C_{\ell}>0$ . Let us write $\mathcal{T}:=\frac{\norm{H}_{2}}{C\Delta}$ and define $\delta t:=2^{n}\frac{C_{\epsilon}}{\mathcal{T}}$ . Then

\displaystyle\delta t=2^{n}\frac{C_{\epsilon}}{\mathcal{T}}\leq\frac{2^{n}}{128\mathcal{T}}\leq\frac{2^{n}}{128}.

(99)

Let $T:=\lfloor 2\mathcal{T}\cdot\frac{1-\frac{\epsilon}{2}-\sqrt{F}_{1}}{C_{\eta}}\rfloor+1$ . Note that $1-\frac{\epsilon}{2}-\sqrt{F_{1}}>\frac{1-\sqrt{F}_{1}}{2}$ because $\epsilon<\min\{\frac{1}{2},1-\sqrt{F_{1}}\}$ . Therefore, $T=\Theta(\mathcal{T})$ . Furthermore, by Remark A.8, it holds that for any $t\leq T+1$ ,

\displaystyle F_{t}\leq\sqrt{F}_{t}\leq\sqrt{F_{1}}+(t-1)\cdot\frac{\delta t}{2^{n}}C_{4}^{\star}\leq\sqrt{F}_{1}+T\cdot\frac{C_{\eta}}{2\mathcal{T}}\leq 1-\frac{\epsilon}{2}+\frac{C_{\eta}}{2\mathcal{T}}.

(100)

By (98), $\frac{1}{\mathcal{T}}<\frac{\epsilon}{2C_{\eta}}$ holds hence we obtain

\displaystyle 1-F_{t}\geq\frac{\epsilon}{2}-\frac{C_{\eta}}{2\mathcal{T}}>\frac{\epsilon}{4}.

(101)

Recall $\epsilon_{f}\geq\frac{2}{2^{n}+1}$ so that $1-\frac{\epsilon}{4}\leq 1-\epsilon_{\text{tol}}$ . By (101), $F_{t}\leq 1-\epsilon_{\text{tol}}$ holds for any $t\leq T+1$ . Let us consider an event $\{F_{t}\geq\epsilon_{\text{tol}}\}\in\mathcal{F}_{t}$ . On this event, we get $\epsilon_{\text{tol}}\leq F_{t}\leq 1-\epsilon_{\text{tol}}$ so that $(1-\epsilon_{\text{tol}})\epsilon_{\text{tol}}\leq(1-F_{t})F_{t}$ . Recall (97) and observe that

\displaystyle\delta t=2^{n}\cdot\frac{2^{n}(1-\epsilon_{\text{tol}})\epsilon_{\text{tol}}}{2\mathcal{T}C_{2}^{\star}}\leq\frac{4^{n}C\Delta(1-F_{t})F_{t}}{2\norm{H}_{2}C_{2}^{\star}}\leq\frac{4^{n}\Delta(1-F_{t})F_{t}}{2\norm{H}_{2}C_{2}^{\star}}.

(102)

Therefore, on the event $\{F_{t}\geq\epsilon_{\text{tol}}\}$ , by Theorem A.7 and (85),

\displaystyle\mathbb{E}[F_{t+1}|\mathcal{F}_{t}]\geq\left(1+\frac{\delta t}{2}(1-F_{t})\frac{\Delta}{\norm{H}_{2}}\right)F_{t}=\left(1+\frac{2^{n}C\Delta^{2}}{2\norm{H}_{2}^{2}}(1-F_{t})C_{\epsilon}\right)F_{t},\quad t\leq T+1.

(103)

Having (97), (98), and (101) in mind, we observe that

\displaystyle 1+\frac{2^{n}C\Delta^{2}}{2\norm{H}_{2}^{2}}(1-F_{t})C_{\epsilon}\geq\frac{2^{n}}{C\mathcal{T}^{2}}\cdot\frac{9}{8}\cdot\frac{\epsilon}{32C_{2}^{\star}}\geq\frac{2^{n}}{\mathcal{T}^{2}}.

(104)

Due to (95) and (98), we can determine $N_{0}\in\mathbb{N}$ such that the following holds

\displaystyle n\left(1-\min\left\{\frac{C_{f}}{2C_{\eta}\mathcal{P}_{k}},1\right\}\cdot\frac{C_{\eta}}{1-\sqrt{F_{1}}}\right)\geq 4\log_{2}\mathcal{P}_{k}-2\log_{2}C_{\ell}C_{\Delta}\geq 2\log_{2}\mathcal{T},

(105)

for every $n\geq N_{0}$ . Note that $N_{0}$ is determined only by $J$ , $F_{1}$ , and $\frac{\Delta}{\norm{H}_{2}}$ . By (105), we obtain

\displaystyle n-2\log_{2}\mathcal{T}\geq\frac{n}{\mathcal{T}}\cdot\frac{C_{\eta}}{1-\sqrt{F_{1}}},\quad\forall n\geq N_{0}.

(106)

Recall $T=\Theta(\mathcal{T})$ and observe that $T\geq\frac{1-\sqrt{F_{1}}}{C_{\eta}}\cdot\mathcal{T}$ holds by the definition. Therefore,

\displaystyle\frac{2^{n}}{\mathcal{T}^{2}}\geq 2^{\frac{n}{\mathcal{T}}\cdot\frac{C_{\eta}}{1-\sqrt{F_{1}}}}\geq 2^{\frac{n}{T}},\quad\forall n\geq N_{0}.

(107)

Due to (107), on the event $\{F_{t}\geq\epsilon_{\text{tol}}\}$ , we can reduce (103) to

\displaystyle\mathbb{E}[F_{t+1}|\mathcal{F}_{t}]\geq 2^{\frac{n}{T}}F_{t},\quad t\leq T+1.

(108)

Recall Definition A.3 and define a stopping time $\tau:=\min\{t:F_{t}<\epsilon_{\text{tol}}\}$ and a stopped process,

\displaystyle R_{t}:=\left(2^{\frac{n}{T}}\right)^{-(t\wedge\tau-1)}F_{t\wedge\tau},\quad t\in\mathbb{N}.

(109)

Consider two events $\{\tau\leq t\}\in\mathcal{F}_{t}$ and $\{\tau>t\}\in\mathcal{F}_{t}$ . On the event $\{\tau\leq t\}$ , by Definition A.3,

\mathbb{E}[\mathds{1}_{\{\tau\leq t\}}R_{t+1}|\mathcal{F}_{t}]=\mathbb{E}[\mathds{1}_{\{\tau\leq t\}}R_{\tau}|\mathcal{F}_{t}]=\mathds{1}_{\{\tau\leq t\}}R_{\tau}=\mathds{1}_{\{\tau\leq t\}}R_{t}.

(110)

On the event $\{\tau>t\}$ , by (108) and Definition A.3,

\displaystyle\begin{split}\mathbb{E}[\mathds{1}_{\{\tau>t\}}R_{t+1}|\mathcal{F}_{t}]=\mathbb{E}\left[\mathds{1}_{\{\tau>t\}}\left(2^{\frac{n}{T}}\right)^{-t}F_{t+1}\Big|\mathcal{F}_{t}\right]&=\mathds{1}_{\{\tau>t\}}\left(2^{\frac{n}{T}}\right)^{-t}\mathbb{E}\left[F_{t+1}|\mathcal{F}_{t}\right]\\ &\geq\mathds{1}_{\{\tau>t\}}\left(2^{\frac{n}{T}}\right)^{-t+1}F_{t}=\mathds{1}_{\{\tau>t\}}R_{t}.\end{split}

(111)

By combining (110) and (111), $R_{t}$ is a submartingale with respect to $\mathcal{F}_{t}$ so that $\mathbb{E}[R_{T+1}]\geq R_{1}=F_{1}$ . Let $A:=\{\tau<T+1\}$ . Recall $2\epsilon_{\text{tol}}\leq F_{1}$ then

\displaystyle 2\epsilon_{\text{tol}}\leq F_{1}\leq\mathbb{E}[R_{T+1}]\leq\mathbb{E}[R_{T+1}\mathds{1}_{A}+R_{T+1}\mathds{1}_{A^{c}}]\leq\epsilon_{\text{tol}}+\mathbb{E}[R_{T+1}\mathds{1}_{A^{c}}].

(112)

Hence $\mathbb{E}[R_{T+1}\mathds{1}_{A^{c}}]\geq\epsilon_{\text{tol}}$ so that $\mathbb{E}[F_{T+1}\mathds{1}_{A^{c}}]\geq 2^{n}\epsilon_{\text{tol}}=1-\frac{\epsilon}{2}$ . Combining this and (100), we can apply the reverse Markov inequality (A.5) to $F_{T+1}$ and obtain

\mathbb{P}\left(F_{T+1}\geq 1-\epsilon\right)\geq\mathbb{P}\left(F_{T+1}\mathds{1}_{A^{c}}\geq 1-\epsilon\right)\geq\frac{\mathbb{E}[F_{T+1}\mathds{1}_{A^{c}}]-(1-\epsilon)}{1-\frac{\epsilon}{2}+\frac{C_{\eta}}{2\mathcal{T}}-(1-\epsilon)}\geq\frac{\frac{\epsilon}{2}}{\frac{C_{\eta}}{2\mathcal{T}}+\frac{\epsilon}{2}}=1-\frac{1}{1+\frac{\epsilon\mathcal{T}}{C_{\eta}}}.

(113)

Due to (98), recall $\frac{\mathcal{P}_{k}}{C_{f}/2C_{\eta}}\leq\mathcal{T}\leq\frac{\mathcal{P}_{k}^{2}}{C_{\ell}C_{\Delta}}$ so that (113) shows (4) with a probability $\eta=\mathcal{O}\left(\frac{1}{\epsilon\mathcal{T}}\right)$ . Additionally, as we already discussed in Section 3.2, $S=JT$ due to Algorithm 1, which implies $S=\mathcal{O}(T)=\mathcal{O}(\mathcal{T})$ . Consequently, we verify (6) and Theorem 3.1 is proved. ∎

Remark A.9.

In (96), we use the same degree of polynomials for $\epsilon_{f}\geq\frac{C_{f}}{\mathcal{P}_{k}}$ and $\frac{\Delta}{\norm{H_2}}\geq\frac{C_{\Delta}}{\mathcal{P}_{k}}$ . Indeed, one can set different degrees $k^{\prime}\neq k$ of polynomials such that $\epsilon_{f}\geq\frac{C_{f}}{\mathcal{P}_{k^{\prime}}}$ and $\frac{\Delta}{\norm{H_2}}\geq\frac{C_{\Delta}}{\mathcal{P}_{k}}$ because (105) holds without any change so that (107) holds. Hence one can drive tighter precisions in Theorem 3.1.

Now we are ready to prove Theorem 3.3. For any given state $\ket{\phi}$ , we consider the Hamiltonian, $H_{\phi}=-\outerproduct{\phi}{\phi}$ . Note that the relative spectral gap of $H_{\phi}$ is one, $\ket{\phi}$ is the ground state, and there exists a computational basis $j_{\phi}\in[2^{n}]$ such that the following holds

\absolutevalue{\bra{\phi}\ket{j_\phi}}\ket{j_{\phi}}^{2}>\frac{1-\epsilon}{2^{n}},

(114)

for an arbitrary $\epsilon\in(0,1)$ .

Proof of Theorem 3.3.

Let $F_{1}=\absolutevalue{\bra{\phi}\ket{j_\phi}}\ket{j_{\phi}}^{2}$ . Since the relative spectral gap of $H_{\phi}$ is one, by putting $\frac{\Delta}{\norm{H}_{2}}=1$ , we can directly follow the previous proof to show (10) for the inverse-polynomial precision regime. Hence we concentrate on (9) for the constant precision regime.

Similar to the proof of Theorem 3.1, we can focus on $\epsilon<\min\{\frac{1}{2},1-\sqrt{F_{1}}\}$ for a given $F_{1}\geq\frac{1}{2^{n}}$ without the loss of generality. We set $\epsilon_{f}\geq C_{f}\geq\frac{2}{2^{n}+1}$ and $\epsilon_{\text{tol}}=\frac{1}{2^{n+1}}(1-\frac{\epsilon}{2})$ so that $\epsilon\geq\epsilon_{f}$ implies $1-\frac{\epsilon}{4}\leq 1-\epsilon_{\text{tol}}$ , and let $T:=\lfloor\frac{2(1-\frac{\epsilon}{2}-\sqrt{F}_{1})}{CC_{\eta}}\rfloor+1$ . Note that $T\geq 2$ , since $0<\frac{\epsilon}{2}\leq 1-\frac{\epsilon}{2}-\sqrt{F_{1}}$ . Recall $C_{\epsilon}$ in (97). Similar to (98), we choose $C>0$ satisfying

\displaystyle C_{\ell}\leq C\leq\min\left\{\frac{C_{f}}{2C_{\eta}},1\right\},\quad C_{\eta}:=2C_{\epsilon}C_{4}^{\star},

(115)

for some constant $C_{\ell}>0$ . Since $CC_{\eta}\leq\frac{C_{f}}{2}\leq\frac{\epsilon_{f}}{2}\leq\frac{\epsilon}{2}$ , similar to (101), we have

\displaystyle 1-F_{t}\geq\frac{\epsilon}{2}-\frac{CC_{\eta}}{2}>\frac{\epsilon}{4},\quad\text{for any }t\leq T+1.

(116)

We observe that for any $n\geq N_{0}$ where $N_{0}=\lceil 2\log_{2}\left(\frac{32C_{2}^{\star}}{9C_{\ell}C_{f}}\right)\rceil$ ,

1+\frac{2^{n}C}{2}(1-F_{t})C_{\epsilon}\geq\frac{2^{n}C_{\ell}}{8}\cdot\epsilon C_{\epsilon}\geq\frac{9\cdot 2^{n-8}C_{\ell}\epsilon}{C_{2}^{\star}}\geq\frac{9\cdot 2^{n-8}C_{\ell}C_{f}}{C_{2}^{\star}}\geq 2^{\frac{n}{2}}\geq 2^{\frac{n}{T}},

(117)

by (115), (116) for the first inequality, (97) for the second, recalling that $\epsilon\geq\epsilon_{f}\geq C_{f}$ for the third and $T\geq 2$ for the last. Therefore, following the techniques below (107), we have

\mathbb{P}\left(F_{T+1}\mathds{1}_{A^{c}}>1-\epsilon\right)\geq\frac{1-\frac{\epsilon}{2}-(1-\epsilon)}{1-\frac{\epsilon}{2}+\frac{CC_{\eta}}{2}-(1-\epsilon)}=\frac{\frac{\epsilon}{2}}{\frac{\epsilon}{2}+\frac{CC_{\eta}}{2}}\geq 1-\frac{1}{1+\frac{\epsilon}{CC_{\eta}}},

(118)

which shows (11). Thus, Theorem 3.3 is proved. ∎

A.5 Robustness to the Circuit Sampling Error

By far, we have considered the scenario where the coefficients $c_{t}^{(j)}$ are computed exactly, but computing them using a quantum computer would involve various noises in practice. Here we assume that there is no device error but only the measurement sampling error occurring due to the Born rule. In this scenario, we confirm that the result in Theorem 3.1 is still valid, proving Corollary 3.2.

Throughout the following analysis, we assume that $m=\text{poly}(n)$ and $a_{k}=\mathcal{O}(1)$ for all $k\in[m]$ in the Hamiltonian model (1). We further assume that our circuit sampling results in measurement outcomes that are read in the computational basis for a Pauli observable, which follows current quantum platforms nielsen2010quantum. We consider a normalized Hamiltonian,

\widetilde{H}:=H/C,\quad C:=4\sum_{k=1}^{m}\absolutevalue{a_k}.

(119)

Assuming the inverse-polynomial relative gap of $H$ as in Eq. 2, we notice that

\frac{\widetilde{\Delta}}{\norm{\widetilde{H}}_{2}}=\frac{\Delta}{\norm{H}_{2}}=\Omega\left(\frac{1}{\text{poly}(n)}\right),\quad\norm{\widetilde{H}}_{2}=\frac{\norm{H}_{2}}{C}\leq\frac{\sum_{k=1}^{m}\absolutevalue{a_k}}{C}=\frac{1}{4},

(120)

recalling that $H=\sum_{k=1}^{m}a_{k}P_{k}$ in (1). Here $\widetilde{\Delta}$ denotes the spectral gap of $\widetilde{H}$ , which equals $\frac{\Delta}{C}$ . We denote by $\{o_{j,t,k}\}_{j,k}$ , estimates of the exact coefficients $\bra{\psi_{1}}\left[P_{k},P_{j}^{(t)}\right]\ket{\psi_{1}}$ , which are averages of measurement outcomes obtained from a quantum computer. We see that

\mathbb{E}[o_{j,t,k}]=\bra{\psi_{1}}U_{t}^{\dagger}\left[P_{k},P_{j}^{(t)}\right]U_{t}\ket{\psi_{1}},

(121)

and then,

\begin{split}&\frac{1}{C}\sum_{k=1}^{m}a_{k}o_{j,t,k}-\absolutevalue{\frac{1}{C}\sum_{k=1}^ma_ko_{j,t,k}-\bra{\psi_1}U_t^\dagger\left[\widetilde{H},P_{j}^{(t)}\right]U_t\ket{\psi_1}}U_{t}^{\dagger}\left[\widetilde{H},P_{j}^{(t)}\right]U_{t}\ket{\psi_{1}}\\ &=\frac{1}{C}\sum_{k=1}^{m}a_{k}o_{j,t,k}-\absolutevalue{\sum_{k=1}^ma_ko_{j,t,k}-\bra{\psi_1}U_t^\dagger\left[H,P_{j}^{(t)}\right]U_t\ket{\psi_1}}U_{t}^{\dagger}\left[H,P_{j}^{(t)}\right]U_{t}\ket{\psi_{1}}\\ &\leq\frac{1}{C}\sum_{k=1}^{m}\absolutevalue{a_k}o_{j,t,k}-\absolutevalue{o_{j,t,k}-\bra{\psi_1}\left[P_k,P_{j}^{(t)}\right]\ket{\psi_1}}\left[P_{k},P_{j}^{(t)}\right]\ket{\psi_{1}}\leq\frac{4}{C}\sum_{k=1}^{m}\absolutevalue{a_k}=1\end{split}

(122)

by using the triangle inequality and the fact that for any state $\ket{\psi}$ and any Pauli operator $P$ ,

o-\absolutevalue{o-\bra{\psi}P\ket{\psi}}P\ket{\psi}\leq 2,

(123)

where $o$ is the average of measurement outcomes with respect to the state $\ket{\psi}$ for the observable $P$ . From this observation, we define

\widetilde{c}_{t}^{(j)}=\frac{1}{2^{n}}\left(\frac{1}{C}\sum_{k=1}^{m}a_{k}o_{j,t,k}\right).

(124)

By the above inequality result, we notice that

\absolutevalue{\widetilde{c}_{t}^{(j)}-c_{t}^{(j)}}\leq\frac{1}{2^{n}},\quad c_{t}^{(j)}\text{ defined in }\lx@cref{creftype~refnum}{alg: algorithm}

(125)

Now we incorporate the circuit sampling noise into the representation (47),

\begin{split}U_{t+1}&=\left(I+\delta t\mathcal{M}_{t}+\widetilde{E}_{1}^{(t)}+\widetilde{E}_{2}^{(t)}+\widetilde{E}_{3}^{(t)}\right),\end{split}

(126)

where the error terms $\widetilde{E}_{i}^{(t)}$ for $i\in\{1,2,3\}$ correspond to the ones in (47) but involve the sampling error, that is, $c_{t}^{(j)}$ ’s replaced by $\widetilde{c}_{t}^{(j)}$ ’s in the respective definitions of the errors, specifically,

\begin{split}&\norm{\widetilde{E}_1^{(t)}}_{2}\leq\frac{dt^{2}}{2}\sum_{j_{1}=1}^{J}\norm{\left[\sum_{j_2=j_1+1}^J\widetilde{c}_{t}^{(j_2)}P_{j_2}^{(t)},\widetilde{c}_{t}^{(j_1)}P_{j_1}^{(t)}\right]}_{2}\\ &\widetilde{E}_{2}^{(t)}=\sum_{j\geq 2}\frac{1}{j!}\left(dt\sum_{j=1}^{J}\widetilde{c}_{t}^{(j)}P_{j}^{(t)}\right)^{j}\\ &\widetilde{E}_{3}^{(t)}=dt\left(\sum_{j=1}^{J}\widetilde{c}_{t}^{(j)}P_{j}^{(t)}-\mathcal{M}_{t}\right),\quad\mathcal{M}_{t}\text{ defined in }\eqref{eq: Udynamics}.\end{split}

(127)

Now we show that the new error terms $\widetilde{E}_{i}^{(t)}$ for $i\in\{1,2,3\}$ are bounded above by similar scalings as in Lemma 3.5, as we proved Lemma A.6. From this observation, we prove Corollary 3.2 as follows.

Proof of Corollary 3.2.

We claim the following: the noisy coefficients $\widetilde{c}_{j,t}$ satisfy

\sum_{j=1}^{J}\absolutevalue{\widetilde{c}_{t}^{(j)}}\leq\frac{J+2}{2^{n+1}},

(128)

and the error terms $\widetilde{E}_{i}^{(t)}$ for $i\in\{1,2,3\}$ satisfy that

\begin{split}&\norm{\widetilde{E}_1^{(t)}}_{2}\leq\left(\frac{J+2}{2^{n+1}}\right)^{2}(\delta t)^{2}\\ &\norm{\widetilde{E}_2^{(t)}}_{2}\leq\exp\left(\frac{J+2}{2^{n+1}}\delta t\right)\left(\frac{J+2}{2^{n+1}}\right)^{2}\frac{(\delta t)^{2}}{2}\\ &\mathbb{E}\left[\widetilde{E}_{3}^{(t)}|\mathcal{F}_{t}\right]=dt\left(\frac{J}{4^{n}}-1\right)\mathcal{M}_{t}\\ &\norm{\widetilde{E}_3^{(t)}}_{2}\leq\frac{\delta t}{2}.\end{split}

(129)

The proof is simply based on those of Lemma A.6, Lemma 3.5, and Theorem 3.1. Using (125) and (120), we notice by the triangle inequality,

\sum_{j=1}^{J}\absolutevalue{\widetilde{c}_{t}^{(j)}}\leq\sum_{j=1}^{J}\absolutevalue{\widetilde{c}_{t}^{(j)}-c_{t}^{(j)}}+\sum_{j=1}^{J}\absolutevalue{c_{t}^{(j)}}\leq\frac{1}{2^{n}}+\frac{J}{2^{n+1}}=\frac{J+2}{2^{n+1}}.

(130)

Then, the remaining error bounds for the three errors immediately follow as in the proof below Lemma A.6. For the third error, by the Born rule, it is satisfed that

\mathbb{E}\left[\sum_{j=1}^{J}\widetilde{c}_{t}^{(j)}P_{t}^{(j)}\Big|\mathcal{F}_{t}\right]=\mathbb{E}\left[\sum_{j=1}^{J}c_{t}^{(j)}P_{t}^{(j)}\Big|\mathcal{F}_{t}\right].

(131)

Noticing that these error bounds have the same scalings as those in Lemma 3.5 with respect to $n$ , we can apply the technical results in Section A.3. Thus, by following the above proof of Theorem 3.1 under the assumption on relative spectral gap (120), $T=\Theta\left(\frac{\norm{H}_{2}}{C\Delta}\right)$ . That is, we run Algorithm 1 with a polynomial number of iterations. In addition, as we assumed that $m=\text{poly}(n)$ in (1), the total number of measurements to estimate (125) for each $j\in[J]$ scales polynomial at each iteration. Since $J=\mathcal{O}(1)$ and $T=\mathcal{O}(\text{poly}(n))$ , the total number of measurements scales polynomial. Furthermore, using Remark 3.4, sampling $J$ Pauli operators at each iteration takes $\mathcal{O}(n)$ classical time. Since $T=\mathcal{O}(\text{poly}(n))$ , the total classical time scales polynomial, too. Therefore, this complete the proof of Corollary 3.2. ∎

A.6 Degenerate ground states

The following proof extends the above ones of Theorem 3.1 and Corollary 3.2, which is for the case of non-degenerate ground state, to that of degenerate ground states. Let us denote by $P_{\lambda_{1}}$ , the projection onto the space of ground states of $H$ , specifically,

P_{\lambda_{1}}:=\sum_{k=1}^{K}\outerproduct{\lambda_{1,k}}{\lambda_{1,k}},

(132)

where $\{\ket{\lambda_{1,k}}\}_{k=1}^{K}$ denotes the set of degenerate ground states of $H$ .

Theorem A.10.

The results in Theorem 3.1 and Corollary 3.2 hold even in the case of degenerate ground states.

Proof.

For convenience, we first consider the case without circuit sampling error. The case with circuit sampling error will then immediately follow as in the above proof of Corollary 3.2.

We prove the case of degenerate ground states by defining a more general overlap, slightly modifying the results in Theorem A.7 and applying the same techniques in the proof of Theorem 3.1. To this end, we define the overlaps with degenerate ground states and the total overlap as follows,

\begin{split}&F_{t,k}:=\absolutevalue{\bra{\lambda_{1,k}}U_t\ket{\psi_1}}U_{t}\ket{\psi_{1}}^{2},\quad\text{for each }k\in[K]\\ &F_{t}:=\sum_{k=1}^{K}F_{t,k}.\end{split}

(133)

Equivalently, we see that

F_{t}=\tr\left(P_{\lambda_{1}}U_{t}\outerproduct{\psi_1}{\psi_1}U_{t}^{\dagger}\right).

(134)

We want to show that the total overlap $F_{t}$ satisfies the results in Theorem A.7, and therefore the above proof of Theorem 3.1 applies.

Then, from (69), we notice no change

\begin{split}D_{t}&=\bra{\psi_{1}}U_{t}^{\dagger}HU_{t}\ket{\psi_{1}}-\lambda_{1}\\ &=\sum_{i=1}^{2^{n}}\lambda_{i}\absolutevalue{\bra{\lambda_i}U_t\ket{\psi_1}}U_{t}\ket{\psi_{1}}^{2}-\lambda_{1}\\ &\geq\lambda_{1}\sum_{k=1}^{K}F_{t,k}+\lambda_{2}(1-\sum_{k=1}^{K}F_{t,k})-\lambda_{1}\\ &=\lambda_{1}F_{t}+\lambda_{2}(1-F_{t})-\lambda_{1}\geq(1-F_{t})\Delta\geq 0,\end{split}

(135)

but the result in Theorem A.7 is slightly changed as

\mathbb{E}[F_{t+1,k}|\mathcal{F}_{t}]\geq\left(1+\frac{\delta t\Delta}{2}(1-F_{t})\right)F_{t,k}.

(136)

By summing the inequalities over $k$ ’s, we obtain

\mathbb{E}[F_{t+1}|\mathcal{F}_{t}]\geq\left(1+\frac{\delta t\Delta}{2}(1-F_{t})\right)F_{t}.

(137)

Next we derive a similar result as in Eq. 86. Similar to (75) in the proof of Eq. 76, we obtain by replacing the non-degenerate ground state $\ket{\lambda_{1}}$ by the projection $P_{\lambda_{1}}$ ,

\begin{split}&\tr\left(P_{\lambda_{1}}(I+\delta t\mathcal{M}_{t}+E_{3}^{(t)})U_{t}\outerproduct{\psi_1}{\psi_1}U_{t}^{\dagger}(I+\delta t\mathcal{M}_{t}+E_{3}^{(t)})^{\dagger}\right)\\ &\tr\left(P_{\lambda_{1}}(I+\delta t\sum_{j=1}^{J}c_{j,t}P_{j}^{(t)})U_{t}\outerproduct{\psi_1}{\psi_1}U_{t}^{\dagger}(I+\delta t\sum_{j=1}^{J}c_{j,t}P_{j}^{(t)})^{\dagger}\right)\\ &=F_{t}+\delta t\tr\left(\left[P_{\lambda_{1}}U_{t}\outerproduct{\psi_1}{\psi_1}U_{t}^{\dagger}\sum_{j=1}^{J}c_{j,t}P_{j}^{(t)}+h.c.\right]\right)+\delta t^{2}P_{\lambda_{1}}\sum_{j=1}^{J}c_{j,t}P_{j}^{(t)}U_{t}\norm{P_{\lambda_1}\sum_{j=1}^Jc_{j,t}P_j^{(t)}U_t\ket{\psi_1}}_{2}^{2}\\ &\leq F_{t}+2\delta t\sqrt{F_{t}}\left(\sum_{j=1}^{J}\absolutevalue{c_{j,t}}\right)+\delta t^{2}\left(\sum_{j=1}^{J}\absolutevalue{c_{j,t}}\right)^{2}=\left(\sqrt{F_{t}}+\delta t\frac{J}{2^{n-1}}\norm{H}_{2}\right)^{2},\end{split}

(138)

by the triangle inequality and the facts that $P_{\lambda_{1}}U_{t}\norm{P_{\lambda_1}U_t\ket{\psi_1}}_{2}^{2}=F_{t}$ , $\norm{P_{\lambda_1}}_{2}=1$ , and $\norm{P_j}_{2}=1$ for any Pauli operator $P_{j}$ . Similar to result Eq. 82, we obtain

\begin{split}&2\tr\left(P_{\lambda_{1}}\left(I+\delta t\mathcal{M}_{t}+E_{3}^{(t)}\right)U_{t}\outerproduct{\psi_1}{\psi_1}\left(E_{1}^{(t)}+E_{2}^{(t)}\right)U_{t}\right)\\ &\leq 2P_{\lambda_{1}}\left(I+\delta t\mathcal{M}_{t}+E_{3}^{(t)}\right)U_{t}\norm{P_{\lambda_1}\left(I + \delta t\mathcal{M}_{t}+E_3^{(t)}\right)U_t\ket{\psi_1}}_{2}U_{t}\left(E_{1}^{(t)}+E_{2}^{(t)}\right)\norm{U_t\left(E_1^{(t)} +E_2^{(t)}\right)\ket{\psi_1}}_{2}\\ &\leq 2\left(1+\frac{J\norm{H}_{2}}{2^{n-1}}\delta t\right)\left(\norm{E_1^{(t)}}_{2}+\norm{E_2^{(t)}}_{2}\right)\\ &\leq 2\left(1+\frac{J\norm{H}_{2}}{2^{n-1}}\delta t\right)\left(1+\frac{1}{2}\exp\left(\frac{J\norm{H}_{2}}{2^{n-1}}\delta t\right)\right)\left(\frac{J\norm{H}_{2}}{2^{n-1}}\right)^{2}(\delta t)^{2}=C_{2}\left(\frac{\delta t}{2^{n}}\right)^{2}\end{split}

(139)

by using Lemma 3.5, and

\begin{split}&\tr\left(P_{\lambda_{1}}\left(E_{1}^{(t)}+E_{2}^{(t)}\right)U_{t}\outerproduct{\psi_1}{\psi_1}U_{t}^{\dagger}\left(E_{1}^{(t)}+E_{2}^{(t)}\right)^{\dagger}\right)\\ &\leq\left(1+\frac{1}{2}\exp\left(\frac{J\norm{H}_{2}}{2^{n-1}}\delta t\right)\right)^{2}\left(\frac{J\norm{H}_{2}}{2^{n-1}}\right)^{4}(\delta t)^{4}=C_{3}\left(\frac{\delta}{2^{n}}\right)^{4}.\end{split}

(140)

Combining these results, we achieve the same result as in Eq. 86,

\sqrt{F_{t+1}}\leq\sqrt{F_{t}}+\frac{\delta t}{2^{n}}\sqrt{4J^{2}\norm{H}_{2}^{2}+C_{2}+C_{3}\left(\frac{\delta t}{2^{n}}\right)^{2}}.

(141)

Following the proof of Theorem 3.1 together with (137) and (141), we prove the case of degenerate ground states without circuit sampling error, and obtain the same conclusion, except that

F_{t}=\tr\left(P_{\lambda_{1}}U_{t}\outerproduct{\psi_1}{\psi_1}U_{t}^{\dagger}\right).

(142)

The case with circuit sampling error can be straightforwardly proved, similar to the proof of Corollary 3.2 in Section A.5.

∎

We apply this result to the classical Ising model (31). Using the notation in Theorem 3.1, we establish the following:

Theorem A.11.

For any Ising model (31) satisfying

\displaystyle\frac{\absolutevalue{J_{ij}}}{\sum_{i^{\prime}j^{\prime}}\absolutevalue{J_{i'j'}}+\sum_{i^{\prime}}\absolutevalue{h_{i'}}}=\Omega\left(\frac{1}{\text{poly}(n)}\right),\quad\frac{\absolutevalue{h_i}}{\sum_{i^{\prime}j^{\prime}}\absolutevalue{J_{i'j'}}+\sum_{i^{\prime}}\absolutevalue{h_{i'}}}=\Omega\left(\frac{1}{\text{poly}(n)}\right),

(143)

for $J_{ij}\neq 0$ and $h_{i}\neq 0$ , there exists $N_{0}\in\mathbb{N}$ such that for any $n\geq N_{0}$ , Algorithm 1 finds a ground state with

\displaystyle\epsilon_{f}=\Omega\left(\frac{1}{\text{poly}(n)}\right),\ S=\mathcal{O}(\text{poly}(n)),\ \eta=\mathcal{O}\left(\frac{1}{\text{poly}(n)}\right),

(144)

with $\mathcal{O}(\text{poly}(n))$ classical time and $\mathcal{O}(\text{poly}(n))$ measurements.

Proof.

We observe that (32) is a sufficient condition for that $\frac{\Delta}{\norm{H}_{2}}=\Omega\left(\frac{1}{\text{poly}(n)}\right)$ . Now we implement Algorithm 1 to find a ground state of the Ising model satisfying the condition in the statement. First, the initial state with uniform amplitudes $\ket{+}^{\otimes n}$ has an overlap of $\frac{1}{2^{n}}$ with a ground state of the Ising model. Second, computing the above lower bound of $\frac{\Delta}{\norm{H}_{2}}$ in (33) takes $\mathcal{O}(n^{2})$ classical time, and so does finding a step size, $\delta t$ , and a maximal iteration step, $T$ , as defined in and below (99). Therefore, by Theorem A.10, with a constant batch size $J=\mathcal{O}(1)$ , Algorithm 1 finds a ground state by outputting a $\mathcal{O}(\text{poly}(n))$ circuit, to within $\Theta\frac{1}{\text{poly}(n)}$ precision, with a failure probability of $\mathcal{O}\left(\frac{1}{\text{poly}(n)}\right)$ . The overall runtime scales polynomial, since the number of measurements and the classical time for sampling Pauli operators in Algorithm 1, which is efficiently done using Remark 3.4, scale polynomial at each iteration and the maximal iteration step $T=\mathcal{O}(\text{poly}(n))$ . ∎

We apply this result to problems $3$ and $5$ in barahona1982computational.

Corollary A.12 (Quantum advantage in solving NP-hard Ising models).

There exists $N_{0}\in\mathbb{N}$ such that for any $n\geq N_{0}$ , NP-hard problems 3 and 5 by Barahona barahona1982computational are solvable in $\mathcal{O}(\text{poly}(n))$ time using both classical and quantum computers, with failure probability $\eta=\mathcal{O}\left(\frac{1}{\text{poly}(n)}\right)<0.01$ .

Proof.

The problems 3 and 5 by Barahona correspond to finding the minimum energy of the following Ising models,

H=-\sum_{1\leq i<j\leq n}J_{ij}Z_{i}Z_{j},\quad H=\sum_{1\leq i<j\leq n}Z_{i}Z_{j}+\sum_{i=1}^{n}Z_{i},

(145)

where each $J_{ij}\in\{-1,0,1\}$ . Obviously, these models satisfy (32), so the statement is proved by Theorem A.11.

∎

Analytic and Stochastic Approach to Quantum Advantages in Ground State and Quantum State Preparation Problems

Abstract

1 Introduction

2 Related works

2.1 Ground state preparation

Variational Quantum Eigensolver (VQE) and Adaptive Variants

Adiabatic State Preparation (ASP)

Filtering-based Quantum Algorithms with Post-selection

Quantum Imaginary Time Evolution (QITE)

Lindblad-type Algorithms

Regime of Quantum Computing

2.2 Quantum state preparation

3 Main Results

3.1 Formulation

Problem 1 (Ground State Preparation).

Theorem 3.1.

Corollary 3.2.

Problem 2 (Quantum State Preparation).

Theorem 3.3.

3.2 Algorithm: Stochastic Riemannian Gradient Flow

Remark 3.4 (Efficient sampling distinct Pauli operators).

3.3 Proof of Theorems 3.1 and 3.3

3.3.1 Decomposition of Recursive Unitary Compiling

Lemma 3.5.

3.3.2 Properties and Behavior of Overlap Process

3.3.3 Derivation of Iteration Complexity with a Relative Spectral Gap

4 Applications to Combinatorial Optimization

5 Conclusion and Discussion

Acknowledgments

Appendix A Appendix

A.1 Preliminaries

Definition A.1.

Definition A.2 (Stopping Time).

Definition A.3 (Stopped Process).

Lemma A.4 (Doob’s Optional Stopping Theorem).

Proof.

Lemma A.5 (Reverse Markov Inequality).

Proof.

A.2 Proof of Lemma 3.5

Lemma A.6.

Proof.

Proof of Lemma 3.5.

A.3 Properties of Overlap Process

Estimation of Q1Q_{1}.

Estimation of Q2Q_{2} and Q3Q_{3}

Theorem A.7.

Proof.

Remark A.8.

A.4 Proof of Main Results

Proof of Theorem 3.1.

Remark A.9.

Proof of Theorem 3.3.

A.5 Robustness to the Circuit Sampling Error

Proof of Corollary 3.2.

A.6 Degenerate ground states

Theorem A.10.

Proof.

Theorem A.11.

Proof.

Corollary A.12 (Quantum advantage in solving NP-hard Ising models).

Proof.

References

Estimation of $Q_{1}$ .

Estimation of $Q_{2}$ and $Q_{3}$