Randomness efficient algorithms for estimating average gate fidelity via k-wise classical and quantum independence

We present three new algorithms for efficient in-place estimation of average fidelity of a d dimensional quantum logic gate, without using ancilla qubits. The main advantage of our algorithms is the much smaller usage of truly random bits compared to what was known so far. Reducing the requirement of classical seed randomness increases the reliability of estimation, as high quality random bits are usually an expensive computational resource. Commonly used sources of random bits are strictly speaking either pseudorandom or have a non-trivial bias. Previous approaches for this task replaced Haar random unitaries in the naive estimation algorithm by approximate unitary 2-designs by sampling 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, highlighting the usage of computational derandomization theory for quantum computation. This algorithm uses random bits in contrast to random bits used in the previous works, with the same number of gate evaluations (c.f. [Dankert et al., Physical Rev. A 80, 012034 (2009)]). Our second efficient algorithm, uses a quantum 4-tensor product expander, in the regime of large gate dimension d and not ”too small” estimation error. It uses even lesser random bits than the first algorithm, and has the added advantage that it needs to implement only one unitary from an approximate 4-design as opposed to potentially all unitaries from an approximate 2-design in previous algorithms. This is significantly advantageous for NISQ machines and early fault tolerant quantum computers where one wants to minimize the number of times the quantum RAM needs to be loaded due to coherence time limitations. 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 from an approximate l-design versus potentially all the unitaries of an approximate 2-design in previous algorithms. This advantage can be of great importance to the experimental implementations in the near future.