Robust Quantum Gate Complexity: Foundations
Johannes Aspman Vyacheslav Kungurtsev Jakub Marecek


APS/123-QED






Department of Computer Science, Czech Technical University in Prague,
 Karlovo nam. 13, Prague 2, Czech Republic


Robust Quantum Gate Complexity: Foundations
    All authors contributed equally.
    April 29, 2024
===========================================







§ INTRODUCTION

Optimal control of closed quantum systems is a well studied geometrically elegant set of computational theory and techniques that have proven pivotal in the implementation and understanding of quantum computers. The design of a circuit itself corresponds to an optimal control problem of choosing the appropriate set of gates (which appear as control operands) in order to steer a qubit from an initial, easily prepared state, to one that is informative to the user in some sense, for e.g., an oracle whose evaluation is part of the circuit. However, contemporary devices are known to be noisy, and it is not certain that a circuit will behave as intended. Yet, although the computational tools exist in broader optimal control theory, robustness of adequate operation of a quantum control system with respect to uncertainty and errors has not yet been broadly studied in the literature. Some previous works have addressed the question of controllability of open quantum system, see for example <cit.>, while the recent work <cit.> does study the optimal control problem with some interesting results. In this paper, we propose a different approach than <cit.>, making use of geometric interpretations of the optimal control problem. To this end, we present the appropriate problem definitions of robustness in the context of quantum control, focusing on its broader implications for gate complexity. 

In a series of seminal papers <cit.>, Nielsen et al. established a formal correspondence between the time optimal closed quantum control problem, the gate complexity of a quantum circuit, and the geodesic path on a manifold corresponding to the geometry of quantum operators, with the metric appropriately informed by the properties of the available gates.

This line of work has developed towards increased sophistication and broader applicability. In <cit.>, the authors formally develop the control/geometry correspondence associated with the metric's Christoffel symbols and parallel transport.
Simple analytically derived examples were studied in <cit.>. See also <cit.> for an application to NMR and <cit.> for connections to high-energy physics. 

Most recently, <cit.> have used this reasoning to show the linear growth of circuit complexity, in terms of the number of Haar-random two-qubit quantum gates required to implement a unitary.
While the original metric of Nielsen <cit.> is known to be non-smooth <cit.> (sometimes known as the “cliff metric”), there also exist smooth variants <cit.>. 
For some discussion of recent developments, see <cit.>. 
Near term devices are all expected, however, to exhibit significant noise with any circuit of reasonable depth. Thus there is always some probability that the desired state will not be achieved, and only proximity with high probability could be a reasonable target. The first work to acknowledge this point formally <cit.>, studied tradeoffs associated with inexact satisfaction of the time optimal control. They computed a pareto front of cost and gate fidelity demonstrating the relative effort required to ensure minimal gate error. 

Control of open quantum systems have been discussed scarcely in the literature, see for example <cit.>. Most of this literature deals with the question of controllability. In <cit.>, however, the question of optimal control for open quantum systems is considered. There, the authors consider an iterative approach for the optimal control of Lindbladian open quantum systems. Our proposal is rather different as we generally do not require an iterative solution of the dynamics at each time step.  




The standard time optimal control associated with the gate complexity problem <cit.> minimizes the time required to synthesize a unitary target U̅ under Schrödinger dynamics,  i.e.,

    min_{h_j(t)}∈ℋ      T 
    subject to dU/dt   =-iH(t)U(t) 
    
         U(T)    U̅
    
         H(t)   ∑_j=1^m h_j(t) H_j

where h_j(t) are control variables. They correspond to implementing a mixture of Hamiltonian operators {H_j} available to the controller. 


We depart from this standard formulation and introduce error in the operator application, in the form of an unknown time dependent switching term selecting between the intended operation and some other operator. Formally, 

    H_j(t) = α_j(t)Ĥ_j+(1-α_j(t))H̆_j

where Ĥ_j is the desired Hamiltonian and H̆_j the erroneous one. In this first work we consider that H̆_j is Hermitian, thus preserving the geometry of the control as being on the manifold of unitary matrices. 

With some probability, any intended trajectory could be thwarted by the presence of errors, i.e., there shall be some t_a,t_b with α_j(t)=0 for t_a<t<t_b. This necessitates considering alternative, approximate notions of the time optimal control and the associated notions of gate complexity and geometric distance minimizing paths. 

