Efficiently estimating average fidelity of a quantum logic gate using few classical random bits

We give three new algorithms for efficient in-place estimation, without using ancilla qubits, of average fidelity of a quantum logic gate acting on a d-dimensional system using much fewer random bits than what was known so far. Previous approaches for efficient estimation of average gate fidelity replaced Haar random unitaries in the naive estimation algorithm by approximate unitary 2-designs, and sampled them uniformly and independently. In contrast, in our first algorithm we sample the unitaries of the approximate unitary 2-design uniformly using a limited independence pseudorandom generator, a powerful tool from derandomisation theory. This algorithm uses the same number of basic operations as previous efficient algorithms but much fewer number of random bits. Reducing the requirement of classical random bits increases the reliability of estimation as often, high quality random bits are an expensive computational resource. Our second efficient algorithm, based on a 4-quantum tensor product expander, works if the gate dimension d is large. It uses even lesser random bits than the first algorithm, and has the added advantage that it needs to implement only one unitary versus potentially all the unitaries of an approximate 2-design in the first algorithm. Our third efficient algorithm, based on an l-quantum tensor product expander for moderately large values of l, works for all values of the parameters. It uses slightly more random bits than the other algorithms but has the advantage that it needs to implement only a small number of unitaries versus potentially all the unitaries of an approximate 2-design in the first algorithm. This advantage is of great importance to experimental implementations in the near future.


