betaFeedback

WorksPhysics and Astronomy

Convergence and efficiency proof of quantum imaginary time evolution for bounded order systems

Abstract

Many current and near-future applications of quantum computing utilise parametric families of quantum circuits and variational methods that can suffer from obstacles including non-convergence to the global minimum due to local minima, critical slowing down, or exponential resource scaling. Here we show that quantum imaginary time evolution can overcome these obstacles if the underlying physical system satisfies a set of conditions. This includes many relevant applications such as ground state preparation for local theories in physics or chemistry, combinatorial optimisation problems, or quantum machine learning. In particular, we analyse the quantum imaginary time evolution showing convergence guarantees to the global minimum without critical slowing down and providing a priori estimates on the required evolution time which scale linearly in system size and inverse energy gap. Furthermore, a provided complexity analysis shows that quantum imaginary time evolution can be efficiently compiled into a parametric quantum circuit, finding the optimal parameters included, for a large class of physically relevant problems.

Introduction

With quantum devices becoming ever more powerful, many of their current and near-future applications have similar computational setups. A common approach is to program the quantum device with a parametric quantum circuit (PQC) and to find the correct parameters of the circuit by optimising some cost function through variational methods. Such cost functions may arise naturally in physics [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12] or chemistry and drug design [13, 14, 15, 16, 17, 18], since the solution of the computational problem is often the ground state of a quantum mechanical system. In fields like quantum machine learning (QML) [19, 20, 21, 22, 23, 24, 25, 26, 27, 29, 30] [28] or combinatorial optimisation [31, 32, 33, 34, 35, 36, 37, 38, 40] [39], the modelling process commonly involves mapping the problem in question to a quantum mechanical system in such a way that the solution is found by optimising some specifically designed observable. Such observables are commonly related to the Hamiltonian (i.e., energy) of the constructed system.

Since quantum devices generally cannot efficiently measure arbitrary observables, some efficiency assumptions need to be made. A common assumption is locality. For physical systems, this is usually automatically satisfied as the dynamics are commonly described through second order terms such as two-body or nearest-neighbour interactions. While higher order interactions are possible, e.g., plaquette terms in lattice gauge theories are fourth order as four “link variables” contribute to each plaquette, most physical systems have some bounded order. Non-physical systems such as those arising from QML or combinatorial optimisation might not have such a “natural” order bound, but constructing the problem in such a way that a bounded order system is to be solved on a quantum device is frequently required as otherwise exponential complexity cannot be avoided.

Once a problem is mapped to an instance accessible via variational quantum computing methods, the main challenges are to choose a suitable PQC and a suitable method of finding the required parameters. Here, various approaches are possible. Many PQCs may be chosen because they are efficient to implement on the hardware and/or enforce required symmetries [21, 22, 23, 41, 42, 43] with optimisers chosen based on performance tests and regularity assumptions of the cost function. Other notable approaches are based on physical system evolutions, such as the quantum approximate optimisation algorithm (QAOA) which is based on adiabatic evolution [44, 45]. While adiabaticity has shown to be very successful [46, 47, 48], it has limitations. For example, the evolution needs to be sufficiently slow to avoid diabatic excitations [49]. This can lead to deep circuits with many parameters and highly oscillatory cost function landscapes that are difficult to optimise due to the high density of local optima [50] and barren plateaus [51, 52, 53, 54, 55, 56]. Thus, higher-order counterdiabatic terms are required [57, 58, 59, 60] which can be difficult to implement on current quantum devices.

An alternative to adiabatic evolution is imaginary time evolution (ITE). Although unphysical, ITE is a powerful tool widely used in quantum and statistical mechanics. In particular, in lattice simulations, ITE is known to converge exponentially with evolution time bounded by the inverse energy gap [61]. Furthermore, quantum ITE implementations have shown good convergence behaviour as well [20, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79]. These are particularly notable for systems with limited interaction terms, e.g., nearest neighbour interactions. While physical intuition suggests a wide applicability range, finding exact conditions under which ITE is efficiently implementable is an open problem. Additionally, the scaling of quantum ITE, that is the implementation of ITE on a quantum device, and whether or not it can circumvent the bottlenecks of other quantum computing approaches remained unknown.

It should be noted that non-variational methods such as quantum phase estimation [80, 81, 82], exact diagonalisation [83, 84], or Krylov space methods [85, 86, 87, 88, 89] exist as well. These methods have shown remarkable results such as theoretical precision guarantees and exponential convergence with polynomial resources. However, they are also not without challenges. For example, general quantum subspace diagonalisation methods commonly lead to ill-conditioned generalised eigenvalue problems that require suitable truncations. Importantly, for many of these methods provable convergence guarantees or provable polynomial cost seem to require an initial reference state with inverse polynomial fidelity. Since the problem of finding the ground state of local Hamiltonians is QMA-complete [90], such restrictions will generally be necessary for any approach and other alternatives to a non-trivial fidelity requirement, including the construction of an adiabatic path from an efficiently solvable Hamiltonian [44], have been studied as well. In that sense, the choice of computational approach not only depends on the performance of various methods given an instance of a computational problem, but also on relevant a priori and ab initio information.

In this article, we will address some of the above mentioned open questions surrounding convergence guarantees, convergence rate, and compilability of quantum ITE. We will show that quantum ITE retains the exponential convergence observed in lattice theories and that this leads to bounds on the evolution time which are linear in the inverse energy gap. Furthermore, we will show that the evolution time is linear in the number of qubits – even for exponentially small initial fidelities – and that no critical slowing down can occur during the evolution. These results are independent of the quantum circuit compilation process which may not be efficiently possible. However, if the Hamiltonian has bounded order and its coefficients have polynomial growth scaling, then we will show that the ITE can be compiled into a PQC of polynomial depth (in the number of qubits and the inverse energy gap), and that the parameters can be found with polynomial cost. Thus, we will prove the efficiency of quantum computations for a large class of bounded order systems which includes many physical and chemical systems, as well as QML and combinatorial optimisation problems.

More precisely, we will prove our main results as summarised in Theorem 1.

Theorem 1. The imaginary time evolution converges with probability 1 to a state in the lowest energy eigenspace up to bounded error in linear time with respect to the number of qubits and inverse energy gap.

Furthermore, the imaginary time evolution for bounded order systems (defined in Complexity Analysis section) can be compiled into a quantum circuit of polynomial depth in the number of qubits and the compilation cost scales polynomially in the number of qubits and inverse energy gap.

The ingredients for the proof of Theorem 1 are split into two categories: General Convergence Results and Complexity Analysis. For the convergence results, we will not consider any means of implementing the ITE, but instead assume that it is possible. We will only discuss circuit compilation in the Complexity Analysis section. Finally, we will provide an explicit Single-Qubit Example highlighting the compilation procedure.

Results

General Convergence Results

For the entire results section, we will assume that the Hamiltonian HH is given on a QQ-qubit system and we choose to order its eigenvalues λ0≤λ1≤⋯≤λN\lambda_0 \leq\lambda_1 \leq\cdots\leq\lambda_N increasingly including multiplicities, i.e., N=2Q−1N = 2^Q - 1. Denoting the multiplicity of λ0\lambda_0 with μ\mu, this means that λ0=⋯=λμ−1<λμ\lambda_0 = \cdots= \lambda_{\mu-1} < \lambda_\mu and we define the energy gap as Δ=λμ−λ0\Delta= \lambda_\mu- \lambda_0. The eigenstates corresponding to the λj\lambda_j will be denoted ∣ψj⟩|\psi_j\rangle.

Convergence Guarantees

The ITE of given initial state ∣ψ(0)⟩|\psi(0)\rangle with respect to the Hamiltonian HH is ∣ψ(t)⟩=∥e−tH∣ψ(0)⟩∥2−1e−tH∣ψ(0)⟩|\psi(t)\rangle= \frac{\|e^{-tH}|\psi(0)\rangle\|_2^{-1}}{}e^{-tH}|\psi(0)\rangle. Using the eigenbasis expansion ∣ψ(t)⟩=∑j=0Nαj(t)∣ψj⟩|\psi(t)\rangle= \sum_{j=0}^{N}\alpha_j(t)|\psi_j\rangle, we observe αj(t)=αj(0)(∑k=0N∣αk(0)∣2e−2t(λk−λj))−12\alpha_j(t) = \alpha_j(0)\left(\sum_{k=0}^{N}|\alpha_k(0)|^2e^{-2t(\lambda_k-\lambda_j)}\right)^{-\frac{1}{2}}. This immediately implies αj(t)≠0\alpha_j(t) \ne0 if and only if αj(0)≠0\alpha_j(0) \ne0 for all t>0t > 0, as well as monotone convergence (in absolute value)