First, a statistical agglomeration must be chosen. Classically, the expectation is applied on the cost function in the optimal control problem, and now the control to minimize the expected cost is sought. Then, since analytic solutions are rarely tractable for these problems, some sampling approach must be used with the numerical optimization to form a well defined finite-dimensional problem. In numerical optimal control, the standard technique is to introduce scenarios whereby a sample average approximation of the objective is constructed and defined to be the target.

In this brief paper, we formulate the robust time optimal control problem, indicate appropriate methods and procedure to solve it, and derive the corresponding perturbative notions for the gate complexity and geodesics. Thus, we introduce considerations of gate errors into the theoretical framework of geometric quantum control in terms of how the control relates to gate complexity and path geometry. 








§ THE ROBUST OPTIMAL CONTROL


The aforementioned literature established formal isomorphisms between the time optimal control problem, the gate complexity of a circuit, and the minimal distance computed between an initial and target state. See the supplementary material for the formal technical details. In the presence of gate errors, this picture needs to be augmented with an appropriate problem formulation that targets a statistic, with respect to the noise, of the optimal time, and correspondingly, the gate complexity and geodesic distance. We shall describe how the standard application of robust scenario based stochastic optimal control on this construction is formed and the kinds of problems and possible algorithms that could be used to solve them. 

Fortunately, when it comes to robust optimal control, there are formulations that exist in the literature, with the most well established ones being based around solving sample average approximations of the problem. In the stochastic programming literature, the operative terminology is using a set of scenarios, and formulating the discretized problem wherein it is enforced that a control action cannot be dependent on a future realization. 





 §.§ Modeling gate errors and noise

Gate error noise corresponds to an application of an operator that is distinct from the intended one. We expect that the tendency for a gate to yield error is auto-correlated across time, so if correctly applied at time t it is likely to be correctly applied at time t+dt. Otherwise α_j(t) in (<ref>) as a function of t could have an infinite number of discontinuous points within any finite time interval, potentially causing regularity issues in studying the OCP.

The appropriate noise process then takes α_j(t) as bang-bang: α_j(t) = 0 for some t∈[0,T] and 1 for the complement on [0, T]. When α_j(t) jumps in that interval is random. This corresponds to a situation wherein we can apply a gate multiple times, with an error appearing at some instances and others not, without the time of the error appearing being known a priori. 
We can consider the possible realizations of α(t), denoted by 𝒜 to be the set of {0,1} valued maps with meas({t:α_j(t)=0})≥ T/a for some 0<a<T. To avoid certain degeneracies that would come up otherwise, we consider that a≥ T/2.

A natural parametrization is as a Poisson point process, i.e., with exponentially distributed jump times, with α_j(0)=1 and,

    ℙ(α_j(t)=0, α_j(s)=1, s<t) = 1-e^-λ_e t

then,

    ℙ(α_j(t)=1, α_j(s)=0, t_0≤ s<t, α_j(r)=1, r<s) 
       = 1-e^-λ_c t

where we can consider asymmetry and the time to balance the lack of errors as more likely/common, i.e., λ_c<λ_e. 



 §.§ The Robust Control Formulation

With the change in the model to incorporate errors, we must now reformulate the optimal control problem. As noted, since the outcome depends on the stochastic realization, the original problem is now ill-defined, and for every equation appearing in (<ref>)-(<ref>) which now would appear as probability-valued, some operation aggregating the distribution must be performed. 

    min_{h_j(t)}∈ℋ     ℛ_ξ(T) 
    subject to    dU(·;ξ)/dt=-iH(t;ξ)U(t;ξ) 
       ℙ_ξ[U(T) - U̅_∞≤η]≥ 1-β
       H(t;ξ):=∑_j=1^m h_j(t) H_j(t) 
        H_j(t;ξ) = α_j(t;ξ)Ĥ_j+(1-α_j(t;ξ))H̆_j, 
       α_j(t;ξ) = ℒ(𝒫)

Throughout we use ξ to denote the randomness in the process. A possible given value of ξ corresponds to a particular possible trajectory of α_j(t) for all j. ℒ is the law of the stochastic process 𝒫 described above governing α_j, that is the meaning of  (<ref>). 

While the controls themselves h_j(t) are deterministic, their effect on the state is mediated by the {α_j(t;ξ)} as expressed in the expression for the actual operator applied given in (<ref>). In (<ref>), we index the state by the stochastic realization ξ. Thus we have a random ODE, with an ODE defined for every possible value of ξ.