I. INTRODUCTION
Unitary quantum logic gates serve as the basic building blocks of quantum circuits implementing quantum algorithms. They are nothing but unitary operators chosen from a predetermined set. Implementation of any quantum algorithm is achieved by application of an appropriate sequence of these gates. However, in practice there is always some error between the ideal gate output given a particular input state and the actual gate output because of noise. Thus if we want to apply a quantum gate, it is desirable that the noisy experimental version Λ be close to the ideal gate U with respect to some measure. Most works use the so-called fidelity as a measure of closeness. This leads to the notion of gate fidelity for a particular input state. Notice that this characterisation depends on the quantum state inputted to the gate. However when the gate is used as part of a quantum circuit, it may not be feasible to figure out the states that may possibly be inputted to the gate during the course of operation of the circuit. One would like to remove this state dependence in the definition of gate fidelity and instead come up with a quantity that serves as a general measure of the quality of the gate implementation. One way to do this is to consider the gate fidelity averaged over the Haar probability measure on all possible pure input states. This quantity is called the average gate fidelity [1].
Emerson et al. [1] gave an algorithm for estimating average fidelity of a unitary d-dimensional gate using several independent samples of d × d Haar random unitaries. While they did not explicitly bound the number of samples required in order to obtain an estimate of the average fidelity to within additive error ǫ, their method can be analysed to show that O(ǫ −2 ) independent Haar random samples of unitaries suffice. This is prohibitively expensive, both in terms of the computational cost required to implement the Haar random unitaries as well as in terms of the number of random bits required to do the sampling. Both these quantities are at least Ω(ǫ −2 d 2 log d log(1/ǫ)) [17,Corollary 4.2.13]. Later works [2,3] showed that the computational cost and the number of random bits can be drastically brought down by choosing independent uniform samples from a unitary 2-design. Again, these papers did not rigorously estimate the running time and the usage of random bits of their algorithm, but nevertheless those can be analysed to obtain a bound of O(ǫ −2 polylog(d/ǫ)) for both.
In this paper, we treat the usage of classical random bits as a resource and try to minimise it. One of the reasons behind this is that high quality random bits are an expensive computational resource. Thus, reducing them while preserving the efficiency of the algorithm and the estimation error would generally lead to more reliable estimation in practice. This is especially important because in the near future, we expect to have experimental realisations of quantum circuits on about ten to fifty qubits, and they have to be benchmarked accurately and reliably so as to further the goal for having a practical quantum computer one day. Another reason behind reducing the number of random bits is that it often gives us deep insights into the algorithms involved, leading to serendipitous additional optimisations that may have otherwise escaped our attention. In this paper, we shall actually see an example of such a serendipitous optimisation. Our second and third algorithms not only use far less random bits that what was known earlier; they also require the algorithms to implement a much smaller set of unitaries than potentially all unitaries of an approximate 2-design in earlier works [2,3]. This is very important for the near future because implementing a wide range of unitaries is technologically fraught with immense challenges. An excellent introduction to derandomisation goals and techniques in computer science can be found in the book [16].
We give three new algorithms for efficient in-place estimation, without using ancilla qubits, of the average fidelity of a quantum logic gate acting on a d dimensional system using much fewer random bits than what was known so far. We consider in-place algorithms only because good quality qubits are likely to remain a very expensive resource in near term experimental implementations, and so we want to avoid ancilla qubits as much as possible. In our first algorithm, in contrast to earlier works, we sample the unitaries of the approximate unitary 2-design uniformly using a limited independence pseudorandom generator [11,12], a powerful tool from derandomisation theory. This algorithm uses O(ǫ −2 (log δ −1 )(log d)(log ǫ −1 )) number of basic operations in order to estimate the average gate fidelity to within an additive error ǫ with confidence 1 − δ, which is the same as [2]. However, it only uses O((log δ −1 )((log d)(log ǫ −1 ) + log log δ −1 )) random bits, which is much lesser number than the Ω(ǫ −2 (log d)(log ǫ −1 )) random bits used in the previous works.
Our second efficient algorithm, based on a 4-quantum tensor product expander [15], works if the gate dimension d is large. It uses even lesser random bits than the first algorithm, and has the added advantage that it needs to implement only one unitary versus potentially all the unitaries of an approximate 2-design in the first algorithm. Our third efficient algorithm, based on an l-quantum tensor product expander [15] for moderately large values of l, works for all values of the parameters. It uses slightly more random bits than the other algorithms but has the advantage that it needs to implement only a small number of unitaries versus potentially all the unitaries of an approximate 2-design in the first algorithm.
The rest of the paper is organised as follows: • In Section II we build up some notations and preliminaries that will be used throughout the paper.
• Section III describes how to bound the tail of the gate fidelity distribution when the unitaries are chosen from an approximate l-quantum tensor product expander (qTPE).
• Section IV summarises the earlier work on estimating average gate fidelity adding a rigorous analysis of estimation and confidence errors missing in previous works.
• In Section V, we describe a randomness efficient algorithm for estimating average gate fidelity using approximate 2-designs combined with a limited independence pseudorandom generator.
• In Section VI, we describe a randomness efficient algorithm for estimating average gate fidelity using an approximate 4-qTPE, which works if the gate dimension is large and needs to implement only one unitary.
• In Section VII, we describe a randomness efficient algorithm for estimating average gate fidelity using approximate l-designs for moderate values of l ≥ 4, which has the advantage that the estimation procedure needs to potentially implement only a very small number of unitaries.
• We conclude in Section VIII with a discussion of what we have achieved, and directions for future work.

