Well-conditioned multiproduct Hamiltonian simulation
Guang Hao Low Vadym Kliuchnikov Nathan Wiebe
quant-ph physics.comp-ph


|#⟩1|#1⟩
⟨#|1⟨#1|




















































proofof[1]
  Proof of #1.

















Microsoft Quantum, Redmond WA, USA

Microsoft Quantum, Redmond WA, USA

Microsoft Quantum, Redmond WA, USA
Pacific Northwest National Laboratory, Richland WA, USA
Department of Physics, University of Washington, Seattle, WA, USA

Product formula approximations of the time-evolution operator on quantum computers are of great interest due to their simplicity, and good scaling with system size by exploiting commutativity between Hamiltonian terms. 

However, product formulas exhibit poor scaling with the time t and error ϵ of simulation as the gate cost of a single step scales exponentially with the order m of accuracy.

We introduce well-conditioned multiproduct formulas, which are a linear combination of product formulas, where a single step has polynomial cost 𝒪(m^2log(m)) and succeeds  with probability Ω(1/log^2(m)).

Our multiproduct formulas imply a simple and generic simulation algorithm that simultaneously exploits commutativity in arbitrary systems and has a worst-case cost 𝒪(tlog^2(t/ϵ)) which is optimal up to poly-logarithmic factors. 

In contrast, prior Trotter and post-Trotter Hamiltonian simulation algorithms realize only one of these two desirable features.

A key technical result of independent interest is our solution to a conditioning problem in previous multiproduct formulas that amplified numerical errors by e^Ω(m) in the classical setting, and led to a vanishing success probability e^-Ω(m) in the quantum setting.

Well-conditioned multiproduct Hamiltonian simulation
    Nathan Wiebe
    
  First Draft: July 26, 2019 

  Current Draft: August 31, 2020
====================================================================














Introduction
Quantum computers promise to enable the efficient simulation of quantum Hamiltonian dynamics, which is, in general, intractable on classical computers. 

However, the quantum gate cost of simulating many important systems, such as quantum field theories <cit.> and chemistry <cit.>, is still prohibitive <cit.>.

As such, new techniques for digital Hamiltonian simulation remains a subject of intense research that has seen tremendous progress in recent years <cit.>.

More, though, is required to realize technologically relevant applications within the foreseeable future.

State-of-art quantum algorithms for simulation may be broadly categorized as one of two complementary approaches: Lie-Trotter-Suzuki product formulas <cit.>, or Linear-Combination-of-Unitaries (LCU) <cit.>.

Both seek to approximate the unitary time-evolution operator of Schrödinger's equation using the fewest number of primitive quantum gates.

However, they differ in asymptotic gate cost with respect to the time, error, and the size of the simulated system.

A dichotomy in this difference often makes the preferred method for any given situation unclear.


On one hand, the gate cost of LCU approaches is near-linear in time and logarithmic in error, which is essentially optimal according to no-fast-forwarding theorems <cit.>.

In contrast, an order 2m product formula is more expensive by a super-logarithmic factor (t/ϵ)^1/2m <cit.> of time and error.

As the cost of product formulas is exponential in the order m, such as the standard recursive construction by Suzuki <cit.>, achieving a poly-logarithmic overhead is impossible, even by varying the order arbitrarily.

On the other hand, product formulas tend to scale significantly better with the size of typical physical systems due to the principle of locality.

A most dramatic separation in performance is observed in simulating strictly local interactions <cit.>.

Without any special modification, the gate cost of high-order product formulas scales almost-linearly like 𝒪(N^1+o(1)) in system size <cit.>.

In contrast, all known LCU  approaches lose this desirable feature and exhibit quadratic scaling in general Ω(N^2) <cit.>.

Whereas the maximum stepsize of product formulas is limited by how well terms in the Hamiltonian commute, LCU approaches are unable to exploit commutation between Hamiltonian terms.

Similar advantages are observed in simulations with long-ranged interactions <cit.> such as the coulomb potential <cit.>, and systems with small algebras such as the quantum harmonic oscillator <cit.>.