In the objective (<ref>), the time has been replaced by some operator ℛ_ξ of the time. In robust OCP this operator can be a statistical moment or a coherent risk measure (e.g., the expectation 𝔼[T], or the conditional value at risk, CVaR). 


Finally we remark on (<ref>). This is a chance constraint, respecting that we are not certain to arrive at the target U̅, and so we can at best aim to reach a neighborhood, defined by some η>0, with some high probability.
It can be observed that this expression resembles the probably approximately correct model of learning. In this sense, the robust optimization problem learns a gate set that aims to learn the procedure to form the desired unitary. The principled methodological introduction of statistical learning techniques for studying this problem would be a potentially interesting and useful topic for future work.



 §.§ Implications for Geometry and Complexity

It turns out that one can write the expression for the action principle for the geodesic equations as a function of the controls, and thus one can obtain the equivalent equation for minimizing the time as by minimizing the corresponding distance on the manifold. Now, however, the distance is considered in a robust sense; we are taking an expectation or risk measure computation of it. 

The link to gate complexity can be seen to have functional correspondence to the robust optimal control problem both directly
and mediated through the geometry. For the first, with the understanding that the optimal control shall be discretized in time, one can immediately consider the total number of discretized intervals to be the total quantity of operators applied, and thus the gate complexity. As the total number of intervals is itself variable, indeed it is the quantity to be minimized in the cost function, this quantity has an exact correspondence to the gate complexity. The chance constraint carries over, and the gate complexity is one of high confidence, probability 1-β for some small β. 

The gate complexity becomes more transparently linked trough this paradigm by the geometry. In particular, the choice of a finite gate set can be used to inform the metric in regards to path distances as depending on the direction of manifold traversal. In the Appendix we present some metrics associated with certain gate sets in the literature. Thus an operator can represent a functional operation on a qubit in the OCP, a pushforward along a geodesic path with a certain distance traversed for the geodesic functional minimization problem, and a gate in a circuit to perform some intended computational operation with varying associated progress towards the ultimate circuit computation desired. 





 §.§ Methods for solving the problem


The Magnus expansion <cit.> is a powerful tool for approximation of solutions of ordinary differential equations appearing throughout mathematics and physics. This has been applied with a great level of success to various fields of physics, including closed quantum optimal control <cit.>. On the other hand, when considering systems with inherent noise, stochastic differential equations are the appropriate model to use. The application of Magnus expansion techniques to stochastic differential equations has been limited, even though some literature exists <cit.>. The theory of stochastic Magnus expansion should serve as an interesting approach for the problem of robust quantum control.

On the other hand, a natural approach to solving the problems described above is Sample Average Approximation (SAA). In SAA one performs a number of samples of the random variables in the problem, and computes a sample average of the resulting deterministic optimization problems. 
Clearly, one needs to sample the random variables associated with the noise process, and thus  trajectories. Associated with each realization is a path U(t,ξ_l) and time T_ξ_l. The cost function could then be, in the case of ℛ_ξ = 𝔼_ξ, recognizing that the state is ξ dependent but not the control h_j(t).
In addition, in order to present a problem amenable to practical computation, the space of control functions also needs to be discretized. Specifically, we discretize the time by Δ t, i.e., set t_0=0, t_1=Δ t, t_2=2Δ t, etc. Given that with time optimal control, we do not know a priori how many time steps will be necessary, we incorporate an initial large value as a guess, noting that after any final time T^l, controls are not expected to influence the outcome for that particular trial.



§ DISCUSSION AND CONCLUSION

In this brief paper, we have discussed the time-optimal control problem for open quantum systems. We presented a robust control formulation for a model of a noisy open quantum system, where the noise is unitary, and discussed which methods and algorithms are equipped to solve this, in particular, we discussed applications of the Magnus expansion for stochastic differential equations as well as the Sample Average Approximation as means to numerically solve the control problems. 

In the Appendix we discuss some more details on the correspondence between geometry and gate complexity, and provide a theoretical bound on the gate complexity based on the corresponding derivation for the closed system by <cit.>. 

