Ansatz-Agnostic Exponential Resource Saving in Variational Quantum Algorithms Using Shallow Shadows

1 Introduction

The field of quantum computing has witnessed significant progress over the past decade. In the current Noisy Intermediate Scale Quantum (NISQ) [Preskill, 2018] era, quantum devices are small and error-prone. Despite this, several research groups have successfully demonstrated quantum advantage over classical computers in synthetic but well-defined sampling problems [Arute et al., 2019; Zhong et al., 2020; Madsen et al., 2022]. The next major breakthrough in this field will involve extending these advantages to solve practically valuable problems.

Many proposals have been put forward, and one that stands out is Variational Quantum Algorithms (VQAs) [McClean et al., 2016]. These algorithms are specifically designed to solve optimization problems involving quantum information, stored as quantum states using quantum bits (i.e., qubits), manipulated through quantum circuits, and measured using quantum observables. Many important functions involving these objects, such as the expectation values of observables with respect to different states, are notoriously hard or intractable to evaluate on classical computers, as the required classical computational resources increases exponentially in the number of qubits involved. By using parameterized quantum circuits, such functions can be estimated with polynomially many quantum resources on quantum devices, thereby enabling optimization using iterative optimization algorithms. Potentially useful applications include Variational Quantum Eigensolver [Peruzzo et al., 2014], Quantum Support Vector Machines [Havl´ıˇcek et al., 2019], Quantum Approximate Optimization Algorithm [Farhi et al., 2014], etc.

Unlike classical computing, the absence of quantummemory devices, combined with the no-cloning theorem, implies that each use of a quantum state necessitates preparing it from scratch. In the context of VQAs, we refer to the term sample complexity to denote the total number of executions of the quantum preparation device required (equivalently, the total number of copies of quantum states consumed). In the standard VQA model, this scales linearly with the total number of function evaluations needed throughout the optimization. When additional factors such as hyperparameter tuning, model and ansatz selection are introduced, the scale of this number becomes notably significant. Moreover, in the near term, only very few capable quantum computers would be available, making the implementation of VQAs with reduced sample complexity crucial.

Classical shadow tomography [Huang et al., 2020] provides an exponentially improved method to estimate linear functionals that involve quantum states. This advancement has been incorporated into the VQA training protocols, leading to an exponential reduction in quantum resources, as demonstrated in [Basheer et al., 2023]. However, the method, titled Alternating Layered Shadow Optimization (ALSO), uses a version of shadow tomography that requires local target observables. This constraint restricts the ansatzes to require simple entanglement structures, such as the Alternating Layered Ansatz (ALA) illustrated in Figure 1(a). This limitation becomes significant when the optimal circuit or state cannot be approximated with ALAs.

The recently proposed shallow shadow technique [Bertoni et al., 2023] describes a tomography procedure similar to classical shadow tomography but designed for easy implementation in NISQ devices. Even better, it does not rely directly on the locality of the observables. Building upon this, we introduce Ansatz Independent Shadow Optimization (AISO) in this work - a method that achieves an exponential reduction in quantum resources for VQA training. AISO is compatible with almost any shallow (depth logarithmic in the number of qubits) quantum circuit structure found in the literature when used in conjunction with observables of low Frobenius norm. We demonstrate these resource savings for two important problems in quantum information where VQAs are applicable: Variational Quantum State Preparation (VQSP) and Variational Quantum Circuit Synthesis (VQCS). Both problems involve determining the optimal circuit parameters for an ansatz that best approximates unknown quantum states or circuits.

The benefits of AISO can be summarized as follows:

1. Exponential reduction in input state copies: AISO achieves arbitrarily precise estimates of all function evaluations encountered during iterative optimization of the VQA cost function while consuming exponentially fewer copies of the input state compared to standard VQA. This enables more iterations, better approximations, and facilitates extensive hyperparameter tuning.
2. Ansatz-agnostic implementation on quantum hardware: Our method ensures a reduction in input state copies for almost any shallow ansatz studied in the literature. Additionally, the operations executed on the quantum device remain independent of the chosen ansatz.
3. Optimization with different ansatzes: The combination of the above two advantages implies that, for a given unknown input state or circuit, optimization can be performed over various types of ansatzes, using the same shallow shadows generated in an ansatz agnostic manner, unlike standard methods where multiple ansatzes must be implemented individually. This flexibility allows one to choose the most suitable ansatz with substantial savings in the utilization of quantum devices.
4. Compatibility with VQCS: Solving VQCS requires the utilization of maximally entangled states. Due to the requirement of ansatzes with limited entanglement for ALSO, it is not suitable for efficiently implementing VQCS. In contrast, AISO is ansatz independent, allowing its effective use in VQCS.

The advantage is experimentally demonstrated in both use cases of interest, where we show that AISO significantly outperforms standard VQA with the same number of copies across four different ansatzes: Alternating Layered Ansatz [Cerezo et al., 2021], Multi-Entanglement Renormalization Ansatz (MERA) [Bridgeman et al., 2015], Hardware Efficient Ansatz (HEA) [Leone et al., 2022], and Tree Tensor Networks (TTN) [Shi et al., 2006] (cf. Figure 1).

We also establish that the sample complexity of AISO, and consequently shallow shadows, can be enhanced when the input state being sampled is from a 2-design instead of a 1design [Harrow and Low, 2009]. Finally, we discuss how AISO aligns with many heuristic methods commonly used to tackle trainability issues, such as barren plateaus, that may arise during optimization.

2 RelatedWorks

Classical shadows have been used to improve the sample complexity of VQAs in [Basheer et al., 2023]. This method, termed ALSO, utilizes a form of shadow tomography relying on local target observables and assumes that the ansatz has a weak entanglement structure, such as an ALA. Consequently, for applications such as VQSP, results can be poor if the optimal state is not approximable by ALAs. Additionally, this method is unsuitable for VQCS since it necessitates working with the maximally entangled state. In contrast, our method AISO uses shallow shadows, allowing it to be used with almost any shallow ansatz studied in the literature, addressing both VQSP and VQCS.

In [Schreiber et al., 2022], classical shadows have been employed to reduce the number of quantum computer calls (i.e., sample complexity) in quantummachine learning applications. Given an already learned VQA model, the approach uses a quantum computer to generate classical shadows so that predictions can be made of the learned model using a classical computer. It is important to note that, in this approach, the learning procedure is still carried out on a quantum computer. In contrast, in AISO, the entire learning procedure takes place on a classical computer.

New classical optimization algorithms, as introduced in [Boyd and Koczor, 2022; Wierichs et al., 2020; Stokes et al., 2020], demonstrate faster convergence rates with significantly fewer iterations than traditional gradient descent. For applications involving shallow circuits and low Frobenius norm observables, AISO, being agnostic towards the choice of classical optimizer, can enhance the performance of these methods by significantly reducing the required number of state copies.

A new related work appears after the completion of ours. In [Cerezo et al., 2023], the authors conjecture that VQA models that can avoid barren plateaus are also classically simulable (with quantum experiments polynomial in the number of qubits). Strong evidence is also provided to support their conjecture. In their terms, our approach actually shows that VQA problems with shallow ansatz and low Frobenius norm observables are also classically simulable, but it is still unclear if these models are barren plateau-free.

3 Background

In this section, we review quantum computing, shallow shadows, and VQAs.

3.1 QuantumComputing

Throughout this work, we use the 'ket' and 'bra' notations to denote column vectors |ψ⟩ and their conjugate transposes ⟨ψ| respectively. |i⟩ ∈ Cd is the ith standard basis vector. We use L(Cd ) to denote the set of all linear operators that act on Cd , and for any operator A, A† is its conjugate transpose.

A quantum state is defined as a positive semidefinite operator ρ ∈ L(Cd ) with tr(ρ) = 1. In quantum computing, a qubit is the analog of a bit in classical computing and can admit any quantum state in L(C2 ) as its value. The state of an n-qubit system can be described using states that act on the tensor product of n two-dimensional vector spaces, denoted as C2 ⊗ · · · ⊗ C2 ∼= C2n .