II. NOTATION AND PRELIMINARIES
Throughout the paper, H denotes a complex Hilbert space of finite dimension d and H ⊗m denotes the m fold tensor product of H. We use 1 1 to denote the identity operator on H. M k,d denotes the vector space of k × d linear operators over complex field and M d = M d,d . Note that M d is itself a Hilbert dpace of dimension d 2 with Hilbert-Schmidt inner product, defined as: A, B T r(A † B). For p > 0, we let · p denote the Schatten p-norm of operators in M d , defined as: A p [Tr (A † A) p/2 ] 1/p . This is nothing but the ℓ p -norm of the vector of singular values of A. The case p = 1 is called the trace norm. The case p = 2 is the Frobenius norm or the Hilbert-Schmidt norm induced from the eponymous inner product. Letting p → ∞ gives us the Schatten ℓ ∞ -norm which is nothing but the largest singular value of A, aka operator norm or spectral norm of A. Often, we use ρ to denote a quantum state or a density matrix which is a Hermitian, positive semidefinite matrix with unit trace. We let D(d) denote the set of all d × d density matrices. A pure quantum quantum is a rank one density matrix. We denote by CP d−1 the set of pure quantum states in H. The notation |· denotes a vector of unit ℓ 2 -length. Thus if |ψ is a unit vector, |ψ ψ| is a pure quantum state. We will often abuse notation and use |ψ to denote a pure quantum state also.
We use Λ to denote the noisy experimental realisation of an ideal unitary quantum gate U. For a bipartite Hilbert space H 1 ⊗ H 2 , the partial trace Tr H2 denotes the operation of tracing out H 2 . We use X to denote a random variable andX to denote its expected value with respect to a probability measure µ, i.e., X X dµ. The notation Var(X) denotes the variance of random variable X, i.e. V ar(X) = (X −X) 2 . The symbol U(d) stands for the the unitary group on H i.e. the group of d × d complex unitary matrices. We tacitly assume that the ceiling is taken of any formula that provides dimension or value of t in unitary t-design. The symbol Haar is used to denote the unique unitarily invariant Haar probability measure on U(d), or CP d−1 as appropriate. Expectation with respect to a measure µ is denoted by E ν [·].
Fidelity between two quantum states ρ and σ is defined as: Fidelity is a measure of distinguishabilty of two states. It is easy to see that F (ρ, σ) = 1 implies ρ and σ are identical, and F (ρ, σ) = 0 implies that ρ and σ have orthogonal support and there exists a single measurement that distinguishes them perfectly. Fidelity is related to trace distance via the following inequality.
A linear mapping Λ : M m → M d is called a super operator, and a super operator which is completely positive and trace preserving is considered as a quantum operation. The vector space of superoperators is denoted by Then U is also a quantum operation defined as U(ρ) = U ρU † . Suppose Λ is a 'noisy' implementation of the unitary quantum operation U. Then Λ is a quantum operation from M d to M d , and so it can be represented using Kraus operators as Kraus operators of Λ, with the property that Σ k A † k A k = 1 1. It turns out that d 2 Kraus operators suffice to describe any quantum operation from M d to M d . We shall measure the distance between two superoperators via the so-called diamond norm [14]. The diamond norm of a superoperator Λ : M d → M d is defined as follows: where I m is the identity superoperator on M m . A quantum operation Λ always has Λ ♦ = 1.
Gate fidelity between Λ and U for an input state ρ is defined as: The average gate fidelityF Λ,U is now defined to be the expectation of the gate fidelity F Λ,U (|ψ ψ|) for pure input states |ψ ψ| chosen from the Haar probability measure on CP d−1 : In practice, when one wants to benchmark the quality of the experimental implementation of a unitary quantum logic gate U, one runs the implementation twice, first in the forward direction followed by the backward direction. If the implemenation were indeed perfect, this would just do the quantum operation U −1 U = 1 1. But because the implementation is noisy what we get is a quantum operation, which we will again denote by Λ, that is close to the identity quantum operation. Let |ψ be a unit length vector in H. Define Then the average gate fidelity of Λ is given bȳ The average gate fidelity defined above has a nice expression in terms of the Kraus operators of Λ [1]: The variance of the gate fidelity under the Haar measure on d × d unitaries V happens to satisfy the following inequality [8,Equation 18].
The gate fidelity is an example of a function from the unit ℓ 2 -norm sphere S 2d−1 in C d to R. More generally, consider a function f : The following fact was proved in [13, Lemma 2.7].
Consider the probability distribution on points (v 1 , . . . , v t ) ∈ (S 2d−1 ) ×t where the v i s are chosen independently from the Haar measure on S 2d−1 . Define Let δ > 0. Then, . Now let f be the following function Trivially, It is easy to see that which shows that the Lipschitz constant η ≤ 4t −1/2 . Let δ > 0. Consider the probability distribution on points (V 1 , . . . , V t ) ∈ U(d) ×t obtained by choosing each V i independently from the Haar measure. Define f (V 1 , . . . , V t ) in the natural fashion. By Fact 1, Now, we define an approximate unitary 2-design via the so-called twirling operation as in [2]. Let ν be a probability measure on U(d). Let Λ be a superoperator on M d . Define the ν-twirling operation E ν : L(M d ) → L(M d ) as follows: where Λ ∈ L(M d ) and X ∈ M d . When ν is the Haar probability measure on U(d), we shall write the above superoperator as E Haar (Λ).
We now recall the definition of a quantum tensor power expander [15].
Definition II.2. A quantum t-tensor product expander (t-qTPE) in H, |H| = d, of degree s can be defined as a quantum operation G : L(H ⊗t ) → L(H ⊗t ) that can be expressed as The qTPE is said to have second singular value λ if G − I ∞ ≤ λ, where I is the 'ideal' quantum operation defined by its action on a matrix M by We use the notation (d, s, λ, t)-qTPE to denote such a quantum tensor product expander.
From the above definition, it is easy to see that a (d, s, λ, t)-qTPE is also simultaneously a (d, s, λ, t ′ )-qTPE for any t ′ < t.
Let X 1 , X 2 , . . . , X n be a sequence of {0, 1}-valued random variables. Let 2 ≤ k ≤ n. Let S ⊆ {1, 2, . . . , n}, S = {s 1 , s 2 , . . . , s k }. Let X s1 X s2 · · · X s k denote the actual joint distribution of the corresponding random variables. Let 0 < p < 1. Let B(k, p) denote the Bernoulli distribution i.e. the distribution of k fully independent identical coin tosses with probability of a coin turning up HEAD equal to p. The sequence X 1 , X 2 , . . . , X n is said to be θ-approximate p-biased k-wise independent if for any subset S = {s 1 , . . . , s k }, i.e. the joint probability distribution of any subset of the random variables of size k is θ-close to the Bernoulli distribution in ℓ 1 -distance.
We first state a Chernoff bound for a fully independent (i.e. 0-approximate n-wise independent) sequence of random variables. This bound can be derived from [7, Corollary A.1.14]. .
We now state a Chernoff-like bound for θ-approximte k-wise independent random variables. This bound can be derived from [12,Theorem 5].
Fact 4. Let k, n be positive integers, θ > 0 and r k + 2 log log k + 2 log log n + 2 log θ −1 . Then there is a function f : {0, 1} r → {0, 1} n such that, if the uniform distribution on {0, 1} r is provided at the input, the resulting sequence X 1 , X 2 , . . . , X n at the output is a θ-approximate 1/2-biased k-wise independent sequence of random bits. Moreover there is a deterministic algorithm that, given an input string z ∈ {0, 1} r and a bit position i ∈ {1, 2, . . . , n}, computes the output bit f (z) i in time poly(r).
Facts 3 and 4 allow us to prove the following easily.
where the expectation is taken over the random variable Y uniformly distributed on Y. Let n be a positive integer, ǫ, θ > 0 and r 4ǫ 2 n log |Y|) + 2 log θ −1 . Then there is a function f : {0, 1} r → Y n such that, if the uniform distribution on {0, 1} r is provided at the input, the resulting sequence X 1 , X 2 , . . . , X n of random bits at the output, where X i = 1 with probability g(Y i ) and 0 otherwise, satisfies X being defined as n −1 n i=1 X i . Moreover there is a deterministic algorithm that, given an input string z ∈ {0, 1} r and a position i ∈ {1, 2, . . . , n}, computes the output element f (z) i ∈ Y in time poly(r) log |Y|.