10
	
	altafini2004coherent
	Claudio Altafini.
	Coherent control of open quantum dynamical systems.
	Physical Review A, 70(6):062321, 2004.
	
	wu2007controllability
	Rong Wu, Alexander Pechen, Constantin Brif, and Herschel Rabitz.
	Controllability of open quantum systems with kraus-map dynamics.
	Journal of Physics A: Mathematical and Theoretical,
	40(21):5681, 2007.
	
	jover2017open
	JA Jover-Galtier.
	Open quantum systems: geometric description, dynamics and
		control.
	PhD thesis, PhD thesis, Universidad de Zaragoza, 2017.
	
	kallush2022controlling
	Shimshon Kallush, Roie Dann, and Ronnie Kosloff.
	Controlling the uncontrollable: Quantum control of open system
	dynamics.
	arXiv preprint arXiv:2205.05971, 2022.
	
	nielsen2006geometric
	Michael A Nielsen.
	A geometric approach to quantum circuit lower bounds.
	Quantum Information & Computation, 6(3):213–262, 2006.
	
	nielsen2006optimal
	Michael A Nielsen, Mark R Dowling, Mile Gu, and Andrew C Doherty.
	Optimal control, geometry, and quantum computing.
	Physical Review A, 73(6):062323, 2006.
	
	nielsen2006quantum
	Michael A Nielsen, Mark R Dowling, Mile Gu, and Andrew C Doherty.
	Quantum computation as geometry.
	Science, 311(5764):1133–1135, 2006.
	
	dowling2008geometry
	Mark R Dowling and Michael A Nielsen.
	The geometry of quantum computation.
	Quantum Information & Computation, 8(10):861–899, 2008.
	
	PhysRevA.78.032327
	Mile Gu, Andrew Doherty, and Michael A. Nielsen.
	Quantum control via geometry: An explicit example.
	Phys. Rev. A, 78:032327, Sep 2008.
	
	PhysRevD.100.046020
	Adam R. Brown and Leonard Susskind.
	Complexity geometry of a single qubit.
	Phys. Rev. D, 100:046020, Aug 2019.
	
	khaneja2002sub
	Navin Khaneja, Steffen J Glaser, and Roger Brockett.
	Sub-riemannian geometry and time optimal control of three spin
	systems: Quantum gates and coherence transfer.
	Physical Review A, 65(3):032301, 2002.
	
	PhysRevD.95.045010
	Adam R. Brown, Leonard Susskind, and Ying Zhao.
	Quantum complexity and negative curvature.
	Phys. Rev. D, 95:045010, Feb 2017.
	
	Jefferson2017
	Robert A. Jefferson and Robert C. Myers.
	Circuit complexity in quantum field theory.
	Journal of High Energy Physics, 2017(10):107, 2017.
	
	brown2018second
	Adam R Brown and Leonard Susskind.
	Second law of quantum complexity.
	Physical Review D, 97(8):086015, 2018.
	
	Haferkamp2022
	Jonas Haferkamp, Philippe Faist, Naga B. T. Kothakonda, Jens Eisert, and Nicole
	Yunger Halpern.
	Linear growth of quantum circuit complexity.
	Nature Physics, 18(5):528–532, 2022.
	
	Bulchandani2021
	Vir B. Bulchandani and S. L. Sondhi.
	How smooth is quantum complexity?
	Journal of High Energy Physics, 2021(10):230, 2021.
	
	brown2021quantum
	Adam R. Brown.
	A Quantum Complexity Lowerbound from Differential Geometry.
	12 2021.
	
	auzzi2021geometry
	Roberto Auzzi, Stefano Baiguera, G Bruno De Luca, Andrea Legramandi, Giuseppe
	Nardelli, and Nicolò Zenoni.
	Geometry of quantum complexity.
	Physical Review D, 103(10):106021, 2021.
	
	tibbetts2012exploring
	Katharine W Moore Tibbetts, Constantin Brif, Matthew D Grace, Ashley Donovan,
	David L Hocker, Tak-San Ho, Re-Bing Wu, and Herschel Rabitz.
	Exploring the tradeoff between fidelity and time optimal control of
	quantum unitary transformations.
	Physical Review A, 86(6):062309, 2012.
	
	blanes2009magnus
	Sergio Blanes, Fernando Casas, Jose-Angel Oteo, and José Ros.
	The magnus expansion and some of its applications.
	Physics reports, 470(5-6):151–238, 2009.
	
	marecek2020quantum
	Jakub Marecek and Jiri Vala.
	Quantum optimal control via magnus expansion and non-commutative
	polynomial optimization.
	arXiv preprint arXiv:2001.06464, 2020.
	
	bondar2022quantum
	Denys I Bondar, Kurt Jacobs, Georgios Korpas, Jakub Marecek, et al.
	Quantum optimal control via polynomial optimization: A globally
	convergent approach.
	arXiv preprint arXiv:2209.05790, 2022.
	
	wang2020magnus
	Zhenyu Wang, Qiang Ma, Zhen Yao, and Xiaohua Ding.
	The magnus expansion for stochastic differential equations.
	Journal of Nonlinear Science, 30:419–447, 2020.
	
	wang2020new
	Xiaoling Wang, Xiaofei Guan, and Pei Yin.
	A new explicit magnus expansion for nonlinear stochastic differential
	equations.
	Mathematics, 8(2):183, 2020.
	
	yang2021class
	Guoguo Yang, Kevin Burrage, Yoshio Komori, Pamela Burrage, and Xiaohua Ding.
	A class of new magnus-type methods for semi-linear non-commutative
	ito stochastic differential equations.
	Numerical Algorithms, pages 1–25, 2021.
	
	Brown:2022phc
	Adam R. Brown.
	Polynomial Equivalence of Complexity Geometries.
	5 2022.
	
	khaneja2005optimal
	Navin Khaneja, Timo Reiss, Cindie Kehlet, Thomas Schulte-Herbrüggen, and
	Steffen J Glaser.
	Optimal control of coupled spin dynamics: design of nmr pulse
	sequences by gradient ascent algorithms.
	Journal of magnetic resonance, 172(2):296–305, 2005.
	
	layden2022first
	David Layden.
	First-order trotter error from a second-order perspective.
	Physical Review Letters, 128(21):210501, 2022.
	