A quantum gate acting on n qubits is a unitary operator U ∈ L(C2n ). Such a gate transforms the state of an n-qubit system from ρ to UρU † . The Pauli gates are defined as

Let P = {1,X, Y,Z}. For γ ∈ {1,-1, i,-i}, we write P (γ) n for the set of all n-fold tensor products of the elements in P, with the scalar γ multiplied to them. Clearly, Pn = P (1) n ∪P (-1) n ∪P (i) n ∪P (-i) n forms a group under matrix multiplication. The n-qubit Clifford gates are those contained in the normalizer of Pn in the group of unitary operators acting on C2n . A quantum circuit is defined as a composition of multiple quantum gates.

To extract information from a quantum system in a state ρ, we perform a measurement using an observable, defined as any Hermitian operator O. Let the spectral decomposition of O be O = ∑i λi |ui⟩ ⟨ui|. The measurement yields an outcome λi with probability ⟨ui| ρ |ui⟩. Subsequently, the post-measurement state becomes |ui⟩. In addition, the expected value of this random procedure is tr(ρO), concisely written as ⟨O⟩ρ. Measurements using diagonal observables are called standard basis measurements.

Pure states are rank one states. In this case, gate operations and measurements can be fully described by any normalized eigenvector in its support.

3.2 Shallow Shadows

For an arbitrary state ρ and known observables O1,O2, . . . ,OM, it requires O(2n · M) copies of ρ to estimate ⟨Oi⟩ρ for each i using conventional quantum tomography techniques. Using classical shadow tomography [Huang et al., 2020], the dependence on M can be reduced exponentially. Furthermore, for certain classes of observables, the dependence on n is O(poly(n)), and thus the total number of copies required in these cases can be reduced to O(poly(n) · logM).

To generate a shadow, we first apply a circuit U sampled from an ensemble U of n-qubit circuits, and then measure the resultant state according to the standard basis to obtain an n-bit string u. A classical shadow is computed classically as

where

Furthermore, ˆ ρU,u gives an unbiased estimator of ρ and hence ⟨Oi⟩ˆ ρU,u is an unbiased estimator of ⟨Oi⟩ρ for all i.

The number of such shadows required for precise estimation is dominated by the state-dependent shadow norm of the traceless part of the observables, defined as

where ˜O = O- tr(O) 2n 1. Using this, the sample complexity of the protocol is given by the following theorem.

Theorem 1. [Huang et al., 2020] Let U be an ensemble of circuits such that ∆-1 U exists, and O1,O2, . . . ,OM be n-qubit observables. For any δ, ϵ ∈ (0, 1), let T1 = 2 log(2M/δ) and T2 = (34/ϵ2 )maxi ∥˜ Oi∥2ρ,U . Let ρ be a state with classical shadows (generated using U) ˆ ρ1, ˆ ρ2, . . . , ˆ ρT1T2 , where ˆ ρi = ˆ ρUi,ui . Define ⟨̂ Oi⟩ρ = µT1,T2 ({⟨Oi⟩ ˆ ρj , 1 ≤ j ≤ T1T2}), where µT1,T2 is the median-of-means estimator (median of T1 means of T2 values each). Then, with probability at least 1 - δ, we have |⟨̂ Oi⟩ρ - ⟨Oi⟩ρ| ≤ ϵ for all i.

Define shadow norm as ∥·∥U :=maxσ:state ∥·∥σ,U. In Theorem 1, we can also replace ∥˜ Oi∥ρ,U with ∥˜ Oi∥U [Huang et al., 2020], which removes the dependency on ρ and provides the worst-case sample complexity of the protocol.

In [Huang et al., 2020], it was shown that when the ensemble is the Clifford group over n qubits, the shadow norm of the observables, and hence the sample complexity, are proportional to the Frobenius norm. But the implementation requires very deep circuits, ruling itself out for NISQ devices.

[Bertoni et al., 2023] proposed an ensemble of shallowdepth circuits Ud (with depth d), given in Figure 2, that achieves similar performance guarantees. Each two-qubit subcircuit here is a uniformly randomly sampled two-qubit Clifford gate. The shadow can be classically computed and stored in the matrix product state form, with cost O(2d ). Formally, we have