We present a simple algorithm for Hamiltonian simulation that combines the best properties of product formula and LCU approaches.

In addition to improved scaling with system size through an explicit dependence on commutators, our algorithm also matches the limits of no-fast-forwarding up to a logarithmic factor of time and error.  

The basic idea is to approximate high-order time-evolution by a linear combination of low-order product formulas, known in classical numerical techniques as a multiproduct formula <cit.>, which is a generalization of Richardson extrapolation.

Unlike the exponential cost of product formulas, we find families of order 2m multiproduct formula that can be realized with only 𝒪(m^2log(m)) queries to any symmetric product formula, and on a quantum computer, succeeds with a high probability Ω(1/log^2(m)) that is easily amplified using robust oblivious amplitude amplification <cit.>.

Thus the overhead 𝒪(m^2log^2(m)(t/ϵ)^1/m) is made logarithmic by a simple optimization over the order.


Our key technical result is solving a conditioning problem in multiproduct formulas, which is of independent interest. 

This problem manifested as an exponentially small probability of success e^-Ω(m) in previous quantum implementations <cit.>, 

which arose from the exponentially precise cancellation of terms required by prior known high-order multiproduct formulas.

In contrast, the properties of our well-conditioned multiproduct formulas, illustrated in <ref>, feature both a polynomial query cost and coefficients of logarithmic size, and are therefore numerically stable.

In the following, we outline the multiproduct conditioning problem in the context of Hamiltonian simulation.

This problem is then solved by our constructive proof that well-conditioned multiproduct formulas of arbitrary order exist, and moreover have an elegant closed-form description. 

We also provide an efficient numerical recipe for constructing optimally-conditioned instances of multiproduct formulas.

These multiproduct formulas let us prove our main claim of a Hamiltonian simulation algorithm that simultaneously has optimal scaling with respect to time and error, up to a logarithmic overhead, and also exploits commutativity of terms. 

We also validate our claims in a simple numerical benchmark depicted in <ref> of simulating the 1D Heisenberg model.

The multiproduct conditioning problem The Hamiltonian H=∑_j=1^N h_j of many physical systems is described by a sum of N local terms. 

The first explicit quantum algorithm for approximating the unitary time-evolution operator U_1(Δ)≈ e^-iHΔ was by Lloyd <cit.>, and splits evolution by the whole into evolution by its parts, that is 

    U_1(Δ)=∏_j=1^N e^-i h_j Δ= e^-iHΔ + 𝒪(∑_j<k[h_j,h_k]Δ^2),