§ GATE COMPLEXITY AND GEOMETRY

Following Nielsen et al., we are interested in studying distances on the group manifold SU(2^n) with respect to various example metrics. A set of bases for the tangent space of SU(2^n) is provided by the generalized Pauli matrices σ_I, I=1,…,2^2n-1, given by traceless tensor products of the ordinary Pauli matrices and the identity matrix. As an example, the tangent space of the two qubit case, n=2, is spanned by the fifteen matrices

    {σ_j⊗1, 1⊗σ_j, σ_j⊗σ_k},     j,k=x,y,z.

We further define the weight of an element in the generalized Pauli basis as the number of factors in the tensor product not equal to the identity. In the two qubit example this means that {σ_j⊗1, 1⊗σ_j} has weight one, while {σ_j⊗σ_k} has weight two. 



 §.§ Gate complexity
 
Gate complexity (sometimes called circuit complexity) is a measure on how complicated it is to generate, or at least approximate, a certain state or unitary operator. As such, it is given by the minimal number of primitive gates needed in the circuit to approximate the requested state or unitary to within some error.




We let 𝒞^A_ϵ(U) be the minimum size of a quantum circuit with gates A that ϵ-approximates U.


To fully characterize the gate complexity of a given system we then need to pick a set of primitive gates together with a tolerance level ϵ. From the Solovay-Kitaev theorem, we know that given any physically universal gate set, a target unitary, and accuracy ϵ, the number of gates that are needed to approximate the target unitary to  the entrywise ϵ accuracy is log^O(1)(1/ϵ). 



One drawback of gate complexity, that led to the introduction of complexity geometry by Nielsen and collaborators, is that it is discontinuous. Since the circuit is discrete, there can be points in the space of unitaries that are arbitrarily close in the ordinary inner product sense, but exponentially far away in gate complexity. By considering a continuous time-optimal control problem, Nielsen and collaborators, <cit.>, presented a framework of using optimal control theory, with its comprehensive literature of theoretical guarantees and algorithms, to make definitive statements regarding otherwise cumbersome analysis of gate complexity outright.









 §.§ Metrics

Points on the manifold SU(2^n) correspond to unitary matrices U and we thus construct metrics by studying the distance to a nearby point U+dU. The most straightforward example is the ordinary inner-product, or Killing, metric

    ds^2=[dU^† dU]=∑_I,J[idU U^†σ_I]δ_IJ[idU U^†σ_J],