Theorem 2. [Bertoni et al., 2023] If d = Θ(logn), then ∥O∥21/2n ,Ud ≤ 4∥O∥2F for any observable O with tr(O) = 0, where ∥ · ∥F is the Frobenius norm.

The term ∥O∥21/2n ,Ud in Theorem 2 is called the locally scrambled shadow norm. For any ensemble D1 of states, if Eρ∼D1 (ρ) = 1/2n (also called state 1-designs when all states are pure), we have ∥O∥21/2n ,U = Eρ∼D1 ∥O∥2ρ,U . Hence, we can view ∥O∥1/2n ,U as a quantity that intuitively characterizes the sample complexity of a shadow protocol for a "typical" state or the performance of the protocol on average, similar to how the shadow norm describes the worst-case performance. This is more apparent when all states in D1 are pure. Then, sampling from D1 is equivalent in mean to sampling uniformly (according to the spherical measure) from the set of all pure states. Throughout this work, we set d = Θ(log n).

3.3 Variational QuantumAlgorithms

Parameterized quantum circuits can be used to encode various optimization problems that one encounters in quantum information. The circuit structure used is called an ansatz. We use U(θ) to denote a parameterized circuit, where θ is a vector of parameters. In standard VQA, we use U(θ) to estimate the value of a target function and then optimize the parameters by feeding the output to a classical iterative optimizer.

For any ansatz U, we define ρ(θ) := U(θ)ρU(θ)† . Our focus in this paper is on the function defined (over θ) as

where ρ is the input quantum state and O is an output observable, and we aim to find the parameters that maximize it. One can estimate ⟨O⟩ρ(θ) for any θ by repeated measurements, after the application of U(θ) on ρ. Given this ability, the gradient of ⟨O⟩ρ(θ) can also be estimated using standard methods such as finite differencing or quantum-specific approaches such as the parameter shift rule [Mitarai et al., 2018]. Problems in quantum information that can be reduced to an instance of optimization of Eq. (5) include variational quantum eigensolver [Peruzzo et al., 2014], quantum autoencoder [Romero et al., 2017], as well as VQSP and VQCS.

4 Ansatz Independent ShadowOptimization

In this section, we explain the main idea and theoretical results behind AISO.