where the ordering of terms e^-ih_1Δe^-ih_2Δ⋯ is indicated by the arrow `→'.

As this decomposition is correct to first order, evolution for arbitrary long times t is accomplished by applying t/Δ approximate segments, each comprising of N exponentials, with the stepsize Δ chosen to control the overall accumulated error.

Importantly, the error term depends explicitly on pairwise commutators of Hamiltonian terms, which in turn limits the maximum stepsize.

Higher order-α integrators exist, such as the second-order symmetric product formula

    U_2(Δ)=U_1(Δ/2)·U_1(Δ/2)=  e^-iHΔ + O(Δ^3),

which is used in the recursion by Suzuki <cit.>

    U_α(Δ)   =U^2_α-2(p_αΔ)· U_α-2((1-4p_αΔ)· U^2_α-2(p_αΔ),
    
    p_α   =1/(4-4^1/(α-1)).

However, these makes 5^α/2-1 queries to the base sequence U_2, and are thus impractical at high orders.



We instead focus on multiproduct formulas, where a higher order 2m integrator is constructed from a linear combination of any symmetric lower-order product formula

    U_k⃗(Δ)=∑^M_j=1a_j U_2^k_j(Δ/k_j) = e^-iHΔ+𝒪(Δ^2m+1),

such as the second-order Trotter-Suzuki formula U_2.

Any symmetric product formula has a formal Baker-Campbell-Hausdorff (BCH) expansion U_2(Δ)= e^-iHΔ +  E_3Δ^3 + E_5 Δ^5+ ⋯ for some error operators E_k <cit.>, which implies the Taylor expansion

    U^k_j_2(Δ/k_j)    = e^-iHΔ + Δ^3/k_j^2Ẽ_3(Δ) + Δ^5/k_j^4Ẽ_5(Δ) + ⋯,

for some error operators Ẽ_k(Δ).

Thus all lower order error terms may be canceled by choices of coefficients a_j that solve the m× M system of linear equations

    [         1         1         ⋯         1;    k_1^-2    k_2^-2         ⋯    k_M^-2;         ⋮         ⋮         ⋱         ⋮; k_1^-2m+2 k_2^-2m+2         ⋯ k_M^-2m+2;           ]_
    V_m,M(k⃗^-2)[ a_1; a_2;   ⋮; a_M ]
    _a⃗=
    [ 1; 0; ⋮; 0 ]
    _
    ê_1
    .

The left-hand side of <ref> is a Vandermonde matrix V_m,M(k⃗^-2)∈ℝ^m× M, where k⃗^-2=[k_1^-2,⋯,k_M^-2].

In the square case M=m, this has the solution

    a_j = ∏_q={1,…,m}∖ jk_j^2/k_j^2-k_q^2=∏_q≠ j1/1-(k_q/k_j)^2.


As described by Chin <cit.>, it suffices to take the simplest choice of an arithmetic progression for the exponents k_j=j with M=m.

By summing over the exponents, only k⃗_1∈𝒪(m^2) queries to U_2 are required, which appears to be an exponential improvement over that of the Trotter-Suzuki integrators <ref>.

Unfortunately, these multiproduct formulas are ill-conditioned, as reflected by the quantity we call the `condition number' a⃗_1∈ e^Ω(m), which is exponentially large in the order m <cit.>.

This implies an extremely precise cancellation of terms in <ref>, which amplifies any numerical error of the base sequence U_2 by a factor a⃗_1.


Within the quantum setting, standard linear-combination-of-unitaries techniques translate ill-conditioning into an exponentially small success probability a⃗^-2_1 <cit.>.

Using the recently developed oblivious amplitude amplification technique <cit.>, this probability may be boosted close to unity, but still at high cost 𝒪(a⃗^-1_1).

This highlights the need for multiproduct formulas with small condition number.

Solutions to the conditioning problem 

We shed insight on the conditioning problem by considering the general under-determined setting where the exponents k_j are arbitrary rather than an arithmetic sequence, and where the Vandermonde matrix is not necessarily square.

Our main technical result is an super-exponential reduction in the condition number, illustrated in <ref> and formally stated by the following theorem.


	
	There exist order-2m multiproduct formulas <ref> with polynomial integer exponents k⃗_1∈𝒪(m^2 log(m)) and logarithmic condition number a⃗_1∈𝒪(log m).



Our strategy for proving <ref> is constructive.

First, we relax <ref> to allow real-valued exponents k”_j with coefficients a”_j, and find well-conditioned solutions in closed-form for arbitrary orders 2m, through an elegant connection to Chebyshev polynomials.

Second, we modify these solutions to obtain exponents k'_j with a larger gap between consecutive exponents |k'_j-k'_j+1|∈Ω(1/m).

Third, we scale and round the exponents k'_j to unique integers k_j, and show that the condition number a⃗_1 changes by at most a constant factor. 


As the U_2 query complexity must be at least quadratic ≥m/2(1+m) for any choice of m unique integer exponents in <ref>, and largest condition number is at most unity, our result in <ref> is also optimal up to at most logarithmic factors.

As a bonus, we also present a rational linear program of polynomial size whose solutions describe multiproduct formulas with optimal condition number.



Consider a set of m polynomials {p_j(x)=∑_i=1^mA_j,i x^i-1}_j=1^m with coefficients represented as the square matrix A∈ℝ^m× m, that are orthogonal

    ⟨p⃗_j, p⃗_k ⟩   = ∑^m_i=1p_j(x_i)p_k(x_i) =δ_jk⟨p⃗_j, p⃗_j ⟩,
    p⃗_j   =[p_j(x_1),p_j(x_2),⋯,p_j(x_m)],