III. BOUNDING THE TAIL OF THE GATE FIDELITY DISTRIBUTION
In this section, we show how to bound the tail of the gate fidelity distribution, both under the Haar measure as well as under the uniform measure on a qTPE. As a warmup, we first show that approximate unitary 2-designs and 2-qTPEs are related.
Above, we used the so-called swap trick Tr [M N ] = Tr [(M ⊗ N )S] in the second equality, ⊗ ′ , ⊗ ′′ in the fourth equality indicate that the splitting of the tensor multiplicands is different from the splitting in X ⊗ V , the fact that G(X) 1 ≤ |H| X 1 G ∞ for an operator X ∈ L(H) and superoperator G : L(H) → L(H) in the third inequality, and V 1 = d 2 in the fifth equality. Since This completes the proof.
We now prove four lemmas that will help us relate the tail of the distribution of gate fidelity calculated with respect to a unitary chosen from the Haar measure versus chosen from a t-qTPE.
Lemma III.1. Let {A k } k be Kraus operators of quantum operation Λ, i.e., Λ(ρ) = k A k ρA † k . We will use F (V ) as a shorthand for F Λ (V ). Let l be a positive integer. Let a ∈ C.
Proof. We have This proves the first equality. For the second equality, This completes the proof.
Lemma III.2. Under the notation of Lemma III.1, where the inequality is obtained by applying Cauchy-Schwarz to the Hilbert-Schmidt inner product. Then This completes the proof of the lemma.
Lemma III.3. Let d, l, s be positive integers and λ > 0. Let a ∈ C. The notation E V :qTPE [·] denotes the expectation with respect to a d × d unitary V chosen uniformly at random from a (d, s, λ, 2l)-qTPE. The notation E V :Haar [·] denotes the expectation with respect to a d × d unitary V chosen from the Haar measure. Then, Proof. Using Lemmas III.1 and III.2, we get This completes the proof of the lemma.
Lemma III.4. Let t be a positive integer. Let d, l, s be positive integers and λ > 0. Let 0 ≤ a ≤ 1.
The notation E V1,...,Vt:qTPE [·] denotes the expectation with respect to independently choosing d × d unitaries V 1 , . . . , V t uniformly at random from a (d, s, λ, 2l)-qTPE. The notation E V1,...,Vt:Haar [·] denotes the expectation with respect to independently choosing d × d unitaries V 1 , . . . , V t from the Haar measure. Define the function f : where in the fourth inequality we used the fact that if (i 1 , . . . , i p ) is a partition of l where each i m = 0, 1 ≤ m ≤ p, then for any x > 1, This completes the proof of the lemma.
We now prove the following important result giving a tail bound on the uniform average of t gate fidelity functions, when the t unitaries are chosen independently and uniformly from a qTPE.
Proposition III.5. Let t, d, s, l be positive integers and δ, λ > 0. Consider the probability distribution on points (V 1 , . . . , V t ) ∈ U(d) ×t obtained by choosing each V i independently and uniformly from a (d, s, λ, 4l)-qTPE. Define the function f : i.e., f is the average of t gate fidelities. Then, For the special case where l = 1, we get Proof For larger values of l, we employ the l-moment method of [4] as adapted into the quantum setting by Low [5], combined with the tail bound of Equation 3 for the Haar measure. We obtain