For any quantum circuit V and any qubit i, we define the number of times a gate touches or crosses the qubit wire as RV,i. Formally, this is the number of 2-qubit gates being applied on any qubits j, k such that j ≤ i ≤ k. Let RV = maxi RV,i. We require our ansatz U to have RU ∈ O(log n). Most shallow ansatzes used in the literature satisfy this. Let ⟨O⟩ρ(θ(1) ) , ⟨O⟩ρ(θ(2 ) , . . . , ⟨O⟩ρ(θ(C) ) be function evaluations that one encountered while optimizing Eq. (5) using an iterative optimization algorithm.

Define WO(θ) = U(θ)†OU(θ). Each function evaluation can be seen as estimating the expectation of ρ with these parameterized observables because

Moreover, the Frobenius norm remains invariant since ∥O∥2F = ∥V OV † ∥2F for any unitary V .

Now, using Theorems 1 and 2, we can estimate all C function evaluations using shallow shadows, and the AISO protocol goes as follows.

1. Choose precision and confidence parameters ϵ, δ ∈ (0, 1). Let m ≥ 1/δ. Generate T1T2 shallow shadows of ρ, where

Let them be ˆ ρU1,u1 , ˆ ρU2,u2 , . . . , ˆ ρUT1T2 ,uT1T2 .

1. Use the iterative optimization algorithm to optimize the target function

Now, we shall prove that when T1 and T2 satisfy Eq. (7). the AISO protocol achieves the desired precision and confidence.

Theorem 3. Let ρ be an n-qubit pure state sampled from a state 1-design D1. For any δ, ϵ ∈ (0, 1), m > 1/δ, and any C > 0, let T1 and T2 satisfy Eq. (7). Then, for any parameter vectors θ(1) , . . . , θ(C) , with probability at least 1-δ, we have |⟨WO(θ(c) )⟩ρ - ⟨̂ WO(θ(c) )⟩ρ| ≤ ϵ for all 1 ≤ c ≤ C, where ⟨WO(θ(c) )⟩ρ and ⟨̂ WO(θ(c) )⟩ρ are defined in Eq.s (6) and (8), respectively.

The rationale behind AISO's ability to yield exponential savings in estimating the cost function can be intuitively grasped as follows. In standard VQA, estimating C evaluations requires preparing U(θ(c) ) for all c and conducting multiple measurements for each. Therefore, the total number of required copies would be O(C). One key limitation arises from the inability to reuse measurement results, as each measurement is conducted specifically to estimate ⟨WO(θ(c) )⟩ρ for a particular c. In contrast, in AISO, all quantummeasurements made are independent of θ(c) , and these measurements are used when estimating all the expectations.

Figure 3: Tensor networks to compute ⟨WO(θ)⟩ˆ ρ.

Although the constants in Eq. (7) appear large, due to the use of union bounds as well as a few loose constants, in practice significantly lesser copies than what is suggested there suffice. We explore this in detail in our experimental results.

The cost of classical computation is dominated by the cost of computing ⟨̂ WO(θ)⟩ρ classically. Thus we have the following theorem.

Theorem 4. In AISO, for any quantum ansatz U with RU ∈ O(logn), ⟨̂ WO(θ)⟩ρ can be classically evaluated with cost O(poly(n) · logC · ∥O∥2F ) for VQSP and VQCS. The overall classical computational cost for C function evaluations is thus O(poly(n) · C log C · ∥O∥2F ).

Note that since the circuit is being implemented classically, RU has no physical relevance here. The space complexity of the protocol is dominated by the storage of shallow shadows. Each shadow is an MPS with maximum bond dimension at most 2d-1 . This means that each shadow can be stored using at most n2d complex numbers and hence the total space complexity is at most nT1T22d . So, when d = O(log n), the space complexity is O(poly(n) · T1T2).

5 Applications

In this section, we discuss how AISO can be used to tackle two important problems in quantum information.

5.1 Variational Quantum State Preparation

In VQSP, our goal is to find a circuit that is capable of (approximately) preparing a pure state ρ = |ψ⟩ ⟨ψ|, given access to multiple copies of it. That is, we would like to find a parameter vector θ that minimizes the infidelity between U(θ)† |0⟩ and |ψ⟩, defined as 1 - | ⟨ψ|U(θ)† |0⟩ |2 , where U is a heuristically chosen ansatz. Infidelity assumes values in [0, 1] and is widely used in quantum information to measure how far apart two states are, with 1 implying orthogonality and 0 implying equality. Note that the minimization of infidelity is the same as the maximization of ⟨|0⟩ ⟨0|⟩ρ(θ). Since |0⟩ ⟨0| has unit Frobenius norm, this objective function is compatible with AISO. Moreover, with AISO, it becomes possible to explore optimal parameters for a diverse range of circuit ansatzes through multiple optimization procedures while minimizing the number of required copies.

Last but not least, for any shallow shadow ˆ ρ, ⟨WO(θ)⟩ˆ ρ can be computed classically efficiently by contracting the tensor network given in Figure 3(a). Even though the example given here is the ALA, using Theorem 4, one can easily replace it with any ansatz with RU ∈ O(logn). The reasoning is explained in detail in the proof of Theorem 4 in the Appendix.

5.2 Variational QuantumCircuit Synthesis

VQCS is a natural extension of VQSP to quantum circuits. Here, our goal is to learn the parameters of an n-qubit ansatz U(θ) that best approximates a given unknown quantum gate V . Similar to how we use infidelity for quantum states, we can use the Hilbert-Schmidt cost function defined for unitaries in [Khatri et al., 2019]. For any θ, this is computed as H(θ) = 1 - |tr(U(θ)†V )|2 /4n and minimizing H gives us the set of parameters that (approximately) prepares V .

To see why, first note that any quantum gate W can be uniquely identified using a representation given as W ⊗W, where W is the complex conjugate of W. This can be derived from its action on the vectorized version of elements in L(C2n ). Then we see that H(θ) is proportional to ∥U(θ) ⊗ U(θ) -V ⊗V ∥2F . To evaluate H(θ) for any θ, we start with the maximally entangled state on two n-qubit systems, defined as |Φ⟩ = 1/√2n ∑2n-1 i=0 |i⟩ |i⟩. Then, we apply V on the second register to obtain |V ⟩ = 1/√2n ∑2n-1 i=0 |i⟩ |v·i⟩, where |v·i⟩ is the ith column of V . Then, one can see that H(θ) = 1 - ⟨|U(θ)⟩ ⟨U(θ)|⟩|V ⟩⟨V |. Therefore, we can use shallow shadows of |V ⟩ to estimate H(θ). Since ∥ |U(θ)⟩ ⟨U(θ)| ∥F = 1 for all θ, the number of shadows, or equivalently, the number of applications of V , is independent of n.

In terms of classical computational complexity, ⟨|U(θ)⟩ ⟨U(θ)|⟩ˆ ρ for any shallow shadow ˆ ρ can be computed by contracting the tensor network given in Figure 3(b), the cost of which is polynomial in n. The explanation regarding the usage of ALA in this figure is the same as the one for VQSP. From now on, when discussing the sample complexity of VQCS, the "number of copies" will mean the number of copies of |V ⟩ consumed (equivalently, the number of applications of V ).

6 Simulation Results

Here we elaborate on the experimental results by comparing the sample complexity of AISO and the standard VQA in the two use cases discussed above.

The depth d of the shallow shadow ensemble (cf. Figure 2) is set to 3 throughout the experiments. The viability of AISO in solving both problems is tested across four different ansatzes that are widely used in the literature, whose structures are given in Figure 1(a,b,c,d). Except in HEA, all two-qubit gates can be arbitrary two-qubit subcircuits. The specific ones used in our simulation are given in Figure 1(e). Also, for VQCS, each two-qubit subcircuit is a combination of two of these. In HEA, the two-qubit gate used is the CNOT gate.

For VQSP, we have used the Simultaneous Perturbation Stochastic Approximation [Spall, 1992] (SPSA), where the converging sequences used are, respectively, cr = ar = r-0.4 and the total number of iterations is 5000. On the other hand, the results of VQCS have used Powell's method [Powell, 1964] with a maximum of 103 function evaluations allowed. We denote by AISO/VQA (T) the AISO/VQA algorithm that uses T copies in total. This means that VQA (T) will consume T/104 copies per function evaluation in SPSA and T/103 copies in Powell's method. This is because SPSA requires two function evaluations to produce estimates of the gradient.

The unknown target states considered in the VQSP are 8qubit states, which are also compatible with the corresponding ansatzes being used. In each setting, the experiment is carried out across five different states and the results are shown in Figure 4. Here, we have plotted the mean of infidelity values achieved at different iterations across the five different experiments that were carried out. The shaded region comprises the mean plus and minus 0.3 times the standard deviation of the five different infidelities.

In Figure 4, VQA (5×105 ), which utlizes 5×105 copies in total, consumes 50 state copies per function evaluation. Similarly, the other VQA algorithms consume 100 and 250 state copies per evaluation. One can see that AISO closely matches or outperforms the results of VQA by consuming only 104 copies in total.

Moving on to VQCS, similar experiments are carried out for 4-qubit quantum gates (meaning 8-qubits used in total). The results are summarized in Figure 5. Here, the minimum H(θ) in each interval of 102 function evaluations out of the total allowed 103 is plotted. The three VQA algorithms used here consume 102 , 103 and 104 copies per function evaluation respectively. It is clear from the plots that AISO can match the performance of standard VQA similarly using considerably fewer copies to what we saw in the case of VQSP.

In Figures 6 and 7, we present the superiority of AISO over VQA in a different light. On the x-axis, we plot different infidelity or Hilbert-Schmidt cost values, and on the y-axis, we plot the number of copies required to achieve them, which are exponentially better for AISO.

7 Improved Bounds Using 2-Design Assumption

In this section, we analyze the assumption of the input state in more detail. The assumption that the state is sampled from a 1-design merely says that the input state is the maximally mixed state. So, to further understand the notion of a "typical input state" and to get closer to the notion of the input state being an average state or a randomly generated state, we make a stronger assumption on the distribution. More precisely, we assume that the input state is sampled from a state 2-design D2. These are ensembles such that sampling from them is equivalent to sampling a pure state uniformly (according to Haar measure) up to two statistical moments. 2-designs are extensively used in quantum information to generate pseudorandomness and to analyze average case complexities [Dankert et al., 2009; Scott, 2008; Ambainis et al., 2009].

In this regime, we derive two results, starting with an upper bound on the variance of the state-dependent shadow norm when the state is sampled from a state 2-design.

Theorem 5. Let D2 be a state 2-design and d = Θ(logn). Then, for any observable O, we have

Using this result, we can derive a result similar to Theorem 3, with better constants.

Theorem 6. Let d = Θ(logn) and ρ be an n-qubit pure state sampled from a state 2-design D2. For any δ, ϵ ∈ (0, 1), m > 1/√δ, and any C > 0, let

For any parameter vectors θ(1) , . . . , θ(C) , with probability at least 1 - δ, we have |⟨WO(θ(c) )⟩ρ - ⟨̂ WO(θ(c) )⟩ρ| ≤ ϵ for all 1 ≤ c ≤ C, where ⟨WO(θ(c) )⟩ρ and ⟨̂ WO(θ(c) )⟩ρ are defined in Eq.s (6) and (8), respectively.

Hence, we see that the lower bound on T1 in Eq. (10) is a constant time better than the lower bound on T1 in Eq. (7). By replacing the function evaluations in Theorem 6 with expectations with arbitrary observables, one can see that similar advantages can be gained for regular shallow shadow estimation also when the input is sampled from a 2-design.

8 Dealing with Barren Plateaus

Global observables may lead to barren plateaus (regions with gradients exponentially small in the number of qubits) occurring in the training landscape [Cerezo et al., 2021; Liu et al., 2022], which makes evaluating them using quantum devices extremely difficult. Although the gradients are evaluated classically in AISO, since we may encounter global observables and require O(1/ϵ2 ) shadows to additively approximate the gradients to precision ϵ, in some cases, we might end up requiring exponentially many shadows for meaningful approximations. However, several heuristic approaches have been proposed, which have been experimentally shown to reduce barren plateaus in many cases. We note that our method is compatible with almost all barren plateau mitigating methods that have been proposed in the literature. For example, [Patti et al., 2021; Mele et al., 2022; Rad et al., 2022; Skolik et al., 2021; Grimsley et al., 2023a; Grimsley et al., 2023b; Friedrich and Maziero, 2022; Verdon et al., 2019; Grant et al., 2019; Kulshrestha and Safro, 2022; Zhang et al., 2022] are methods that ultimately use the quantum device only to estimate ⟨WO(θ)⟩ρ at certain carefully chosen inputs θ. So, it is clear that if we use shadows to estimate them, then exponential advantages similar to the ones discussed in this paper can be achieved.

9 Conclusion and Future Direction

In this work, we proposed AISO - a training algorithm that leverages shallow shadows to achieve an exponential reduction in quantum resources required to train VQA cost functions. AISO is a very general approach that works with almost all of the popular shallow quantum circuit structures in the literature, when used in combination with observables of low Frobenius norm. It allows one to do more iterations of the classical optimizer, more hyperparameter tuning, and experiment with various ansatzes and optimizers with very few executions of the quantum device. We demonstrated this advantage in two important use cases of interest in quantum information: Variational Quantum State Preparation and Variational Quantum Circuit Synthesis.

For future work, we aim to design similar resourceefficient and ansatz-agnostic protocols for local observables, by leveraging classical machine learning with classical shadows similar to [Huang et al., 2021].

Acknowledgements

We thank Afham for pointing out important references and related works. We also thank Hakop Pashayan and Christian Bertoni for helping us clear up any questions we had about shallow shadows. This work is partially supported by the Australian Research Council (Grant No: DP220102059). AB was partially supported by the Sydney Quantum Academy PhD scholarship.