over some discrete set of interpolation points x⃗, where δ_jk is the Kronecker delta function. 

Now, left-multiply the Vandermonde matrix by the polynomial coefficients A. The j^th row of the output satisfies

    (A· V_m,m(x⃗)·a⃗”)_j
    =(A·ê_1)_j
    =A_j,1
    =⟨p⃗_j,a⃗”⟩.

Using orthogonality <ref>, the above <ref> is satisfied by the choice
a⃗” = ∑_i=1^mA_i,1p⃗_⃗i⃗/⟨ p_i, p_i⟩.

We find that coefficients with desirable properties are described by the basis p_j(x)≡ T_j-1(2x-1) of Chebyshev polynomials T_j(x)=cos(j cos^-1(x)) which are orthogonal
⟨ p_j, p_k⟩ = m/2δ_jk(1+δ_j1) with respect to the Chebyshev interpolation points 

    x_j^(m)=sin^2(π(2j-1)/4m)=1/k_j”^2.


By substitution, the coefficients are given by 

    a_j”^(m)= (-1)^j+1/m(π(2j-1)/4m),  j∈[m].


We drop the superscript (m) indicating the multiproduct formula order 2m whenever the context is clear.

Thus we may bound the exponents k⃗”_1∈Θ(mlog(m)) and condition number a⃗”_1∈Θ(log(m)).

An intermediate real-exponent solution that is important to obtaining our rounded integer-exponent solution drops the latter half of the Chebyshev interpolation points.

Choose x_j'^(m)=1/k'^2_j=x_j^(2m), where j∈[m].

Then from <ref>,
	
    | a_j'^(m)|
    	≤|∏_q=m+1^2ma_j'^(m)/1-x_j^(2m)/x_q^(2m)|
    	=
    	|a_j”^(2m)|, j ∈ [m],

	which follows from the monotonicity of x_j. 

Thus the exponents and condition number are also bounded by
	
	a⃗'_1∈𝒪(log(m))
	
	and k⃗'_1∈Θ(mlog(m)).

	


Implementing fractional U_2 queries, though asymptotically efficient in principle <cit.>, can be impractical. 

Thus, we choose for an order 2m multiproduct formula the rounded exponents 

    k_j = ⌈ K k'_j⌉=⌈ K/√(x_j^(2m))⌉,  j∈[m],

where the scale factor K<√(8)m/π ensures rounding to unique integers, and implies k⃗_1∈𝒪(m^2log(m)).

We now prove that the coefficients a_j change by at most a multiplicative constant compared to a'_j.

As K k'_j∈Θ(m^2/j)⊆Ω(m), the fractional shift |k_j-K k'_j|/m∈Θ(1/m) is small for large orders.

Thus the fractional change in γ_q=(k'_q/k'_j)^2 from Taylor's theorem is

    (k_q/k_j)^2=(k'^2_q/k'^2_j)^2(1+Δ[q,j])
    , 
    |Δ[q,j]|∈Θ(|q-j|/m^2),

where the sign of Δ[q,j] matches the sign of (q-j).