where the trace has been normalized such that [1]=1. The approach of Nielsen et al. was to generalize this metric by introducing a penalty matrix ℐ_IJ that encodes the idea that certain directions on SU(2^n) might be more costly to move in than others. Here, ℐ_JK is positive and symmetric. The resulting family of metrics is given by

    ds^2=∑_I,J[idU U^†σ_I]ℐ_IJ[idU U^†σ_J].

An important aspect of these metrics is that they are right-invariant, meaning that it is invariant under U→ UU_R, while, in contrast, generally not being left-invariant. A metric that is both right- and left-invariant is called bi-invariant, and the ordinary inner-product metric of (<ref>) is an example. 


We will assume that ℐ_IJ is diagonal with respect to the generalized Pauli basis, such that the metric becomes

    ds^2=∑_Iℐ_II[idU U^†σ_I]^2.

A natural choice for the metric is to penalize directions with high weight, i.e. making it easier to act on a small number of qubits. The penalty matrix is then only dependent on the weight of the basis element and we specify the metric completely by specifying  ℐ_IIℐ_k for σ_I having weight k. Three such examples of metrics are studied in <cit.>:

    
  * Firstly, we can consider the case of penalizing basis directions with weight higher than two. In other words we set ℐ_II=ℐ_k=1 whenever σ_I has weight k=1,2, and ℐ_II=ℐ_k=k when σ_I has weight k>2. This is often referred to as the cliff metric, and corresponds to the case already studied in the original works by Nielsen et al. <cit.>.
    
    
  * Secondly, we can consider adding a penalty that depends on how often a certain weight in the basis appears. For the generalized Pauli basis, there are exactly [ n; k ]3^k elements having weight k. We can thus consider the binomial metric as having ℐ_k(α)=([ n; k ]3^k)^α, for some parameter α <cit.>. 
    
    
  * Finally, we can consider simply increasing the penalty with increasing weight. This gives the exponential metric, ℐ_k(x)=x^2k of <cit.>. 
    

Of course, in the single qubit case we only have weight one operators and the above is not applicable. A natural approach is then to pick out one particular direction, say ℐ_zz, to penalize, setting ℐ_xx=ℐ_yy=1 <cit.>. Similarly, for the two qubit case we simply penalize the directions with weight two (corresponding to the operators {σ_j⊗σ_k}), setting ℐ_II=1 for the other directions.  




 §.§ Geodesics and optimal control

The important insight of Nielsen et al. was to equate the optimal value of the cost function with a right invariant metric on SU(2^n),

    c(H,T)=∫_0^T√(g(H(t), H(t)))dt,

where g(·,·) denotes a specific metric. This is equal to the length of the curve mapped out by the Schrödinger evolution. When we do not have any noise, we can express the Hamiltonian in the generalized Pauli basis as

    H(t)=∑_I h_I(t)σ_I.

For the general family of metrics, (<ref>), we then find 

    g(H,H)=∑_I ℐ_IIh_I^2.

We now define the operator complexity by

    C(U)=inf_H,Tc(H,T),

where we take the infimum over the time T and over the control Hamiltonians that synthesize U̅. Looking for minimal curves on manifolds is of course the same as looking for minimal length geodesics with respect to the given metric. Thus, in the case wherein the control spans the space, which corresponds to the generality of parametrizing an arbitrary curve, the cost can be identically computed by solving the optimal control problem as solving the geodesic equations. 



 §.§ Geodesics with Unitary Noise


If we assume that the noise is Hermitian, such that the geometry is preserved. We can then expand H̆ in the generalized Pauli basis,

    H̆_J=∑_I M_IJσ_I,

for some constants, or possibly time dependent, M_IJ. We now find that the “difficulty" of applying H is given by

    g(H,H)=   ∑_I ℐ_II(α_I h_I)^2
       +2∑_I∑_J≠ Iℐ_IIα_I(1-α_J)h_Ih_JM_IJ
       +∑_I,J,Kℐ_II(1-α_I)(1-α_J)h_Ih_J M_KIM_KJ,

and the length of the trajectory is given by

    c(H,T)=∫_0^T√(g(H(t),H(t)))dt.




§ BOUNDING GATE COMPLEXITY

To bound the gate complexity, we follow Brown <cit.> and make three approximations of our path. Our target unitary U̅ is given by

    U̅=𝒫exp[ i∫ dt H(t)].