This gives us
Pr (V1,...,Vt):qTPE This completes the proof of the proposition.

IV. EARLIER WORK ON ESTIMATING AVERAGE GATE FIDELITY
We first recall the naive algorithm [1] for estimating average gate fidelity using Haar random unitaries for reference and comparison. The basic procedure is the following. It is easy to see that the probability of success in one iteration of the basic procedure is, by taking |ψ U |0 , The basic procedure of the naive algorithm is prohibitively expensive, both in terms of the computational cost required to implement the Haar random unitaries as well as in terms of the number of random bits required to do the sampling. Uniformly sampling a d × d Haar random unitary to within ℓ 2 -distance ǫ requires at least Ω(d 2 log(1/ǫ)) random bits and circuit size at least Ω( d 2 log d log(1/ǫ)) [17, Lemma 3.5]. Thus the overall number of random bits used by the basic procedure becomes Ω(d 2 log(1/ǫ)), and the overall circuit size of the basic procedure Ω( d 2 log d log(1/ǫ)). Since twirling with a Haar random unitary is the same as twirling with a uniformly random unitary chosen from an exact unitary 2-design, we can replace the Haar random unitary in the basic procedure by a uniformly random unitary chosen from an exact 2-design without changing the probability of success at all [2]. The advantage of doing so is that there exist 2-designs each of whose unitaries can be implemented by a circuit of size O((log d) 2 ), whereas a Haar random unitary almost always requires circuits of size at least Ω(d 2 log(1/ǫ)) to implement within precision ǫ.
One iteration of the basic procedure succeeds with probabilityF Λ . A single outcome, success or failure, gives us no clue about the value ofF Λ . So in order to actually estimateF Λ to within an additive error ǫ, with confidence 1 − δ, we have to repeat the basic procedure several times. Neither [1] nor [2] do this rigorously. We now address this important shortcoming. Let us repeat the basic procedure independently Θ(ǫ −2 log(1/δ)) times and take the empirical average of successes. By Fact 2, an estimate ofF to within an additive error of ǫ with probability at least 1 − δ. The running time of this algorithm turns out to be O(ǫ −2 log δ −1 (log d) 2 ), and the number of random bits consumed turns out to be O(ǫ −2 log δ −1 log ǫ −1 (log d) 8 ) [9]. We note that there are constructions of exact unitary 2-designs [10] using Clifford gate circuits of size O((log d)(log log d) 2 (log log log d)), but they use at least Ω(log d) ancilla qubits. Since qubits are likely to be a very expensive resource in foreseeable implementations of quantum gates, we prefer that all our algorithms be in-place without using ancilla qubits.
Dankert et al. [2] showed how to improve the running time and the number of random bits in the basic procedure by replacing the use of an exact 2-design by a θ-approximate 2-design. Due to the replacement, the probability of success in the basic procedure becomes where we used the fact that Λ ♦ = 1 as Λ is a quantum operation. We can now take θ = ǫ/2 and repeat the basic procedure Θ(ǫ −2 log(1/δ)) times and take the empirical average of successes, in order to get an estimate ofF Λ to within an additive error of ǫ with confidence 1 − δ. The running time and usage of random bits of this algorithm turn out to be O(ǫ −2 log δ −1 (log d) log ǫ −1 ). [2]. We note that Dankert et al. [2,Theorem 3] incorrectly repeat the basic procedure O(log δ −1 ) times to get confidence 1 − δ, ignoring the issue of additive error ǫ completely.
By Fact 6, replacing the Haar random unitary U in the basic procedure by a (d, s, ǫ 2d 4 , 2)-qTPE G also leads to an efficient algorithm for estimating average gate fidelity. In fact, a direct analysis shows that a (d, s, ǫ 2d , 2)-qTPE suffices too. Such 2-qTPEs can be obtained via the so-called zigzag product [6]. The unitaries of the qTPE can be implemented by circuits of size O((log d) 2 (log d/ǫ). The number of random bits required is only O(log(d/ǫ)). The running time of this algorithm turns out to be O(ǫ −2 log δ −1 (log d) 2 (log d/ǫ)), and the number of random bits consumed turns out to be O(ǫ −2 log δ −1 log(d/ǫ)). The circuit size is slightly inferior to Dankert et al. [2] but the number of random bits used is less.

V. RANDOMNESS EFFICIENT ALGORITHM USING APPROXIMATE UNITARY 2-DESIGNS
Instead of repeating Algorithm 1 with independently chosen unitaries per iteration, we pick the sequence of unitaries of the approximate 2-design from an approximate k-wise independent distribution for a suitable value of k. For clarity, we give the full algorithm below. Algorithm 3 consists of a classical preprocessing step where the sequence Y 1 , Y 2 , . . . , Y n is computed. This takes classical deterministic time O(ǫ −2 poly(r)). After the preprocessing step, Algorithm 3 runs in quantum time O(ǫ −2 log δ −1 (log d) 2 (log(d/ǫ))). The number of random bits used is r = O(log δ −1 (log(d/ǫ) + log log δ −1 )). By Fact 5, Algorithm 3 gives an estimate b ofF Λ such that Pr[|b −F Λ | > ǫ] ≤ δ. Comparing with the zigzag product based algorithm in Section IV, we get the same quantum circuit size but much lesser usage of random bits.
Instead of the zigzag product, we can take the ǫ/2-approximate unitary 2-design of Dankert et al. [2]. An advantage of doing this is that we use only Clifford gates in the approximate unitary 2-design which may be technologically easier to implement. That would give us classical preprocessing time of O(ǫ −2 poly(r)), quantum time of O(ǫ −2 log δ −1 (log d)(log ǫ −1 )) and number of random bits r = O(log δ −1 ((log d)(log ǫ −1 ) + log log δ −1 )). Comparing with the corresponding algorithm in Section IV, we get the same quantum circuit size but much lesser usage of random bits. Thus this algorithm is a good candidate for actual experimental implementations in the near future.
unitary Y will give an estimate b of F Λ (Y ) such that where the probability arises because of inherent quantum uncertainty of measurement outcomes. Overall we get, Pr[|b −F Λ | > ǫ] ≤ δ. Algorithm 4 takes quantum running time O(ǫ −2 log δ −1 (log d) 3 ) which is the same as the zigzag product based approximate 2-design Algorithm 3 of Section V. However it consumes only O(log d) random bits, where the constant hiding in the O(·) is independent of ǫ and δ, which is less than what Algorithm 3 consumes. The drawback of Algorithm 4 is that it requires that 108 ǫ 2 d < δ 2 , whereas Algorithm 3 has no such assumption. In practice, this means that Algorithm 4 can only be used if the dimension d is large and the estimation error ǫ and confidence error δ are not too small.

VII. RANDOMNESS EFFICIENT ALGORITHM USING APPROXIMATE 4l-QTPE
We now address the main drawback of Algorithm 4 i.e. what if the dimension d is not large enough? This is a pertinent question because in the near future we hope to experimentally implement and benchmark quantum circuits acting on ten to fifty qubits. For ten to twenty qubits, the dimension d may not be large enough to satisfy the assumption 108 ǫ 2 d < δ 2 for reasonably small values of ǫ and δ. It would be nice to have an efficient algorithm using a few random bits for arbitrary values of d, ǫ and δ. Algorithm 3 is one such algorithm, but it requires us to be able to implement the entire plethora of 2 Ω(log(d/ǫ)) unitaries in an approximate 2-design. In some technological scenarios, it may be better to spend a few more random bits but reduce the number of unitaries that may need to be implemented by the algorithm. Algorithm 4 is indeed a step in this direction but it suffers from the drawback mentioned above.
To achieve this goal, we develop Algorithm 5 by combining ideas from Algorithms 3 and 4. Algorithm 5 is a two-phase algorithm using an l-qTPE for l ≥ 4, but still small enough to be efficiently implementable.
Choose: independently and uniformly at random unitaries V 1 , . . . , V t from Y. Call this set of unitaries as Y.
Construct: a sequence Y 1 , Y 2 , . . . , Y n of unitaries from Y as the output of f : {0, 1} r → Y n guaranteed by Fact 5, when a uniformly random input z ∈ {0, 1} r is fed to f , where r ǫ 2 n log t + 2 log θ −1 .
In Phase 1, we take a (d, s, λ, 4l)-qTPE V and sample from it independently and uniformly at random a small number of unitaries V 1 , . . . , V t . For l = log(16/δ), t = 2 11 l ǫ 2 d = 2 11 log(16/δ) . λ ( ǫ 2 2 5 d 2 ) l = ( ǫ 2 2 5 d 2 ) log 16/δ , Proposition III.5 will ensure that the gate fidelity averaged over this small set of unitaries is ǫ/2-close to the actual average gate fidelityF Λ with confidence at least 1 − δ 2 . The number of random bits required to independently sample t times uniformly from V is Each unitary in V can be implemented in quantum time O((log d) 2 (log δ −1 ) 3 (log log δ −1 ) log(d/ǫ)). The constants hiding in both the O(·) notations above are independent of d, ǫ, δ. These facts follow from the so-called zigzag product [6]. Morally speaking, this preprocessing step achieves the goal of the first phase of Algorithm 4. In Phase 2 of our algorithm, we sample only from the set Y {V 1 , . . . , V t } in an approximate limited independence fashion as in Fact 5, and run Algorithm 2 on those samples in so as to empiricially estimate the gate fidelity averaged over the set Y. We apply Fact 5 with n 2 4 log(4/δ) 2 4 log(4/δ) ) log(4/δ) , r ǫ 2 n log t + 2 log θ −1 = 16 log δ −1 (log log δ −1 + 2 log ǫ −1 − log d + O(1)) + 2 log(4/δ) Morally speaking, this achieves the goal of the second phase of Algorithm 3.
We now analyse the running time and number of random bits used by Algorithm 5. The total confidence of Phases 1 and 2 is at least 1 − δ. Suppose 2 11 log(16/δ) Then, we set t = 1 and so Phase 2 does not use any more random bits. The total number of random bits used in Phases 1 and 2 now becomes O(log δ −1 log(d/ǫ)), where the constant hiding in the O(·) notation does not depend on ǫ, δ, d. This is comparable to the total number of random bits used by Algorithm 3. However, Algorithm 5 requires us to implement only one unitary as opposed to implementing potentially all the unitaries in an approximate 2-design in Algorithm 3. Also the constraint on the dimension d is less stringent than the constraint required by Algorithm 4. Suppose 2 11 log(16/δ) The total number of random bits used in Phases 1 and 2 becomes where the constant hiding in the O(·) notation does not depend on ǫ, δ, d. Now the number of random bits used is greater than that of Algorithm 3. However, Algorithm 5 requires us to implement only log(16/δ) ǫ 2 d unitaries as opposed to implementing potentially 2 Ω(log(d/ǫ)) unitaries in Algorithm 3. This is a big saving on the number of unitaries an algorithm has to potentially implement. In both cases, the total running time of Algorithm 5 is O(ǫ −2 (log δ −1 ) 4 (log d) 2 (log log δ −1 ) log(d/ǫ)), which is slightly worse than that of Algorithm 3. The worse running time is due to the fact that Algorithm 5 needs a O(log δ −1 )-qTPE whereas Algorithm 3 only needs a 2-qTPE. Any future improvement in construction of t-qTPEs for large t will improve the running time of Algorithm 5.