As Δ[q,j] is also small, the shift in a'_j to leading order is given by the derivatives ∂ a'_j/∂γ_q=a'_j/1-γ_q, following <ref>. Thus

    |a'_j-a_j|/|a_j|   ∈Θ(∑_q≠ jΔ[q,j]/1-γ_q)
    ⊆Θ(∑_q≠ jx'_q|q-j|/m^2|x'_q-x'_j|)
       ⊆Θ(1).


We complete our proof by evaluating k⃗_1 using <ref>, and noting that <ref> implies a⃗_1∈Θ(a⃗'_1).


We can further optimize the condition number a⃗_1 by a numerical search over to all Mm subsets of exponents {k_j}_j=1^m⊆[M]. 

This can be cast as an efficient linear program

    min_a⃗a⃗_1 s.t. V_m,M(k⃗^-2)·a⃗=ê_1 ∧ k_j=j∈[M],

followed by minimizing with respect to m∈[M]. 

Analogous to sparse signal recovery <cit.>, one-norm minimization ensures that the solution a⃗ is sparse with exactly m non-zero elements.

We tabulate the solutions to <ref> in <ref>.

Hamiltonian simulation in the worst-case

In the worst-case where all terms are maximally non-commutative, well-conditioned multiproduct formulas translate into Hamiltonian simulation algorithms that match no-fast-forwarding up to a logarithmic factors in time and error, stated formally in the following. 


	
	Time evolution can be approximated with error U^r_k⃗(t/r) - e^-itH≤ϵ≤1, where r=Θ(tλ) and λ=∑_j=1^Nh_j, by a quantum circuit that succeeds with probability 1-𝒪(ϵ) using
	𝒪(tλlog^2(tλ/ϵ))
	controlled-U_2 queries
	and 𝒪(tλlog(tλ/ϵ)) additional quantum gates.



The basic idea is to bound the error of a single multiproduct step, followed by varying the multiproduct order sub-logarithmically with time and error. 

We begin with the remainder of a product formula <cit.>

    ℛ_2m[U_2^j(Δ/j)-e^-iHΔ]≤2|Δλ|^2m+1/(2m+1)!e^|Δλ|.



By a triangle inequality, the error

    U_k⃗(Δ)-e^-iHΔ≤2a⃗_1|Δλ|^2m+1/(2m+1)!e^|Δλ|=ϵ_Δ,

of a single multiproduct step accumulates after r=t/Δ steps to

    U^r_k⃗(t/r)-e^-iHt≤ϵ_t/r r(1+ϵ_t/r)^r-1≤ϵ,
 

which is at most ϵ≤ 1 with the choice 

    r = tλmax{(8tλa⃗_1/ϵ(2m+1)!)^1/(2m) , 1/log(2)}.


The cost of U^r_k⃗(t/r) is then rk⃗_1 queries to the base product formula U_2.

This expression is simplified using Stirling's formula 1/(2m+1)!∈Θ(e^e^z-ze^z-z/2) where 2m=e^z.

We scale the order with z=W(log(tλ/ϵ)) using the Lambert-W function which satisfies,  by definition, z e^z=log(tλ/ϵ).

Using the well-conditioned multiproduct formulas of <ref> where a⃗_1∈𝒪(log(m))⊆𝒪(z) and k⃗_1∈Θ(m^2log(m))⊆Θ(ze^2z),
the number of steps is r∈Θ(tλ).

Thus at most rk⃗_1∈Θ(tλ)·Θ(z e^2z) queries to U_2 suffice to approximate e^-iHt.

The linear combination of unitaries quantum circuit implements a single multiproduct step.

This uses a coefficient state |a⟩=∑_j=1^m√(a_j)|j⟩ and a unitary selector S=∑^m_j=1|j⟩⟨j|⊗ (sign[a_j])U^k_j(Δ/k_j).

These apply the multiproduct formula (⟨a|⊗ I)S(|a⟩⊗ I)=U_k⃗(Δ)/a⃗_1 with success probability 1/a⃗^2_1.

The controlled-U_2 query cost of this step is k⃗_1 due to S, and the gate cost is 𝒪(m) due the dimension of |a⟩.


A quantum circuit implements multiple multiproduct steps with high probability using robust oblivious amplitude amplification <cit.>, which boosts the success probability of each step to 1-𝒪(ϵ/r) at a multiplicative cost of 𝒪(a⃗_1). 

This also increases the error by at most an absolute constant.

Thus the overall success probability of applying r steps is 1-𝒪(ϵ), with a total U_2 query cost of ra⃗_1k⃗_1∈𝒪(tλ z^2 e^2z)⊆𝒪(tλlog^2(tλ/ϵ)), and a total additional gate cost of ra⃗_1 m∈𝒪(tλ z e^z)⊆𝒪(tλlog(tλ/ϵ)) that is sub-dominant.


Note that the query cost may be reduced by an additional factor of z∈𝒪(loglog(t/λ/ϵ)) using more specialized query models outlined in <ref>.

Cost dependence on Hamiltonian term commutators As multiproduct formulas use product formulas as their base sequence, their costs also inherit an explicit scaling with the commutators of Hamiltonian terms, as captured by the following.

	(Commutator dependence of multiproduct formulas)
	The error U_k⃗(Δ)e^iΔ H - I of an order 2m multiproduct formula U_k⃗ with U_α as the base sequence depends on Hamiltonian terms that all occur in commutators [h_j_β,[⋯,[h_j_2,h_j_1]⋯]] nested to depth β>α.


The error of a multiproduct formula that is correct to order 2m is the sum of remainders of product formulas.

Thus it suffices to examine the commutator structure of W(T)≡ U^k_α(Δ/k)e^iΔ H, which, for some piece-wise constant time-dependent Hamiltonian, solves the time-dependent Schrödinger equation

i∂/∂ sW(s)=Δ A(s)W(s),
W(0)=I 
at time T=2kN+1.

For instance, U_2 is generated by

    A_k(s)   =
    
    -H,    s∈[0,1), 
    
    h_⌊ s⌋/(2k),    s∈[1,2kN+1],
    
    0,   otherwise,
    
    
    h_s   ≡ h_1+( s-1(2N)).



Following a decomposition theorem by Lam <cit.>, any time-ordered exponential has the expansion
W(T)=∑_n=0^∞Δ^n ∑_l=1^n∑_m_1,⋯,m_l>0,m⃗_1=nξ(m⃗)C_m_1C_m_2⋯ C_m_l, where 
ξ(m⃗)=∏_i=1^dimm⃗[∑_j=i^dimm⃗ m_j]^-1 and

    C_m
    =∫_T≥ s_m≥⋯≥ s_1≥ 0ds⃗  
    
    [A(s_m),[⋯,[A(s_2),A(s_1)]⋯]].


The advantage of this expression is the explicit dependence on nested commutators C_m of Hamiltonian terms.

Any product formula that is correct to order α satisfies U_α(Δ)e^iΔ H-I∈𝒪(Δ^α+1) by definition. 

This implies that C_1=C_2=⋯=C_α=0.

Thus W(T) explicitly depends only on higher-ordered nested commutators. 





Heisenberg model benchmark
In practice, the optimal step-size Δ is determined empirically, such as by extrapolation from smaller to larger instances <cit.>.

Using the 1D Heisenberg chain H=∑_j=1^N(X_j X_j+1+Y_j Y_j+1+Z_j Z_j+1) with periodic boundary conditions,

we numerically validate in <ref> the logarithmic scaling of cost with maximum allowable error U^r_k⃗(t/r)-e^-iHt≤ϵ and that cost with respect to system size no worse than product formula used as the base sequence.


For each maximum error threshold ϵ, we minimize the cost 3rk⃗, where the factor three is from oblivious amplitude amplification, over all multi-product formulas tabulated in <ref> that are optimized for oblivious amplitude amplification.

For each choice of multiproduct formula, we apply binary search to find the maximum number of steps r within the allowable error ϵ.


Conclusion
We have constructed well-conditioned multiproduct formulas that simultaneously exploit the commutativity structure of the simulated Hamiltonian and achieve a logarithmic cost dependence on error in the worst-case.

Variations of our approach are possible and worth investigating in future work.

For instance, rigorous error bounds on the nested commutators would be of practical relevance, which also have a non-trivial dependence on the order of product formulas chosen as the base sequence.

An extension to the time-dependent case is also possible by bootstrapping off existing product formulas for time-dependent simulation <cit.>.

More broadly, continued research in capitalizing on the features of average-case Hamiltonians <cit.> will be crucial to the practical realization of quantum simulation on quantum computers.


apsrev4-1
apsrev41Control





§ EXAMPLES OF OPTIMAL MULTI-PRODUCT FORMULAS


In this section, we tabulate coefficients for multiproduct formulas.

We provide optimized solutions where the base sequence is either a symmetric second order product formula in <ref>, or a symmetric fourth order product formula in <ref>.

Symmetric order-α product formulas may be formally expressed as
U_α(Δ)= e^-iHΔ +  E_α+1Δ^α+1 + E_α+3Δ^α+3+ ⋯ for some error matrices E_k <cit.>. This implies the Taylor expansion

    U^k_j_α(Δ/k_j)    = e^-iHΔ
    
    + Δ^α+1/k_j^αẼ_α+1(Δ) + Δ^α+3/k_j^α+2Ẽ_α+3(Δ) + ⋯.

Thus all error terms of order 2m and below cancel in the linear combination

    U_k⃗(Δ)=∑^M_j=1a_k_j U_α^k_k_j(Δ/k_k_j) = e^-iHΔ+𝒪(Δ^2m+1),

if the coefficients a_j and exponents k_j satisfy the following under-determined system of linear equations.

    [         1         1         ⋯         1;    k_1^-α    k_2^-α         ⋯    k_M^-α;  k_1^-α-2  k_2^-α-2         ⋯  k_M^-α-2;         ⋮         ⋮         ⋱         ⋮; k_1^-2m+2 k_2^-2m+2         ⋯ k_M^-2m+2;           ][ a_1; a_2; a_3;   ⋮; a_M ][ 1; 0; 0; ⋮; 0 ]
    .


These coefficients are optimized through the linear program of <ref> to minimize the number of queries to the base sequence, which is captured by the product a⃗_1k⃗_1, where k⃗ only contains the k_j exponents that correspond to non-zero a_j coefficients in <ref>. 

Use of oblivious amplitude amplification <cit.> requires rounding a⃗_1 up to the smallest value n that satisfies 

    n=argmin_1≤ y≤a⃗_1⌈π/4 sin^-1(1/y)-1/2⌉∈ℤ_odd,


For all cases that we tabulate in <ref>, it turns out that a⃗_1 is small enough that n is always 3. 

Thus we also provide solutions that minimize k⃗_1 for the largest a⃗_1≤2.










§ MULTIPRODUCT CIRCUIT OPTIMIZATIONS


Given a multiproduct formula U_k⃗(Δ)=∑^M_j=1a_j U_2^k_j(Δ/k_j) from <ref>,
we expressed cost in terms of a sum of queries to the base product formula.  

This contributes a multiplicative factor of k⃗_1=k_1+k_2+⋯+k_M. 

However, it should be recognized that this factor is a worst-case bound.

In this section, we briefly discuss a query model where this multiplicative factor is reduced from  k⃗_1 to max_j k_j.

Though this corresponds to improving the query complexity of <ref> by only a sub-logarithmic factor, this improvement could nevertheless be situationally advantageous.


For a Hamiltonian H=h_1+h_2⋯+h_N with N terms, let us define the programmable rotation

    Prog_k(Δ)=∑_p=0^P|p⟩⟨p|⊗ e^-ipΔ h_k/P.

Controlled on a binary number p∈[0,P], this applies time evolution by Δ scaled by a fraction p/P.

Using N programmable rotations in sequence, this allows us to synthesize the programmable product formula

    ProgPF(Δ)=∑_p=0^P|p⟩⟨p|⊗ U_2(pΔ/ P).


We may then synthesize

    ProgMPF(Δ)=∑_j=1^M|j⟩⟨j|⊗∑_p=0^P|p⟩⟨p|⊗ U^k_j_2(pΔ/ P).

Note that this uses max_j k_j queries to the programmable product formula rather than k⃗_1. 

As the exponents k_j are known beforehand, we may create a circuit where controlled on |j⟩, we simply do not apply the remaining M-k_j programmable product formulas.

Thus a single-step of the multiproduct formula 

    (⟨G|⊗ I)·ProgMPF(Δ)· (|G'⟩⊗ I)=1/a⃗_1∑^M_j=1a_j U_2^k_j(Δ/k_j),

is approximated to error ϵ by using the states 

    |G⟩   =∑_j=1^M√(a_j)|j⟩|P/k_j⟩,
    |G'⟩   =∑_j=1^M√(-a_j)|j⟩|P/k_j⟩,

and choosing P∈𝒪(NMΔ/ϵ).