We now make three approximations

    
  * We first cut out the most expensive components by introducing a cut-off ℐ̅,
    
    H(t)→  H_P(t)=∑_I
    ℐ_II<ℐ̅h_I(t)H_I(t).

    
    
  * Next, we divide the path into S equal steps of inner-product length δ and take the average Hamiltonian on each step,
    
    𝒫exp[ i∫_T^T+δ dt H(t)]→exp[ i∫_T^T+δ dt H(t)],

    for each time possible time T. This is similar to the popular GRAPE algorithm <cit.>.
    
    
  * Finally, we “trotterize", meaning that we apply each term in the expansion of the Hamiltonian sequentially,
    
    exp[i∫ dt∑_I h_I(t)H_I(t)]→∏_Iexp[i∫ dt h_I(t)H_I(t)].


Each of these steps introduces some error that we need to bound. To this end, we introduce the notation s(·,·) for the Killing metric. Note that the relation to g(·,·) of say Eq. (<ref>) is just to set ℐ_IJ=δ_IJ. 


    
  * In the Killing metric, the error from pruning is bounded by realising
    
    s   (𝒫e^i∫ H(t)dt,𝒫e^i∫ H_P(t)dt)
    ≤   ∫ dt√(Tr[(H(t)-H_P(t))^2])
    
                =   ∫ dt√(Tr[(∑_I:ℐ_II≥ℐ̅h_IH_I(t))^2]).

    We recognize the factor under the square root as (<ref>) with ℐ_II=1 and where the summand is restricted due to the pruning. Denoting Γ^2 g(H,H) we have
    
    Γ^2=∑_I ℐ_II(…)≥ℐ̅∑_I: ℐ_II≥ℐ̅(…),

    where the dots represent everything within the sum of (<ref>). This gives us
    
    s(𝒫e^i∫ H(t)dt,𝒫e^i∫ H_p(t)dt)≤∫ dt Γ/√(ℐ̅).

    
    
    
  * To find the Killing error from averaging, we first note that it is a known fact that for any operators A and B we have <cit.>
    
    AB_F≤A_FB_op.,

    where we normalise the Frobenius norm such that H(t)≤ 1. Brown also shows that, for a Hamiltonian H with N non-zero generalized Pauli matrices, we have the inequality
    
    H_op.≤√(N)H_F.

    Combining these two results we have
    
    H_1⋯ H_m_F≤ N^m-1/2H_1_F⋯H_m_F.

    Now, to bound the error from averaging we use the Dyson expansion. For one time interval t∈ [0,δ] we write H_av.δ^-1∫_0^δ dtH_P(t), and we thus have
 
    0.5!exp[i∫_0^δ dtH_P(t)]-𝒫exp[i∫_0^δ dtH_P(t)]_F
    
                =   ∑_m=2^∞(-iH_av.δ)^m/m!-∑_m=2^∞(-i)^m∫_0^δ dt_1∫_0^t_1dt_2⋯∫_0^t_m-1dt_mH_P(t_1)⋯ H_P(t_m)_F
    ≤   ∑_m=2^∞(-iH_av.δ)^m_F/m!+∑_m=2^∞∫_0^δ dt_1⋯∫_0^t_m-1dt_mH_P(t_1)⋯ H_P(t_m)_F
    ≤   2∑_m=2^∞N^m-1/2δ^m/m!
    ≤   2(e^√(N)δ-1-√(N)δ)/√(N),

where we used our normalisation H_F≤ 1. If we now pick δ<N^-12 we find

    exp[i∫_0^δ dtH_P(t)]-𝒫exp[i∫_0^δ dtH_P(t)]_F< 2√(N)δ^2,

which implies that the Killing error is bounded by

    s(𝒫exp[i∫_0^δ dtH_P(t)],exp[i∫_0^δ dt H_P(t)])<π√(N)δ^2,

where we used that the Killing metric is bounded by the Frobenius norm <cit.>.

    
  * Finally, the error from the trotterization has been actively studied in recent years, see for example <cit.>. We consider the error
    
    err._trot.   e^i∫_T^T+δdt∑_I H_I-∏_I=1^N( e^i∫_T^T+δdtH_I)
    
            =   1/2∑_I∑_J<I[H_I,H_J]δ^2+𝒪(δ^3).

    In our case, when we have noisy control Hamiltonians, the consideration is a bit more subtle than in the closed quantum case of <cit.>, since we can have constructive interference 


We will expand on point 3. above and finish bounding the gate complexity of the open quantum system similar to the discussion in  Section 3.2 of <cit.> in future work.