VIII. CONCLUSION
We have described three new algorithms for efficient in-place estimation, without using ancilla qubits, of average fidelity of a quantum logic gate using much fewer random bits than what was known so far. We considered only in-place algorithms in this work because qubits are likely to remain an expensive resource in experimental implementations in the near future, and so we would like to avoid ancilla qubits as far as possible. We achieve the reductions in the number of random bits by appealing to two powerful tools. The first tool, a limited independence pseudorandom generator, comes from classical derandomisation theory in computer science. It is used in the first and the third estimation algorithms. The second tool, an approximate l-quantum tensor product expander (l-qTPE) for moderate values of l, is a recent quantum computational object defined as an analogue of an approximate l-wise independent pseudorandom generator well known from classical derandomisation theory. In fact, to obtain our parameters we actually have to appeal to the state of the art in quantum tensor product expanders, which in turn were obtained by 'quantising' another famous result from classical derandomisation theory viz. the zigzag product of graphs. The second tool is used in our second, and more strongly, in our third estimation algorithm.
Each of our algorithms have unique features that, depending upon the experimental limitations and desired parameters, sometimes make one of them the most suitable, sometimes another. If one wants an efficient algorithm that works for all values of the gate dimension d, estimation error ǫ and confidence error δ, and uses the least number of random bits, then the first algorithm is the way to go. Reducing the number of random bits will increase the reliability of the estimation in practice as explained earlier. Moreover, this algorithm can be chosen to be implemented using only Clifford gates which may be an advantage for some technologies.
If the gate dimension is large, then the second algorithm is the best one. It uses the least number of random bits and needs to implement only one unitary from an approximate 4-qTPE. If the aim is to use an algorithm that works for all parameter values but needs to implement as few unitaries as possible, then the third algorithm is the right one. Though it uses more random bits than the first algorithm, it needs to implement much fewer unitaries than the first. This feature can be the most crucial for certain technologies.
Moving on from estimating average gate fidelity, it will be interesting to find other applications of both classical derandomisation as well as quantum derandomisation tools in quantum computation, both theoretical and experimental. The experimental implementations of quantum computers of the near future, of the order of tens of qubits, will be very noisy. Reliable and efficient test suites optimised for every bit of precision and performance are the need of the hour to measure progress in the exciting times to come.