αj(t)→{αj(0)∑k=0μ−1∣αk(0)∣2,j<μ,0,j≥μ.(1)\alpha_j(t) \to\begin{cases} \frac{\alpha_j(0)}{\sqrt{\sum_{k=0}^{\mu-1}|\alpha_k(0)|^2}}, & j < \mu,\\ 0, & j \geq\mu. \end{cases} \tag*{(1)}

Equation (1) assumes at αj(0)≠0\alpha_j(0) \ne0 for at least one j<μj < \mu. If that is not the case, the same expression holds for the lowest energy eigenspace that has non-zero overlap with ∣ψ(0)⟩|\psi(0)\rangle. In other words, the non-linear operator ∣ψ(0)⟩↦lim⁡t→∞∣ψ(t)⟩|\psi(0)\rangle\mapsto\lim_{t\to\infty}|\psi(t)\rangle is equivalent to the two-step process of orthogonally projecting onto the eigenspace of HH with smallest eigenvalue that ∣ψ(0)⟩|\psi(0)\rangle isn’t orthogonal to and then normalising to the unit sphere in the underlying Hilbert space.

At first sight, this seems to imply that the initial state ∣ψ(0)⟩|\psi(0)\rangle having non-zero overlap with at least one of the states ∣ψ0⟩,…,∣ψμ−1⟩|\psi_0\rangle,\ldots,|\psi_{\mu-1}\rangle somehow needs to be satisfied in practice in order to ensure convergence to a state in the lowest energy eigenspace. However, the manifold of states orthogonal to the lowest energy eigenspace is a null set. This follows since the set of states orthogonal to the lowest energy eigenspace is the intersection of the unit sphere of the Hilbert space with a subspace of codimension μ\mu. Thus, unless the Hamiltonian is a multiple of the identity, this orthogonal set is a lower-dimensional submanifold of the state space and Sard’s theorem [91] implies that all lower-dimensional submanifolds are null sets. The probability for a random initial state to have non-zero overlap with the lowest energy eigenspace is therefore 1. Furthermore, even if we had such a bad initial state, in the presence of device noise, the probability of remaining in this null set is 0. In other words, the ITE converges to a state in the lowest energy eigenspace with probability 1 (up to device precision). Hence, from this point onwards, we will assume non-orthogonality of the initial state ∣ψ(0)⟩|\psi(0)\rangle with the lowest energy eigenspace spanned by ∣ψ0⟩,…,∣ψμ−1⟩|\psi_0\rangle,\ldots,|\psi_{\mu-1}\rangle.

Absence of Critical Slow Down

Many optimisation algorithms can suffer from a variation of “critical slow down”, that is, the optimisation appears arrested without having achieved convergence. Considering the path of the evolution t↦∣ψ(t)⟩t \mapsto|\psi(t)\rangle in the unit sphere ∂B(0,1)\partial B(0,1) of the underlying Hilbert space, we observe

ddt∣ψ(t)⟩=⟨ψ(t)∣H∣ψ(t)⟩∣ψ(t)⟩−H∣ψ(t)⟩=−pr⁡T∣ψ(t)⟩∂B(0,1)H∣ψ(t)⟩(2)\frac{d}{dt}|\psi(t)\rangle=\langle\psi(t)|H|\psi(t)\rangle|\psi(t)\rangle-H|\psi(t)\rangle=-\operatorname{pr}_{T_{|\psi(t)\rangle}\partial B(0,1)}H|\psi(t)\rangle \tag*{(2)}

where pr⁡T∣ψ(t)⟩∂B(0,1)\operatorname{pr}_{T_{|\psi(t)\rangle}\partial B(0,1)} denotes the orthogonal projector onto the tangent space of the unit sphere ∂B(0,1)\partial B(0,1) at the point ∣ψ(t)⟩|\psi(t)\rangle. Considering the energy E(t)=⟨ψ(t)∣H∣ψ(t)⟩E(t)=\langle\psi(t)|H|\psi(t)\rangle along the path, this implies E′(t)=−2∥pr⁡T∣ψ(t)⟩∂B(0,1)H∣ψ(t)⟩∥22≤0E'(t)=-2\left\|\operatorname{pr}_{T_{|\psi(t)\rangle}\partial B(0,1)}H|\psi(t)\rangle\right\|_2^2\leq0, i.e., the energy is monotonically decreasing. Additionally, the energy gradient can only vanish if ∣ψ(t)⟩|\psi(t)\rangle is an eigenstate of HH. In other words, any critical slowing down of the evolution can only occur in a neighbourhood of an eigenstate of the Hamiltonian. But, this cannot happen for any excited state ∣ψj⟩|\psi_j\rangle with λj>λ0\lambda_j>\lambda_0 due to monotonicity of αj→0\alpha_j\to0 and, since the energy is efficiently measurable for bounded order Hamiltonians, it provides useful on-the-fly data that can be used to ascertain convergence.

Rate of Convergence

Having established convergence without critical slowing down, i.e., guaranteed convergence in practical settings, we can turn our attention to the rate of convergence. Setting a=∑k=0μ−1∣αk(0)∣2a=\sum_{k=0}^{\mu-1}|\alpha_k(0)|^2 and x=∑k=μN−1∣αk(0)∣2e−2t(λk−λ0)x=\sum_{k=\mu}^{N-1}|\alpha_k(0)|^2e^{-2t(\lambda_k-\lambda_0)} we obtain ∣ψ(t)⟩=∑k=0μ−1αk(0)∣ψk⟩+∑k=μN−1αk(0)e−t(λk−λ0)∣ψk⟩a+x|\psi(t)\rangle=\frac{\sum_{k=0}^{\mu-1}\alpha_k(0)|\psi_k\rangle+\sum_{k=\mu}^{N-1}\alpha_k(0)e^{-t(\lambda_k-\lambda_0)}|\psi_k\rangle}{\sqrt{a+x}} and lim⁡τ→∞∣ψ(τ)⟩=∑k=0μ−1αk(0)∣ψk⟩a\lim_{\tau\to\infty}|\psi(\tau)\rangle=\frac{\sum_{k=0}^{\mu-1}\alpha_k(0)|\psi_k\rangle}{\sqrt{a}}. Thus,

∥∣ψ(t)⟩−lim⁡τ→∞∣ψ(τ)⟩∥22=(1a+x−1a)2a+xa+x=2(1−aa+x)≤xa≤1−aae−2tΔ.(3)\begin{aligned} \left\||\psi(t)\rangle-\lim_{\tau\to\infty}|\psi(\tau)\rangle\right\|_2^2=\left(\frac{1}{\sqrt{a+x}}-\frac{1}{\sqrt{a}}\right)^2a+\frac{x}{a+x} \\ &=2\left(1-\sqrt{\frac{a}{a+x}}\right)\leq\frac{x}{a}\leq\frac{1-a}{a}e^{-2t\Delta}. \tag*{(3)} \end{aligned}

Thus, we observe exponential convergence with the rate of convergence determined by the energy gap and the constant determined by the initial overlap with the solution.

More precisely, we can bound the fidelity f(t)=∑j=0μ−1∣αj(t)∣2≥11+f(0)−1e−2tΔf(t)=\sum_{j=0}^{\mu-1}|\alpha_j(t)|^2 \geq\frac{1}{1+f(0)^{-1}e^{-2t\Delta}} which implies that any fidelity threshold ff is guaranteed for t≥ln⁡f−ln⁡(1−f)−ln⁡(f(0))2Δt \geq\frac{\ln f-\ln(1-f)-\ln(f(0))}{2\Delta}. Assuming f(0)∝2−Qf(0)\propto2^{-Q} can be achieved for random or specifically chosen initial states (in the following section we will show that this can reasonably be considered a default assumption for random initial states), this implies that arbitrary fidelity thresholds can be guaranteed in linear time with respect to the number of qubits and inverse energy gap Q/ΔQ/\Delta.

Bounding the Initial Fidelity

In the paragraph above, the assumption f(0)∝2−Qf(0)\propto2^{-Q} was used to justify linear scaling in Q/ΔQ/\Delta to reach arbitrary fidelity thresholds. Here, we will show that this is generally satisfied and expected for uniformly random initial states in the unit sphere of the underlying Hilbert space, i.e., the quantum device state space.

Let us assume that the lowest eigenvalue has multiplicity μ\mu and that the initial state is decomposed as ∣ψ⟩=∑j=02Q−1αj∣j⟩|\psi\rangle=\sum_{j=0}^{2^Q-1}\alpha_j|j\rangle where {∣j⟩;0≤j≤2Q−1}\{|j\rangle; 0\leq j\leq2^Q-1\} is an orthonormal basis and {∣j⟩;0≤j≤μ−1}\{|j\rangle; 0\leq j\leq\mu-1\} an orthonormal basis of the ground state eigenspace. Since a uniform distribution on a sphere in Rd\mathbb{R}^d can be generated by using dd independent standard normal distributions to sample the coefficients and normalising [92, 93], we know that ∣ψ⟩|\psi\rangle can be generated using 2Q+12^{Q+1} many standard normally distributed random variables Zk,jZ_{k,j} with k∈{1,2}k\in\{1,2\} and 0≤j<2Q0\leq j<2^Q. In fact, we can express the coefficients of ∣ψ⟩|\psi\rangle as αj=Z1,j+iZ2,j∣Z∣\alpha_j=\frac{Z_{1,j}+iZ_{2,j}}{|Z|} with ∣Z∣=∑j=02Q−1∑k=12Zj,k2|Z|=\sqrt{\sum_{j=0}^{2^Q-1}\sum_{k=1}^{2}Z_{j,k}^2}.

Setting Z^2:=∑j=0μ−1∑k=12Zj,k2\hat{Z}^2:=\sum_{j=0}^{\mu-1}\sum_{k=1}^{2}Z_{j,k}^2 and Zˇ2:=∑j=μ2Q−1∑k=12Zj,k2\check{Z}^2:=\sum_{j=\mu}^{2^Q-1}\sum_{k=1}^{2}Z_{j,k}^2, the initial fidelity f(0)f(0) is then given by the random variable Z^2Z^2+Zˇ2\frac{\hat{Z}^2}{\hat{Z}^2+\check{Z}^2}. We also note that Z^2\hat{Z}^2 is χ2(2μ)\chi^2(2\mu)-distributed and Zˇ2\check{Z}^2 is χ2(2Q+1−2μ)\chi^2(2^Q+1-2\mu)-distributed. Using that the Beta(α,β)(\alpha,\beta) distribution can be expressed as XX+Y\frac{X}{X+Y} with X∼χ2(2α)X\sim\chi^2(2\alpha) and Y∼χ2(2β)Y\sim\chi^2(2\beta) [94], we conclude that the initial fidelity f(0)f(0) has distribution Beta(μ,2Q−μ)(\mu,2^Q-\mu). This implies that the expected initial fidelity is E(f(0))=μ2Q∝2−Q\mathbb{E}(f(0))=\frac{\mu}{2^Q}\propto2^{-Q}.

Utilising that the cumulative distribution function of the Beta(α,β)(\alpha,\beta)-distribution is the regularised incomplete beta-function Ix(α,β)I_x(\alpha,\beta), we also obtain that the probability of having an initial fidelity less than ϵ\epsilon satisfies

P(f(0)<ϵ)=Iϵ(μ,2Q−μ)=ϵμΓ(2Q)μΓ(μ)Γ(2Q−μ)+O(ϵμ+1).(4)P(f(0)<\epsilon)=I_{\epsilon}(\mu,2^Q-\mu)=\frac{\epsilon^\mu\Gamma(2^Q)}{\mu\Gamma(\mu)\Gamma(2^Q-\mu)}+O\left(\epsilon^{\mu+1}\right). \tag*{(4)}

Thus, for ϵ=c2−Q\epsilon=c2^{-Q} with an arbitrary constant c>0c>0, we observe

P(f(0)<ϵ)<(ϵ2Q)μμ!+O(ϵμ+1)=cμμ!+O(cμ+12−Q(μ+1)).(5)P(f(0)<\epsilon)<\frac{(\epsilon2^Q)^\mu}{\mu!}+O\left(\epsilon^{\mu+1}\right)=\frac{c^\mu}{\mu!}+O\left(c^{\mu+1}2^{-Q(\mu+1)}\right). \tag*{(5)}

Hence, we can ensure that the probability P(f(0)<c2−Q)P(f(0)<c2^{-Q}) is arbitrarily small, i.e., f(0)∈Ω(2−Q)f(0)\in\Omega(2^{-Q}) holds with probability 1. This can be interpreted as satisfying f(0)∝2−Qf(0)\propto2^{-Q} or better with probability 1.

Combinatorial Optimisation

In the case of combinatorial optimisation problems, we can refine the convergence results above. By combinatorial optimisation problems we mean Hamiltonians that are sums of tensor products of Pauli-Z operators. Thus, every individual measurement in the Pauli-Z-basis on the quantum device is a viable candidate for the solution. Hence, we generally don’t need to ensure that the solution fidelity reaches 1, but only a threshold ε\varepsilon. E.g., when using SS many shots (individual measurements), we can express the threshold fidelity ε\varepsilon in terms of the number of shots SS as ε=κ/S\varepsilon= \kappa/S for some κ>0\kappa> 0 which we assume constant when varying SS. Then, the single-shot success probability at the fidelity threshold is given by κ/S\kappa/S. This implies that the multi-shot success probability (at least one single-shot success) is given by 1−(1−κ/S)S1 - (1 - \kappa/S)^S which converges to 1−e−κ1 - e^{-\kappa} for S→∞S \to\infty. In other words, a multi-shot success probability pS=1−(1−κ/S)S≈1−e−κp_S = 1 - (1 - \kappa/S)^S \approx1 - e^{-\kappa} arbitrarily close to 1 can be chosen by setting κ=−ln⁡(1−pS)\kappa= -\ln(1 - p_S) and choosing SS sufficiently large that the error in (1−κ/S)S≈e−κ(1 - \kappa/S)^S \approx e^{-\kappa} is negligible.

The initial state can easily be prepared to be an equal superposition of all computational basis states, i.e., ∀j:αj(0)=2−Q/2\forall j : \alpha_j(0) = 2^{-Q/2}. This implies for the single-shot success probability p(t)=∑j=0μ−1∣αj(t)∣2≥11+2Qμ−1e−2tΔp(t) = \sum_{j=0}^{\mu-1} \lvert\alpha_j(t)\rvert^2 \ge\frac{1}{1+2^Q\mu^{-1}e^{-2t\Delta}}. Thus, the multi-shot success probability threshold pS=1−e−κp_S = 1 - e^{-\kappa} is approximately reached when p(t)≥ε=κ/Sp(t) \ge\varepsilon= \kappa/S. Finally, this is guaranteed for t≥Qln⁡2−ln⁡μ+ln⁡ε−ln⁡(1−ε)2Δt \ge\frac{Q\ln2-\ln\mu+\ln\varepsilon-\ln(1-\varepsilon)}{2\Delta} which scales linearly in Q/ΔQ/\Delta.

Complexity Analysis

Knowing that ITE can reach the solution in linear time up to bounded errors, we still need to consider whether or not the ITE can be efficiently implemented. In full generality, the answer is likely no. However, we will see that it is possible for bounded order systems. Multiple approaches to implementing ITE exist [62, 63, 64, 65, 69, 79], however for the purposes of this complexity analysis, the finer details are not relevant. Instead, we will use a general circuit construction technique based on dimensional expressivity analysis [41, 95] because it provides additional information that simplifies the complexity analysis.

Bounded Order Systems

We assume a bounded order system, that is, the Hamiltonian is a sum H=∑iaiSiH = \sum_i a_i S_i where each SiS_i is a bounded tensor product of Pauli-operators and the aia_i scale at most polynomially with the number of qubits. This means that there exists a constant BB such that all SiS_i are tensor products of at most BB many non-identity Paulis. Hence, there are at most 3B(QB)3^B \binom{Q}{B} many SiS_i in HH.

Trotterisation

The time evolution e−tHe^{-tH} is then trotterised [96] as ∏τ=1t/δ∏ie−δaiSi\prod_{\tau=1}^{t/\delta} \prod_i e^{-\delta a_i S_i} using small time-steps δ\delta, i.e., there are O(QB⋅t/δ)O(Q^B \cdot t/\delta) many individual factors. The main complexity question therefore becomes whether or not gates acting as the e−δaiSie^{-\delta a_i S_i} can be found efficiently.

Considering the e−δaiSie^{-\delta a_i S_i} in the τ\tau-layer of the expansion, let ∣ψi,τ⟩|\psi_{i,\tau}\rangle be the corresponding state of the quantum device immediately prior to the e−δaiSie^{-\delta a_i S_i} operation. Up to normalisation, the step of the evolution e−δaiSi∣ψi,τ⟩e^{-\delta a_i S_i}|\psi_{i,\tau}\rangle can then be expressed in terms of a parametric quantum circuit Ci,τ(θi,τ)C_{i,\tau}(\theta_{i,\tau}) acting on ∣ψi,τ⟩|\psi_{i,\tau}\rangle. The exact number of gates in Ci,τC_{i,\tau} depends on the compilation approach, but a general purpose circuit of depth 5⋅2B−1−25 \cdot2^{B-1}-2 with θi,τ∈R2B+1−1\theta_{i,\tau}\in\mathbb{R}^{2^{B+1}-1} can be constructed [95] and, using symmetry arguments, much simpler circuits using only up to 4B4^{B} Pauli-rotation gates (which can be compiled with polynomial depth in the error bound by the Solovay–Kitaev theorem) but incurring an O(δ2)O(\delta^{2})-error are known [64, 65]. These are constant bounds as BB is a constant and hence we conclude that the ITE of a Hamiltonian with order bound BB can be compiled into a quantum circuit of O(QB⋅t/δ)O(Q^{B}\cdot t/\delta) depth.

Trotterisation Error

Using the normal Trotter error e−δH−∏ie−δaiSi∈O(δ2)e^{-\delta H}-\prod_i e^{-\delta a_iS_i}\in O(\delta^2), it is not immediately obvious, how the error propagates when the normalisation is added to each e−δaiSie^{-\delta a_iS_i} step. To analyse this error propagation, we first consider the single-Trotter-step error followed by the integrated error on the interval [0,t][0,t].

For the single-Trotter-step analysis, we first note that

∏iCi,τ(θi,τ)∣ψ(τδ)⟩=∏ie−δaiSi∣ψ(τδ)⟩∥∏ie−δaiSi∣ψ(τδ)⟩∥=∏ie−δaiSi∣ψ(τδ)⟩∥e−δH∣ψ(τδ)∥+O(δ2).(6)\prod_i C_{i,\tau}(\theta_{i,\tau})|\psi(\tau\delta)\rangle = \frac{\prod_i e^{-\delta a_iS_i}|\psi(\tau\delta)\rangle}{\left\|\prod_i e^{-\delta a_iS_i}|\psi(\tau\delta)\rangle\right\|} = \frac{\prod_i e^{-\delta a_iS_i}|\psi(\tau\delta)\rangle}{\left\|e^{-\delta H}|\psi(\tau\delta)\right\|+O(\delta^2)}. \tag*{(6)}

Defining ev⁡min⁡(M)\operatorname{ev}_{\min}(M) and ev⁡max⁡(M)\operatorname{ev}_{\max}(M) as the smallest and largest eigenvalues (resp.) of a diagonalisable matrix MM, we observe ∥e−δH∣ψ(τδ)⟩∥≥ev⁡min⁡(e−δH)=e−δev⁡max⁡(H)\left\|e^{-\delta H}|\psi(\tau\delta)\rangle\right\|\geq\operatorname{ev}_{\min}(e^{-\delta H})=e^{-\delta\operatorname{ev}_{\max}(H)} since ∥∣ψ(τδ)⟩∥=1\||\psi(\tau\delta)\rangle\|=1. The polynomial scaling assumption of the aia_i in the definition of bounded order systems then implies that ev⁡max⁡(H)≤∑i∣ai∣∈O(poly⁡(Q))\operatorname{ev}_{\max}(H)\leq\sum_i|a_i|\in O(\operatorname{poly}(Q)). Thus, restricting δ\delta to 0<δ≤δ^:=ln⁡γ∑i∣ai∣0<\delta\leq\hat{\delta}:=\frac{\ln\gamma}{\sum_i|a_i|} for arbitrary γ>1\gamma>1 yields ∥e−δH∣ψ(τδ)⟩∥≥γ−1\left\|e^{-\delta H}|\psi(\tau\delta)\rangle\right\|\geq\gamma^{-1} in a region of no more than polynomially decaying size for δ\delta. The same δ≤δ^\delta\leq\hat{\delta} condition also implies ∥∏ie−δaiSi∣ψ(τδ)⟩∥≥γ−1\left\|\prod_i e^{-\delta a_iS_i}|\psi(\tau\delta)\rangle\right\|\geq\gamma^{-1} and thus

∏iCi,τ(θi,τ)∣ψ(τδ)⟩=∏ie−δaiSi∣ψ(τδ)⟩∥e−δH∣ψ(τδ)⟩∥+O(δ2)=∏ie−δaiSi∣ψ(τδ)⟩∥e−δH∣ψ(τδ)⟩∥+O(δ2)=e−δH∣ψ(τδ)⟩+O(δ2)∥e−δH∣ψ(τδ)⟩∥+O(δ2)(7)\begin{aligned} \prod_i C_{i,\tau}(\theta_{i,\tau})|\psi(\tau\delta)\rangle &=\frac{\prod_i e^{-\delta a_iS_i}|\psi(\tau\delta)\rangle}{\|e^{-\delta H}|\psi(\tau\delta)\rangle\|+O(\delta^2)} =\frac{\prod_i e^{-\delta a_iS_i}|\psi(\tau\delta)\rangle}{\|e^{-\delta H}|\psi(\tau\delta)\rangle\|}+O(\delta^2)\\ &=\frac{e^{-\delta H}|\psi(\tau\delta)\rangle+O(\delta^2)}{\|e^{-\delta H}|\psi(\tau\delta)\rangle\|}+O(\delta^2) \tag*{(7)} \end{aligned}

which finally implies

∥e−δH∣ψ(τδ)⟩∥e−δH∣ψ(τδ)⟩∥−∏iCi,τ(θi,τ)∣ψ(τδ)⟩∥≤∥γO(δ2)+O(δ2)∥≤(γ+1)O(δ2).(8)\left\|\frac{e^{-\delta H}|\psi(\tau\delta)\rangle}{\|e^{-\delta H}|\psi(\tau\delta)\rangle\|}-\prod_i C_{i,\tau}(\theta_{i,\tau})|\psi(\tau\delta)\rangle\right\| \leq\left\|\gamma O(\delta^2)+O(\delta^2)\right\| \leq(\gamma+1)O(\delta^2). \tag*{(8)}

In other words, the impact of the normalisation is limited to a change in the constant of the single-Trotter-step error if the step-size has a bound that decays polynomially for bounded order systems.

The integrated Trotter error is then obtained by executing tδ−1t\delta^{-1} many consecutive single Trotter steps that each have the (γ+1)O(δ2)(\gamma+1)O(\delta^2) bound. Hence, the second Trotter step already starts in a state ∣ψ~(δ)⟩=∣ψ(δ)⟩+(γ+1)O(δ2)\lvert\widetilde{\psi}^{(\delta)}\rangle=\lvert\psi^{(\delta)}\rangle+(\gamma+1)O(\delta^2). Considering therefore a τ(γ+1)O(δ2)\tau(\gamma+1)O(\delta^2) error on the state at time τδ\tau\delta, we obtain

∥e−δH∣ψ(τδ)⟩∥e−δH∣ψ(τδ)⟩∥−∏iCi,τ(θi,τ)(∣ψ(τδ)⟩+τ(γ+1)O(δ2))∥≤(τ+1)(γ+1)O(δ2).(9)\left\lVert\frac{e^{-\delta H}\lvert\psi(\tau\delta)\rangle}{\lVert e^{-\delta H}\lvert\psi(\tau\delta)\rangle\rVert}-\prod_i C_{i,\tau}(\theta_{i,\tau})\left(\lvert\psi(\tau\delta)\rangle+\tau(\gamma+1)O(\delta^2)\right)\right\rVert\leq(\tau+1)(\gamma+1)O(\delta^2). \tag*{(9)}

By induction, the accumulated Trotter error over τ\tau many steps is (γ+1)τO(δ2)(\gamma+1)\tau O(\delta^2), and since there are τ=tδ−1\tau=t\delta^{-1} many Trotter steps in total, the integrated Trotter error becomes (γ+1)tO(δ)=O(Qδ/Δ)(\gamma+1)tO(\delta)=O(Q\delta/\Delta).

In other words, controlling the Trotter error implies a step-size decay in O((Q/Δ)−1)O((Q/\Delta)^{-1}) and O(δ^)=O(1poly⁡(Q))O(\hat{\delta})=O\left(\frac{1}{\operatorname{poly}(Q)}\right), which are both polynomial in Q/ΔQ/\Delta.

Finding Optimal Parameters

The circuit compilation requires us to find the optimal values θi,τ\theta_{i,\tau}. For example, this can be done by maximising Ω(δ,θi,τ)=⟨ψi,τ∣(cosh⁡(δai)−sinh⁡(δai)Si)Ci,τ(θi,τ)∣ψi,τ⟩\Omega(\delta,\theta_{i,\tau})=\langle\psi_{i,\tau}\lvert(\cosh(\delta a_i)-\sinh(\delta a_i)S_i)C_{i,\tau}(\theta_{i,\tau})\rvert\psi_{i,\tau}\rangle. Using the circuit Ci,τC_{i,\tau} obtained from dimensional expressivity analysis [41] applied to the simpler rotation-gate only circuits [64, 65], Ω(δ,θi,τ)\Omega(\delta,\theta_{i,\tau}) is a polynomial in the variables sj=sin⁡θi,τ,j2s_j=\sin\frac{\theta_{i,\tau,j}}{2} and cj=cos⁡θi,τ,j2c_j=\cos\frac{\theta_{i,\tau,j}}{2}. Thus, ∂θi,τΩ(δ,θi,τ)\partial_{\theta_{i,\tau}}\Omega(\delta,\theta_{i,\tau}) expressed in the sjs_j and cjc_j variables together with the conditions sj2+cj2−1=0s_j^2+c_j^2-1=0 defines a system h(δ,(s,c))=0h(\delta,(s,c))=0 of polynomial equations. Here, hh is a homotopy with trivial solution h(0,(0,1))=0h(0,(0,1))=0 and ∂(s,c)h(0,(0,1))≠0\partial_{(s,c)}h(0,(0,1))\ne0 by construction of Ci,τC_{i,\tau} [41, 95]. Following the proof of the implicit function theorem, polynomial bounds on the step-size δ\delta, which only depend on BB, Ci,τC_{i,\tau}, and at most 4B(Q)4^B(Q) many ⟨ψ∣σ∣ψ⟩\langle\psi\lvert\sigma\lvert\psi\rangle, where σ\sigma is a Pauli-operator acting non-trivially on at most BB many qubits, can be obtained. In fact, using seamless switching [41], a minimum viable step-size δ\delta can be guaranteed. Furthermore, the single-shot measurement of ⟨ψ∣σ∣ψ⟩\langle\psi\lvert\sigma\lvert\psi\rangle is a random variable with standard deviation ≤1\leq1, and thus probabilistic error bounds on the multi-shot expectation of ⟨ψ∣σ∣ψ⟩\langle\psi\lvert\sigma\lvert\psi\rangle scale like (number shots)−1/2(\text{number shots})^{-1/2}. Hence, the quantum resource requirements scale polynomially with respect to error bound requirements and number of qubits. Using homotopy continuation methods [97, 98], the circuit for Ci,τ(θi,τ)C_{i,\tau}(\theta_{i,\tau}) can be compiled in polynomial time, and only polynomially many steps of size δ\delta are required to reach the total required evolution time tt. As tt scales linearly in Q/ΔQ/\Delta, this completes the proof of Theorem 1.

Single-Qubit Example

To illustrate the compilation process more clearly, we will consider an explicit single-qubit combinatorial optimisation example. In this case, the Hamiltonian is chosen to be H=aZH=aZ and the initial state ∣ψ(0)⟩=α0(0)∣0⟩+α1(0)∣1⟩\lvert\psi(0)\rangle=\alpha_0(0)\lvert0\rangle+\alpha_1(0)\lvert1\rangle. We chose a combinatorial optimisation Hamiltonian because it allows us to use additional symmetries, namely that we can initialise ∣ψ(0)⟩\lvert\psi(0)\rangle with real amplitudes, e.g., with α0(0)=α1(0)=12\alpha_0(0)=\alpha_1(0)=\frac{1}{\sqrt{2}}, and since e−taZe^{-taZ} is a real operator, ∣ψ(t)⟩|\psi(t)\rangle will always have real amplitudes. Thus, the compiled circuit can be constructed to preserve real amplitudes as well. In this case, the ITE can be computed analytically, and we obtain e−taZ∣ψ(0)⟩=e−ta2∣0⟩+eta2∣1⟩e^{-taZ}|\psi(0)\rangle= \frac{e^{-ta}}{\sqrt{2}}|0\rangle+ \frac{e^{ta}}{\sqrt{2}}|1\rangle. Adding the normalisation yields ∥e−taZ∣ψ(0)⟩∥=cosh⁡(2ta)\lVert e^{-taZ}|\psi(0)\rangle\rVert= \sqrt{\cosh(2ta)}, i.e.,

∣ψ(t)⟩=e−ta2cosh⁡(2ta)∣0⟩+eta2cosh⁡(2ta)∣1⟩.(10)|\psi(t)\rangle= \frac{e^{-ta}}{\sqrt{2\cosh(2ta)}}|0\rangle+ \frac{e^{ta}}{\sqrt{2\cosh(2ta)}}|1\rangle. \tag*{(10)}

Circuit Ansatz

For the circuit compilation, we can use dimensional expressivity analysis [41, 95] to obtain that C(θ)=RY(θ)C(\theta)=R_Y(\theta) is a minimal and maximally expressive circuit on the real submanifold of the single-qubit state space manifold. This means that any ∣ψ((τ+1)δ)⟩|\psi((\tau+1)\delta)\rangle can be expressed as C(θτ)∣ψ(τδ)⟩C(\theta_\tau)|\psi(\tau\delta)\rangle (maximally expressive), i.e., that the action of the ITE can be implemented by that circuit, and that any parametric quantum circuit with fewer parameters no longer guarantees the implementability of the ITE (minimality). Of course, in this simple example, dimensional expressivity analysis isn’t required to obtain this knowledge, but in general, a minimal and maximally expressive circuit needs to be constructed and dimensional expressivity analysis is a useful tool to achieve that.

Homotopy Setup

Using C(θ)=RY(θ)C(\theta)=R_Y(\theta), the overlap function becomes

Ω(δ,θτ)=⟨ψτ∣(cosh⁡(δa)−sinh⁡(δa)Z)RY(θτ)∣ψτ⟩=cosh⁡(δa)cos⁡θτ2−sinh⁡(δa)⟨ψτ∣Z∣ψτ⟩cos⁡θτ2−cosh⁡(δa)⟨ψτ∣iY∣ψτ⟩sin⁡θτ2+sinh⁡(δa)⟨ψτ∣X∣ψτ⟩sin⁡θτ2.(11)\begin{aligned} \Omega(\delta,\theta_\tau) &= \langle\psi_\tau|(\cosh(\delta a)-\sinh(\delta a)Z)R_Y(\theta_\tau)|\psi_\tau\rangle\\ &= \cosh(\delta a)\cos\frac{\theta_\tau}{2}-\sinh(\delta a)\langle\psi_\tau|Z|\psi_\tau\rangle\cos\frac{\theta_\tau}{2}\\ &\quad-\cosh(\delta a)\langle\psi_\tau|iY|\psi_\tau\rangle\sin\frac{\theta_\tau}{2}+\sinh(\delta a)\langle\psi_\tau|X|\psi_\tau\rangle\sin\frac{\theta_\tau}{2}. \tag*{(11)} \end{aligned}

Noting that ∣ψτ⟩|\psi_\tau\rangle having real amplitudes implies ⟨ψτ∣iY∣ψτ⟩=0\langle\psi_\tau|iY|\psi_\tau\rangle=0, we can define ω1:=sinh⁡(δa)⟨ψτ∣X∣ψτ⟩\omega_1:=\sinh(\delta a)\langle\psi_\tau|X|\psi_\tau\rangle and ω2:=cosh⁡(δa)−sinh⁡(δa)⟨ψτ∣Z∣ψτ⟩\omega_2:=\cosh(\delta a)-\sinh(\delta a)\langle\psi_\tau|Z|\psi_\tau\rangle to simplify notation to Ω=ω1sin⁡θτ2+ω2cos⁡θτ2\Omega=\omega_1\sin\frac{\theta_\tau}{2}+\omega_2\cos\frac{\theta_\tau}{2}. This overlap function needs to be maximised, i.e., θτ\theta_\tau is a solution to 2∂θτΩ=ω1cos⁡θτ2−ω2sin⁡θτ2=02\partial_{\theta_\tau}\Omega=\omega_1\cos\frac{\theta_\tau}{2}-\omega_2\sin\frac{\theta_\tau}{2}=0. Since we also know that δ=0\delta=0 implies θτ=0\theta_\tau=0, we can understand the overlap condition as a homotopy in (δ,θτ)(\delta,\theta_\tau). Introducing the substitutions c=cos⁡θτ2c=\cos\frac{\theta_\tau}{2} and s=sin⁡θτ2s=\sin\frac{\theta_\tau}{2}, this yields the homotopy continuation problem

h(δ,(s,c))=(ω1c−ω2ss2+c2−1)(12)h(\delta,(s,c))= \begin{pmatrix} \omega_1 c-\omega_2 s\\ s^2+c^2-1 \end{pmatrix} \tag*{(12)}
h(0,(0,1))=0.h(0,(0,1))=0.

General Homotopy Continuation

It is possible to solve this homotopy continuation problem analytically. We will do this in the next section. However, in general, numerical methods will be required, so in this section, we will discuss how to numerically solve the homotopy continuation problem.

A reasonably simple approach to solving a homotopy problem is to follow the proof of the implicit function theorem. Doing so, we extend the homotopy by defining h^(δ,(s,c)):=(δ,h(δ,(s,c)))T\hat{h}(\delta,(s,c)) := (\delta,h(\delta,(s,c)))^{T} and noting

det⁡h^′(δ,(s,c))=det⁡(100ω11c−ω21s−ω2ω102s2c)=−2cω2−2sω1.\det\hat{h}'(\delta,(s,c)) = \det\begin{pmatrix} 1 & 0 & 0 \\ \omega_{1}^{1}c-\omega_{2}^{1}s & -\omega_{2} & \omega_{1} \\ 0 & 2s & 2c \end{pmatrix} = -2c\omega_{2}-2s\omega_{1}.

Thus, det⁡h^′(0,(0,1))=−2\det\hat{h}'(0,(0,1))=-2 implies invertibility of h^\hat{h} in a neighbourhood of (0,(0,1))(0,(0,1)). This neighbourhood depends polynomially on ss and cc, and implicitly on δ\delta via ω1\omega_{1} and ω2\omega_{2}. However, the δ\delta-dependence in ω1\omega_{1} and ω2\omega_{2} is given by cosh⁡(δa)\cosh(\delta a) and sinh⁡(δa)\sinh(\delta a) terms which are bounded by constants through the δ<δ^=ln⁡γa\delta< \hat{\delta} = \frac{\ln\gamma}{a} condition introduced in the Trotterisation Error section. Thus, the invertibility region is of polynomially decaying size.

Remark 1. The general case as discussed in the Finding Optimal Parameters section has the same structure. The only difference is that there are polynomially many sjs_j and cjc_j variables, thus the determinant is a higher order polynomial is sjs_j and cjc_j. However, the determinant remains a polynomial, and thus the invertibility region remains of polynomially decaying size provided that the determinant is non-zero at the starting point. Here, we could simply confirm the starting point having non-vanishing determinant, but in the general case this is a necessary consequence of the minimality assumption of the circuit ansatz because dimensional expressivity analysis implies that the homotopy image must be lower dimensional if any parameter is removed, i.e., none of the rows or columns in h^′(0,(0,1))\hat{h}'(0,(0,1)) can be linearly dependent on the rest.

It follows that the implicit function f(δ)f(\delta) with h^′(δ,f(δ))=0\hat{h}'(\delta,f(\delta))=0 exists and it satisfies

f′(δ)=−(∂(s,c)h(δ,(s,c)))−1∂δh(δ,(s,c))∣(s,c)=f(δ)(13)f'(\delta)=-\left(\partial_{(s,c)}h(\delta,(s,c))\right)^{-1}\partial_{\delta}h(\delta,(s,c))\bigg|_{(s,c)=f(\delta)} \tag*{(13)}

f(0)=(0,1)f(0)=(0,1).

This is an implicit ordinary differential equation in two dimensions (in general the dimension is twice the dimension of θτ\theta_{\tau}) and can be solved with a variety of methods. The error scaling here clearly depends on the chosen numerical scheme. For general order bounds BB as defined in the Bounded Order Systems section, this also directly leads to precision requirements on the expectation values of the at most 4B(B)(Q)4B^{(Q)}_{(B)} many ⟨ψ∣σ∣ψ⟩\langle\psi|\sigma|\psi\rangle used to set up the general homotopy in the Finding Optimal Parameters section.

A minimum viable step-size can be obtained from picking a rectangle that is fully contained in the invertibility region. For example, we may restrict ∣θτ∣≤π4|\theta_{\tau}|\leq\frac{\pi}{4}, i.e., 0≤∣s∣≤12≤c≤10\leq|s|\leq\frac{1}{\sqrt{2}}\leq c\leq1, and compute an upper bound on ∥f′(δ)∥\lVert f'(\delta)\rVert for 0≤δ≤δ^=ln⁡γa0\leq\delta\leq\hat{\delta}=\frac{\ln\gamma}{a}.

Doing so will provide a lower bound δˇ\check{\delta} on δ\delta for f(δ)=(s(δ),c(δ))Tf(\delta)=(s(\delta),c(\delta))^{T} to reach the boundaries of 0≤∣s∣≤12≤c≤10 \leq|s| \leq\frac{1}{\sqrt{2}} \leq c \leq1. The minimum between δˇ\check{\delta} and δ^\hat{\delta} is then the minimum viable step-size.

Analytic Homotopy Continuation

While the general homotopy continuation as discussed in the previous section is generally applicable, Equation (12) can be solved more easily for the purposes of this example. Let us first restrict ∣θτ∣<π|\theta_\tau| < \pi for each Trotter step. This implies c>0c > 0, i.e., c=1−s2c = \sqrt{1-s^2}. Then, we simply need to solve ω1c−ω2s=0\omega_1 c-\omega_2 s=0, i.e., s2=ω12ω12+ω22s^2=\frac{\omega_1^2}{\omega_1^2+\omega_2^2}. Using ω1(δ=0)=0\omega_1(\delta=0)=0, ω2(δ=0)=1\omega_2(\delta=0)=1, c(δ=0)=1c(\delta=0)=1, and s(δ=0)=0s(\delta=0)=0, we obtain from ω1c−ω2s=0\omega_1 c-\omega_2 s=0 that ss and ω1\omega_1 need to have the same sign near δ=0\delta=0, i.e., s=ω1ω12+ω22s=\frac{\omega_1}{\sqrt{\omega_1^2+\omega_2^2}}. We note that ∣s∣<1|s|<1 holds for all δ\delta. This implies that the restriction ∣θτ∣<π|\theta_\tau|<\pi is also satisfied for all δ\delta.

For the first Trotter step, we know that ∣ψ0⟩=∣0⟩+∣1⟩2|\psi_0\rangle=\frac{|0\rangle+|1\rangle}{\sqrt{2}}, i.e., ω1=sinh⁡(δa)\omega_1=\sinh(\delta a) and ω2=cosh⁡(δa)\omega_2=\cosh(\delta a). Using RY(θ0)=c−isYR_Y(\theta_0)=c-isY, we obtain

∣ψ1⟩=RY(θ0)∣ψ0⟩=(1−s2−s)∣0⟩+(1−s2+s)∣1⟩2=e−δa2cosh⁡(2δa)∣0⟩+eδa2cosh⁡(2δa)∣1⟩=∣ψ(δ)⟩.(14)|\psi_1\rangle=R_Y(\theta_0)|\psi_0\rangle=\frac{(\sqrt{1-s^2}-s)|0\rangle+(\sqrt{1-s^2}+s)|1\rangle}{\sqrt{2}} =\frac{e^{-\delta a}}{\sqrt{2\cosh(2\delta a)}}|0\rangle+\frac{e^{\delta a}}{\sqrt{2\cosh(2\delta a)}}|1\rangle=|\psi(\delta)\rangle. \tag*{(14)}

Thus, since we didn’t have to do any Trotter splitting in this simple example, we obtain that a single Trotter step can be performed for arbitrarily large times and solves the ITE exactly.

Discussion

First and foremost, it should be noted that many decisions about the quantum circuit compilation are made in this article because they introduce the necessary regularity providing us with polynomial bounds. These bounds are by no means sharp and better performing circuits can be constructed in practice [41, 62, 63, 64, 65, 69, 71, 72, 73, 74, 75, 76, 77, 79, 95].

As such, we have shown that bounded order systems can be solved (up to arbitrary bounded error) using ITE with an evolution time that scales linearly in the number of qubits and inverse energy gap Q/ΔQ/\Delta. Furthermore, we have shown that this ITE can be compiled into a quantum circuit with depth scaling polynomially in Q/ΔQ/\Delta and the compilation effort scales polynomially in Q/ΔQ/\Delta as well. This explicit polynomial scaling of the circuit construction, circuit depth, and required evolution time in qubits is what we mean by “efficient”.

This efficiency claim in terms of qubits needs to be understood in context. Similar to the classical complexity classes P and NP, there are quantum complexity analogues BQP (bounded-error quantum polynomial time) and QMA (Quantum Merlin Arthur or “quantum NP”). Considering only the linear scaling in qubits without taking the inverse energy gap scaling into account, Theorem 1 at first glance seems to indicate that bounded order systems are in BQP. However, this would be quite an extraordinary claim. The class of bounded order systems considered here contains the class of kk-local Hamiltonians, and the kk-local Hamiltonian problem is known to be QMA-complete [90], even for k=2k = 2. Thus, one might hastily conclude BQP=QMA, i.e., the quantum analogue of P=NP. This does not follow from Theorem 1. Instead, we are exploiting that the physically relevant manifold of states only grows polynomially in the number of qubits for local Hamiltonians which allows for an efficient compilation and simulation on a quantum computer [99].

The efficiency claim of Theorem 1 is more akin to pseudo-polynomial complexity with respect to the inverse energy gap. The inverse energy gap can have superpolynomial growth in the number of qubits for arbitrary sequences of bounded order systems. Similarly, the assumption that the coefficients aia_i have no worse than polynomial scaling is required as otherwise we cannot conclude that the ITE step size δ\delta scales polynomially. We would only obtain the polynomial scaling for each δai\delta a_i. Otherwise, the Hamiltonian could always be rescaled to have an energy gap Δ=1\Delta= 1 which would allow us to prove NP⊆\subseteqBQP. Although there is no conclusive evidence, this is unlikely to be true [100] and it does not follow from Theorem 1.

Nevertheless, true polynomial scaling is obtained if the sequence of systems has “well-behaved” energy gap scaling. This class of systems includes suitable discretisations of a gapped continuum theory, truncations of gapped systems, as well as many combinatorial optimisation problems. Thus, although “bad” systems exist, the here shown results are applicable to many highly relevant problems such as in physics [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12], chemistry and drug design [13, 14, 15, 16, 17, 18], quantum machine learning [19, 20, 21, 22, 23, 24, 25, 26, 27, 29, 30] [28], and combinatorial optimisation [31, 32, 33, 34, 35, 36, 37, 38, 40] [39].

Acknowledgements

The authors would like to thank Yahui Chai and Stefan Kühn for fruitful discussions. The authors would also like to thank the anonymous reviewer who pointed out an improved rate of convergence argument leading to Equation (3).

Funding Statements

T.H. declares no relevant funding. K.J. discloses support for the research of this work from the European Union’s Horizon Europe Framework Programme (HORIZON) under the ERA Chair scheme with grant agreement no. 101087126 and the Ministry of Science, Research and Culture of the State of Brandenburg within the Centre for Quantum Technologies and Applications (CQTA).

Competing Interests Statements

All authors declare no competing interests.

Data Availability Statements

Data Availability Statements. Data sharing not applicable to this article as no datasets were generated or analysed during the current study.

Author Contributions

Author Contributions. Conceptualization (T.H. lead, K.J. supporting), Methodology (T.H./K.J. equal), Validation (K.J. lead, T.H. supporting), Formal analysis (T.H. lead, K.J. supporting), Investigation (T.H./K.J. equal), Writing - Original Draft (T.H. lead, K.J. supporting), Writing - Review & Editing (T.H./K.J. equal), Funding acquisition (K.J. lead)

All authors have approved the submitted version of the manuscript.

References

  1. [1]Feynman, R.P.: Simulating physics with computers. International Journal of Theoretical Physics 21, 467–488 (1982)
  2. [2]Funcke, L., Hartung, T., Jansen, K., Kühn, S., Schneider, M., Stornati, P., Wang, X.: Towards quantum simulations in particle physics and beyond on noisy intermediate-scale quantum devices. Philosophical Transactions of the Royal Society A 380, 20210062 (2022)DOI
  3. [3]Funcke, L., Hartung, T., Jansen, K., Kühn, S.: Review on quantum computing for lattice field theory. PoS LATTICE2022, 228 (2023)DOI
  4. [4]Baňuls, M.C., Blatt, R., Catani, J., Celi, A., Cirac, J.I., Dalmonte, M., Fallani, L., Jansen, K., Lewenstein, M., Montangero, S., Muschik, C.A., Reznik, B., Rico, E., Tagliacozzo, L., Acoleyn, K.V., Verstraete, F., Wiese, U.-J., Wingate, M., Zakrzewski, J., Zoller, P.: Simulating lattice gauge theories within quantum technologies. The European Physical Journal D 75, 8 (2020)DOI
  5. [5]Di Meglio, A., et al.: Quantum Computing for High-Energy Physics: State of the Art and Challenges. PRX Quantum 5(3), 037001 (2024) https://doi.org/10. 1103/PRXQuantum.5.037001 arXiv:2307.03236 [quant-ph]
  6. [6]Abrams, D.S., Lloyd, S.: Simulation of many-body fermi systems on a universal quantum computer. Phys. Rev. Lett. 79, 2586–2589 (1997) https://doi.org/10.1103/PhysRevLett.79.2586
  7. [7]Lloyd, S.: Universal quantum simulators. Science 273(5278), 1073–1078 (1996) https://doi.org/10.1126/science.273.5278.1073 https://www.science.org/doi/pdf/10.1126/science.273.5278.1073
  8. [8]Klco, N., Dumitrescu, E.F., McCaskey, A.J., Morris, T.D., Pooser, R.C., Sanz, M., Solano, E., Lougovski, P., Savage, M.J.: Quantum-classical computation of schwinger model dynamics using quantum computers. Phys. Rev. A 98, 032331 (2018) https://doi.org/10.1103/PhysRevA.98.032331
  9. [9]Klco, N., Savage, M.J., Stryker, J.R.: Su(2) non-abelian gauge field theory in one dimension on digital quantum computers. Phys. Rev. D 101, 074512 (2020) https://doi.org/10.1103/PhysRevD.101.074512
  10. [10]Ciavarella, A., Klco, N., Savage, M.J.: Trailhead for quantum simulation of su(3) yang-mills lattice gauge theory in the local multiplet basis. Phys. Rev. D 103, 094501 (2021) https://doi.org/10.1103/PhysRevD.103.094501
  11. [11]Clemente, G., Crippa, A., Jansen, K.: Strategies for the determination of the running coupling of (2 + 1)-dimensional qed with quantum computing. Phys. Rev. D 106, 114511 (2022) https://doi.org/10.1103/PhysRevD.106.114511
  12. [12]Bharti, K., Cervera-Lierta, A., Kyaw, T.H., Haug, T., Alperin-Lea, S., Anand, A., Degroote, M., Heimonen, H., Kottmann, J.S., Menke, T., Mok, W.-K., Sim, S., Kwek, L.-C., Aspuru-Guzik, A.: Noisy intermediate-scale quantum algorithms. Rev. Mod. Phys. 94, 015004 (2022) https://doi.org/10.1103/RevModPhys.94.015004
  13. [13]Aspuru-Guzik, A., Dutoi, A.D., Love, P.J., Head-Gordon, M.: Simulated quantum computation of molecular energies. Science 309(5741), 1704–1707 (2005) https://doi.org/10.1126/science.1113479 https://www.science.org/doi/pdf/10.1126/science.1113479
  14. [14]Kandala, A., Mezzacapo, A., Temme, K., Takita, M., Brink, M., Chow, J.M., Gambetta, J.M.: Hardware-efficient variational quantum eigensolver for small molecules and quantum magnets. Nature 549, 242–246 (2017)DOI
  15. [15]McArdle, S., Endo, S., Aspuru-Guzik, A., Benjamin, S.C., Yuan, X.: Quantum computational chemistry. Rev. Mod. Phys. 92, 015003 (2020) https://doi.org/10.1103/RevModPhys.92.015003
  16. [16]Kirsopp, J.L.M., Di Paola, C., Manrique, D.Z., Krompiec, M., Greene-Diniz, G., Guba, W., Meyder, A., Wolf, D., Strahm, M., Muñoz Ramo, D.: Quantum computational quantification of protein–ligand interactions. International Journal of Quantum Chemistry 122(22), 26975 (2022) https://doi.org/10.1002/qua.26975 https://onlinelibrary.wiley.com/doi/pdf/10.1002/qua.26975
  17. [17]Cao, Y., Romero, J., Aspuru-Guzik, A.: Potential of quantum computing for drug discovery. IBM Journal of Research and Development 62(6), 6–1620 (2018) https://doi.org/10.1147/JRD.2018.2888987
  18. [18]Flöther, F.F., Blankenberg, D., Demidik, M., Jansen, K., Krishnakumar, R., Krishnakumar, R., Laanait, N., Parida, L., Saab, C., Utro, F.: How quantum computing can enhance biomarker discovery (2024) arXiv:2411.10511 [q-bio.OT]DOI
  19. [19]Cerezo, M., Verdon, G., Huang, H.-Y., Cincio, L., Coles, P.J.: Challenges and opportunities in quantum machine learning. Nature Computational Science 2, 567–576 (2022)DOI
  20. [20]Zoufal, C., Lucchi, A., Woerner, S.: Variational quantum boltzmann machines. Quantum Machine Intelligence 3, 7 (2021)DOI
  21. [21]Larocca, M., Sauvage, F., Sbahi, F.M., Verdon, G., Coles, P.J., Cerezo, M.: Group-invariant quantum machine learning. PRX Quantum 3, 030341 (2022) https://doi.org/10.1103/PRXQuantum.3.030341
  22. [22]Meyer, J.J., Mularski, M., Gil-Fuster, E., Mele, A.A., Arzani, F., Wilms, A., Eisert, J.: Exploiting symmetry in variational quantum machine learning. PRX Quantum 4, 010328 (2023) https://doi.org/10.1103/PRXQuantum.4.010328
  23. [23]Sauvage, F., Larocca, M., Coles, P.J., Cerezo, M.: Building spatial symmetries into parameterized quantum circuits for faster training. Quantum Science and Technology 9(1), 015029 (2024) https://doi.org/10.1088/2058-9565/ad152e
  24. [24]Nguyen, Q.T., Schatzki, L., Braccia, P., Ragone, M., Coles, P.J., Sauvage, F., Larocca, M., Cerezo, M.: Theory for equivariant quantum neural networks. PRX Quantum 5, 020328 (2024) https://doi.org/10.1103/PRXQuantum.5.020328
  25. [25]Ragone, M., Braccia, P., Nguyen, Q.T., Schatzki, L., Coles, P.J., Sauvage, F., Larocca, M., Cerezo, M.: Representation Theory for Geometric Quantum Machine Learning. Preprint at https://arxiv.org/abs/2210.07980 (2023). https://doi.org/10.48550/arXiv.2210.07980
  26. [26]Wiersema, R., Kemper, A.F., Bakalov, B.N., Killoran, N.: Geometric quantum machine learning with horizontal quantum gates. Phys. Rev. Res. 7, 013148 (2025) https://doi.org/10.1103/PhysRevResearch.7.013148
  27. [27]Schatzki, L., Larocca, M., Nguyen, Q.T., Sauvage, F., Cerezo, M.: Theoretical guarantees for permutation-equivariant quantum neural networks. npj Quantum Abbas, A., Sutter, D., Zoufal, C., Lucchi, A., Figalli, A., Woerner, S.: The power of quantum neural networks. Nature Computat. Sci. 1, 403–409 (2021) https://doi.org/10.1038/s43588-021-00084-1 arXiv:2011.00027 [quant-ph]
  28. [29]Liu, J., Najafi, K., Sharma, K., Tacchino, F., Jiang, L., Mezzacapo, A.: Analytic theory for the dynamics of wide quantum neural networks. Phys. Rev. Lett. 130, 150601 (2023) https://doi.org/10.1103/PhysRevLett.130.150601
  29. [30]Zheng, H., Li, Z., Liu, J., Strelchuk, S., Kondor, R.: Speeding up learning quantum states through group equivariant convolutional quantum ansätze. PRX Quantum 4, 020327 (2023) https://doi.org/10.1103/PRXQuantum.4.020327
  30. [31]Gemeinhardt, F., Garmendia, A., Wimmer, M., Weder, B., Leymann, F.: Quantum combinatorial optimization in the nisq era: A systematic mapping study. ACM Comput. Surv. 56(3) (2023) https://doi.org/10.1145/3620668
  31. [32]Farhi, E., Goldstone, J., Gutmann, S., Lapan, J., Lundgren, A., Preda, D.: A quantum adiabatic evolution algorithm applied to random instances of an np-complete problem. Science 292(5516), 472–475 (2001) https://doi.org/10.1126/science.1057726 https://www.science.org/doi/pdf/10.1126/science.1057726
  32. [33]Crippa, A., Funcke, L., Hartung, T., Heinemann, B., Jansen, K., Kropf, A., Kühn, S., Meloni, F., Spataro, D., Tüysüz, C., Yap, Y.C.: Quantum algorithms for charged particle track reconstruction in the luxe experiment. Computing and Software for Big Science 7, 14 (2023)arxiv.org/abs/2304.01690
  33. [34]Chai, Y., Funcke, L., Hartung, T., Jansen, K., Kühn, S., Stornati, P., Stollenwerk, T.: Optimal flight-gate assignment on a digital quantum computer. Physical Review Applied 20, 064025 (2023)DOI
  34. [35]Zahedinejad, E., Zaribafiyan, A.: Combinatorial Optimization on Gate Model Quantum Computers: A Survey (2017) arXiv:1708.05294 [quant-ph]arxiv.org/abs/1708.05294
  35. [36]McGeoch, C.C., Wang, C.: Experimental evaluation of an adiabatic quantum system for combinatorial optimization. In: Proceedings of the ACM International Conference on Computing Frontiers. CF ’13. Association for Computing Machinery, New York, NY, USA (2013). https://doi.org/10.1145/2482767.2482797 . https://doi.org/10.1145/2482767.2482797
  36. [37]Morris, T.D., Kaushik, A., Roetteler, M., Lotshaw, P.C.: Performant near-term quantum combinatorial optimization (2024). https://arxiv.org/abs/2404.16135
  37. [38]Sankar, K., Scherer, A., Kako, S., Reifenstein, S., Ghadermarzy, N., Krayenhoff, W.B., Inui, Y., Ng, E., Onodera, T., Ronagh, P., Yoshihisa Yamamoto, Y.: A benchmarking study of quantum algorithms for combinatorial optimization. npj Schwägerl, T., Chai, Y., Hartung, T., Jansen, K., Kühn, S.: Benchmarking Variational Quantum Algorithms for Combinatorial Optimization in Practice. Quantum Mach. Intell. 8, 26 (2026)
  38. [40]Chicano, F., Luque, G., Dahi, Z.A., Gil-Merino, R.: Combinatorial optimization with quantum computers. Engineering Optimization 57(1), 208–233 (2025) https://doi.org/10.1080/0305215x.2024.2435538
  39. [41]Funcke, L., Hartung, T., Jansen, K., Kühn, S., Stornati, P.: Dimensional expressivity analysis of parametric quantum circuits. Quantum 5, 422 (2021) https://doi.org/10.22331/q-2021-03-29-422
  40. [42]Wang, X., Liu, J., Liu, T., Luo, Y., Du, Y., Tao, D.: Symmetric pruning in quantum neural networks. In: The Eleventh International Conference on Learning Representations (2023). https://openreview.net/forum?id=K96AogLDT2Karxiv.org/abs/2208.14057
  41. [43]Zheng, H., Li, Z., Strelchuk, S., Kondor, R., Liu, J.: Toward superpolynomial quantum speedup of equivariant quantum algorithms with SU(d) symmetry. Phys. Rev. A 112, 052435 (2025) https://doi.org/10.1103/pt27-v2nj
  42. [44]Farhi, E., Goldstone, J., Gutmann, S., Sipser, M.: Quantum computation by adiabatic evolution. Preprint at https://arxiv.org/abs/quant-ph/0001106 (2000). https://doi.org/10.48550/arXiv.quant-ph/0001106
  43. [45]Farhi, E., Goldstone, J., Gutmann, S.: A Quantum Approximate Optimization Algorithm. Preprint at https://arxiv.org/abs/1411.4028 (2014). https://doi.org/10.48550/arXiv.1411.4028
  44. [46]Choi, J., Kim, J.: A tutorial on quantum approximate optimization algorithm (qaoa): Fundamentals and applications. In: 2019 International Conference on Information and Communication Technology Convergence (ICTC), pp. 138–142 (2019). https://doi.org/10.1109/ICTC46691.2019.8939749
  45. [47]Zhou, L., Wang, S.-T., Choi, S., Pichler, H., Lukin, M.D.: Quantum approximate optimization algorithm: Performance, mechanism, and implementation on near-term devices. Phys. Rev. X 10, 021067 (2020) https://doi.org/10.1103/PhysRevX.10.021067
  46. [48]Streif, M., Yarkoni, S., Skolik, A., Neukart, F., Leib, M.: Beating classical heuristics for the binary paint shop problem with the quantum approximate optimization algorithm. Phys. Rev. A 104, 012403 (2021) https://doi.org/10.1103/PhysRevA.104.012403
  47. [49]Bode, T., Wilhelm, F.K.: Adiabatic bottlenecks in quantum annealing and nonequilibrium dynamics of paramagnons. Phys. Rev. A 110, 012611 (2024)DOI
  48. [50]Wang, Z., Zheng, P.-L., Wu, B., Zhang, Y.: Quantum dropout: On and over the hardness of quantum approximate optimization algorithm. Phys. Rev. Res. 5, 023171 (2023) https://doi.org/10.1103/PhysRevResearch.5.023171
  49. [51]McClean, J.R., Boixo, S., Smelyansky, V.N., Babbush, R., Hartmut Neven, H.: Barren plateaus in quantum neural network training landscapes. Nat Commun 9, 4812 (2018) https://doi.org/10.1038/s41467-018-07090-4
  50. [52]Ragone, M., Bakalov, B.N., Sauvage, F., Kemper, A.F., Marrero, C.O., Larocca, M., Cerezo, M.: A lie algebraic theory of barren plateaus for deep parameterized quantum circuits. Nat Commun 15, 7172 (2024) https://doi.org/10.1038/s41467-024-49909-3
  51. [53]Fontana, E., Herman, D., Chakrabarti, S., Kumar, N., Yalovetzky, R., Heredge, J., Sureshbabu, S.H., Pistoia, M.: Characterizing barren plateaus in quantum ansätze with the adjoint representation. Nat Commun 15, 7171 (2024) https://doi.org/10.1038/s41467-024-49910-w
  52. [54]McClean, J.R., Boixo, S., Smelyansky, V.N., Babbush, R., Neven, H.: Barren plateaus in quantum neural network training landscapes. Nature Communications 9 (2018)DOI
  53. [55]Cerezo, M., Sone, A., Volkoff, T., Cincio, L., Coles, P.J.: Cost function dependent barren plateaus in shallow parametrized quantum circuits. Nature Commun. 12(1), 1791 (2021) https://doi.org/10.1038/s41467-021-21728-w arXiv:2001.00550 [quant-ph]
  54. [56]Larocca, M., Thanaslip, S., Wang, S., Sharma, K., Biamonte, J., Coles, P.J., Cincio, L., McClean, J.R., Holmes, Z., M. Cerezo, M.: Barren plateaus in variational quantum computing. Nature Reviews Physics 7, 174–189 (2025)DOI
  55. [57]Guéry-Odelin, D., Ruschhaupt, A., Kiely, A., Torrontegui, E., Martínez-Garaot, S., Muga, J.G.: Shortcuts to adiabaticity: Concepts, methods, and applications. Rev. Mod. Phys. 91, 045001 (2019) https://doi.org/10.1103/RevModPhys.91.045001
  56. [58]Wurtz, J., Love, P.J.: Counterdiabaticity and the quantum approximate optimization algorithm. Quantum 6, 635 (2022) https://doi.org/10.22331/q-2022-01-27-635
  57. [59]Chai, Y., Han, Y.-J., Wu, Y.-C., Li, Y., Dou, M., Guo, G.-P.: Shortcuts to the quantum approximate optimization algorithm. Phys. Rev. A 105, 042415 (2022) https://doi.org/10.1103/PhysRevA.105.042415
  58. [60]Guan, H., Zhou, F., Albarrán-Arriagada, F., Chen, X., Solano, E., Hegade, N.N., Huang, H.-L.: Single-layer digitized-counterdiabatic quantum optimization for p-spin models. Quantum Science and Technology 10(1), 015006 (2024) https://doi.org/10.1088/2058-9565/ad7880
  59. [61]Gattringer, C., Lang, C.B.: Quantum Chromodynamics on the Lattice vol. 788. Springer, Berlin (2010). https://doi.org/10.1007/978-3-642-01850-3
  60. [62]McArdle, S., Jones, T., Endo, S., Li, Y., Benjamin, S.C., Yuan, X.: Variational ansatz-based quantum simulation of imaginary time evolution. npj Quantum Information 5, 75 (2019)DOI
  61. [63]Benedetti, M., Fiorentini, M., Lubasch, M.: Hardware-efficient variational quantum algorithms for time evolution. Phys. Rev. Res. 3, 033083 (2021) https://doi.org/10.1103/PhysRevResearch.3.033083
  62. [64]Wang, X., Chai, Y., Feng, X., Guo, Y., Jansen, K., Tüysüz, C.: Imaginary hamiltonian variational ansatz for combinatorial optimization problems. Phys. Rev. A 111, 032612 (2025) https://doi.org/10.1103/PhysRevA.111.032612
  63. [65]Wang, X., Chai, Y., Demidik, M., Feng, X., Jansen, K., Tıysüz, C.: Symmetry enhanced variational quantum imaginary time evolution. Preprint at https://arxiv.org/abs/2307.13598 (2023). https://doi.org/10.48550/arXiv.2307.13598
  64. [66]Wang, X., Feng, X., Hartung, T., Jansen, K., Stornati, P.: Critical behavior of the ising model by preparing the thermal state on a quantum computer. Phys. Rev. A 108, 022612 (2023) https://doi.org/10.1103/PhysRevA.108.022612
  65. [67]Liu, J., Li, Z., Zheng, H., Yuan, X., Sun, J.: Towards a variational jordan–lee–preskill quantum algorithm. Machine Learning: Science and Technology 3(4), 045030 (2022) https://doi.org/10.1088/2632-2153/aca06b
  66. [68]Yuan, X., Endo, S., Zhao, Q., Li, Y., Benjamin, S.C.: Theory of variational quantum simulation. Quantum 3, 191 (2019) https://doi.org/10.22331/q-2019-10-07-191
  67. [69]Motta, M., Sun, C., Tan, A.T.K., O’Rourke, M.J., Ye, E., Minnich, A.J., Brandão, F.G.S.L., Chan, S.L. G. K.-L. Campbell, Gear, C.W.: Determining eigenstates and thermal states on a quantum computer using quantum imaginary time evolution. Nature Physics 16, 205–210 (2020)DOI
  68. [70]Sun, S.-N., Motta, M., Tazhigulov, R.N., Tan, A.T.K., Chan, G.K.-L., Minnich, A.J.: Quantum computation of finite-temperature static and dynamical properties of spin systems using quantum imaginary time evolution. PRX Quantum 2, 010317 (2021) https://doi.org/10.1103/PRXQuantum.2.010317
  69. [71]Kosugi, T., Nishiya, Y., Nishi, H., Matsushita, Y.-i.: Imaginary-time evolution using forward and backward real-time evolution with a single ancilla: First- quantized eigensolver algorithm for quantum chemistry. Phys. Rev. Res. 4, 033121 (2022) https://doi.org/10.1103/PhysRevResearch.4.033121
  70. [72]Nishi, H., Kosugi, T., Matsushita, Y.-i.: Implementation of quantum imaginary- time evolution method on nisq devices by introducing nonlocal approximation. npj Quantum Information 7 (2020)DOI
  71. [73]Gacon, J., Nys, J., Rossi, R., Woerner, S., Carleo, G.: Variational quantum time evolution without the quantum geometric tensor. Phys. Rev. Res. 6, 013143 (2024) https://doi.org/10.1103/PhysRevResearch.6.013143
  72. [74]Lin, S.-H., Dilip, R., Green, A.G., Smith, A., Pollmann, F.: Real- and imaginary- time evolution with compressed quantum circuits. PRX Quantum 2, 010342 (2021) https://doi.org/10.1103/PRXQuantum.2.010342
  73. [75]Xie, H.-N., Wei, S.-J., Yang, F., Wang, Z.-A., Chen, C.-T., Fan, H., Long, G.-L.: Probabilistic imaginary-time evolution algorithm based on nonunitary quantum circuits. Phys. Rev. A 109, 052414 (2024) https://doi.org/10.1103/PhysRevA. 109.052414
  74. [76]Kolotouros, I., Joseph, D., Narayanan, A.K.: Accelerating quantum imaginary- time evolution with random measurements. Phys. Rev. A 111, 012424 (2025) https://doi.org/10.1103/PhysRevA.111.012424
  75. [77]Gomes, N., Mukherjee, A., Zhang, F., Iadecola, T., Wang, C., Ho, K., Orth, P.P., Yao, Y.: Adaptive variational quantum imaginary time evolution approach for ground state preparation. Advanced Quantum Technologies 4(12) (2021) https://doi.org/10.1002/qute.202100114
  76. [78]Koch, M., Schaudt, O., Mogh, G., Mrziglod, T., Berg, H., Beck, M.E.: A variational ansatz for tailored imaginary time evolution. ACS Omega 8(25), 22596–22602 (2023) https://doi.org/10.1021/acsomega.3c01060 https://doi.org/10.1021/acsomega.3c01060
  77. [79]Chai, Y., Di Tucci, A.: Optimizing qubo on a quantum computer by mimicking imaginary time evolution. New Journal of Physics 28(6), 064508 (2026) https: //doi.org/10.1088/1367-2630/ae6dedarxiv.org/abs/2505.22924
  78. [80]Kitaev, A.Y.: Quantum measurements and the Abelian Stabilizer Problem (1995). https://arxiv.org/abs/quant-ph/9511026
  79. [81]Lin, L., Tong, Y.: Heisenberg-limited ground-state energy estimation for early fault-tolerant quantum computers. PRX Quantum 3, 010318 (2022) https://doi. org/10.1103/PRXQuantum.3.010318DOI
  80. [82]Lin, L., Tong, Y.: Near-optimal ground state preparation. Quantum 4, 372 (2020) https://doi.org/10.22331/q-2020-12-14-372
  81. [83]Robledo-Moreno, J., Motta, M., Haas, H., Javadi-Abhari, A., Jurcevic, P., Kirby, W., Martiel, S., Sharma, K., Sharma, S., Shirakawa, T., Sitdikov, I., Sun, R.-Y., Sung, K.J., Takita, M., Tran, M.C., Yunoki, S., Mezzacapo, A.: Chemistry beyond the scale of exact diagonalization on a quantum-centric supercomputer. Science Advances 11(25), eadu9991 (2025) https://doi.org/10.1126/sciadv.adu9991 https://www.science.org/doi/pdf/10.1126/sciadv.adu9991
  82. [84]Epperly, E.N., Lin, L., Nakatsukasa, Y.: A theory of quantum subspace diagonalization. SIAM Journal on Matrix Analysis and Applications 43(3), 1263–1290 (2022) https://doi.org/10.1137/21M145954X https://doi.org/10.1137/21M145954X
  83. [85]Cortes, C.L., Gray, S.K.: Quantum krylov subspace algorithms for ground- and excited-state energy estimation. Phys. Rev. A 105, 022417 (2022) https://doi.org/10.1103/PhysRevA.105.022417
  84. [86]Kirby, W., Motta, M., Mezzacapo, A.: Exact and efficient lanczos method on a quantum computer. Quantum 7, 1018 (2023) https://doi.org/10.22331/q-2023-05-23-1018
  85. [87]Yoshioka, N., Amico, M., Kirby, W., Jurcevic, P., Dutt, A., Fuller, B., Garion, S., Haas, H., Hamamura, I., Irvin, A., Majumdar, R., Minev, Z., Motta, M., Pokharel, B., Rivero, P., Sharma, K., Wood, C.J., Javadi-Abhari, A., Mezzacapo, A.: Krylov diagonalization of large many-body hamiltonians on a quantum processor. Nature Communications 16, 5014 (2025) https://doi.org/10.1038/s41467-025-59716-z
  86. [88]Yu, J., Moreno, J.R., Iosue, J.T., Bertels, L., Claudino, D., Fuller, B., Groszkowski, P., Humble, T.S., Jurcevic, P., Kirby, W., Maier, T.A., Motta, M., Pokharel, B., Seif, A., Shehatta, A., Sung, K.J., Tran, M.C., Tripathi, V., Mezzacapo, A., Sharma, K.: Quantum-Centric Algorithm for Sample-Based Krylov Diagonalization (2025). https://arxiv.org/abs/2501.09702
  87. [89]Lee, C., Park, D.K.: Generative Krylov Subspace Representations for Scalable Quantum Eigensolvers (2025). https://arxiv.org/abs/2512.19420
  88. [90]Kempe, J., Kitaev, A., Regev, O.: The complexity of the local hamiltonian problem. SIAM Journal on Computing 35(5), 1070–1097 (2006) https://doi.org/10.1137/S0097539704445226 https://doi.org/10.1137/S0097539704445226
  89. [91]Sard, A.: The measure of the critical values of differentiable maps. Bulletin of the American Mathematical Society 48, 883–890 (1942) https://doi.org/10.1090/S0002-9904-1942-07811-6
  90. [92]Muller, M.E.: Some continuous monte carlo methods for the dirichlet problem. The Annals of Mathematical Statistics 27(3), 569–589 (1956)DOI
  91. [93]Muller, M.E.: A note on a method for generating points uniformly on n-dimensional spheres. Communications of the ACM 27, 19–20 (1959)DOI
  92. [94]Bailey, R.W.: Distributional identities of beta and chi-squared variates: A geometrical interpretation. The American Statistician 46(2), 117–120 (1992). Accessed 2026-02-17DOI
  93. [95]Funcke, L., Hartung, T., Jansen, K., Kühn, S., Schneider, M., Stornati, P.: Best-approximation error for parametric quantum circuits. In: 2021 IEEE International Conference on Web Services (ICWS), pp. 693–702. IEEE, ??? (2021)arxiv.org/abs/2107.07378
  94. [96]Trotter, H.F.: On the product of semi-groups of operators. Proceedings of the American Mathematical Society 10(4), 545–551 (1959). Accessed 2025-02-13DOI
  95. [97]Sommese, A.J., Verschelde, J., Wampler, C.W.: In: Bronstein, M., Cohen, A.M., Cohen, H., Eisenbud, D., Sturmfels, B., Dickenstein, A., Emiris, I.Z. (eds.) Introduction to numerical algebraic geometry, pp. 301–337. Springer, Berlin, Heidelberg (2005). https://doi.org/10.1007/3-540-27357-3_8 . https://doi.org/10.1007/3-540-27357-3_8
  96. [98]Chen, T., Li, T.-Y.: Homotopy continuation method for solving systems of nonlinear and polynomial equations. Communications in Information and Systems 15(2), 119–307 (2015)DOI
  97. [99]Poulin, D., Qarry, A., Somma, R., Verstraete, F.: Quantum simulation of time-dependent hamiltonians and the convenient illusion of hilbert space. Phys. Rev. Lett. 106, 170501 (2011) https://doi.org/10.1103/PhysRevLett.106.170501
  98. [100]Bennett, C., Bernstein, E., Brassard, G., Vazirani, U.: Strengths and weaknesses of quantum computing. SIAM J. Comput. 26, 1510–1523 (1997)DOI

Paper details

vlnc:W_echzwhhx
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 11

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Physics and Astronomy

Not recorded for this paper

View statement
Looking for related papers…
Contents