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.
This thesis discusses the young fields of quantum pseudo-randomness and quantum learning algorithms. We present techniques for derandomising algorithms to decrease randomness resource requirements and improve efficiency. One key object in doing this is a k-design, which is a distribution on the unitary group whose kth moments match those of the unitarily invariant Haar measure. We show that for a natural model of a random quantum circuit, the distribution of random circuits quickly converges to a 2-design. We then present an efficient unitary k-design construction for any k, provided the number of qubits n satisfies k = O(n/log n). In doing this, we provide an efficient construction of a quantum tensor product expander, which is a generalisation of a quantum expander which in turn generalises classical expanders. We then discuss applications of k-designs. We show that they can be used to improve the efficiency of many existing algorithms and protocols and also find new applications to derandomising large deviation bounds. In particular, we show that many large deviation bound results for Haar random unitaries carry over to k-designs for k = poly(n). In the second part of the thesis, we present some learning and testing algorithms for the Clifford group. We find an optimal algorithm for identifying an unknown Clifford operation. We also give an algorithm to test if an unknown operation is close to a Clifford or far from every Clifford.
This paper proposes a general method to estimate the practical average fidelity error using an -approximate unitary 2 t -design. We then build a specific model of local random circuits to construct the -approximate unitary t -design under a tighter bound on the diamond norm of the corresponding error. For a twirled t -tensor product noisy channel constructed by local random circuits, we extend the estimation of average fidelity using approximate unitary 2 t -designs to an ( m + 1 ) -fold noise scenario. Compared to previous randomized benchmarking, the average fidelity estimated by the method of local random circuits requires less experiments but longer circuit lengths for large n quantum system.
We develop the concept of a unitary
t-design as a means of expressing operationally useful subsets of the stochastic properties of the uniform (Haar) measure on the unitary group
U(2n) on
n qubits. In particular, sets of unitaries forming 2-designs have wide applicability to quantum information protocols. We devise an
O(n)-size in-place circuit construction for an approximate unitary 2-design. We then show that this can be used to construct an efficient protocol for experimentally characterizing the fidelity of a quantum process on
n qubits with quantum circuits of size
O(n) without requiring any ancilla qubits, thereby improving upon previous approaches.
Randomized benchmarking is a useful scheme for evaluation the average fidelity of a noisy quantum circuit. However, it is insensitive to the unitary error. Here, we propose a method of randomized benchmarking in which a unitary t-design is applied and by which the unitary error estimation can be converted to analysis of pseudo-randomness on a set of unitary operators. We give a bound on the number of randomized benchmarking sequences, when performing a unitary t-design on n-qubit d-dimensional system. By applying local random unitary operators, a decomposition of a unitary t-design, the bound is more practical than the previous bound for multi-qubit circuit. We also give a rigorous bound of a diamond norm between arbitrary and uniform distributions of a set of unitary operators to form an ε-approximate unitary t-design. It can be used to quantitatively analyze the corresponding average fidelity and errors in a large-scale quantum circuit.
Abstract Randomized benchmarking is an important protocol for robustly characterizing the error rates of quantum gates. The technique is typically applied to the Clifford gates since they form a group that satisfies a convenient technical condition of forming a unitary 2-design, in addition to having a tight connection to fault-tolerant quantum computing and an efficient classical simulation. In order to achieve universal quantum computing one must add at least one additional gate such as the T gate (also known as the π /8 gate). Here we propose and analyze a simple variation of the standard interleaved RB protocol that can accurately estimate the average fidelity of the T gate while retaining the many advantages of a unitary 2-design and the fidelity guarantees that such a design delivers, as well as the efficient classical simulation property of the Clifford group. Our work complements prior methods that have succeeded in estimating T gate fidelities, but only by relaxing the 2-design constraint and using a more complicated data analysis.
Random quantum circuits aim to efficiently reproduce the statistical properties of ideal random quantum evolution. One approach is to construct approximate unitary designs, which match the moments of Haar-random unitaries up to a prescribed order with controlled error. We establish quantitative guarantees for how accurately these designs reproduce the distribution of each output probability. We show that, for every strong
ε-approximate unitary
k-design on
n qubits, the distribution of each output probability is within
O(k−1/2(1+k/2n)−1/2+ε) in Kolmogorov distance of the Porter-Thomas distribution, a beta distribution with parameters
1 and
2n−1. This bound is optimal up to constant factors, implying that a substantially better uniform bound requires additional structure. We then show that a mild form of local invariance suffices. We prove that any such design that is invariant under unitary translations acting on a single qubit approximates Porter-Thomas to total variation distance
O(k−1/2+ε). Every strong
ε-approximate unitary
k-design invariant on
logk+O(1) qubits achieves error
2−Ω(k)+O(ε) in Kolmogorov distance and
2−Ω(k)+O(εlog(2/ε)) in total variation distance. These results identify the distributional accuracy guaranteed by moment matching and the structure that improves it. As an application, we show that the Shannon entropy of the output distribution of a strong
ε-approximate
k-design is concentrated around its Haar value
n−Θ(1): its mean differs from the Haar mean by
O(k−1/4+ε1/2) and its standard deviation is
O(2−n/2+k−1/8+ε1/4). Consequently, a trusted device sampling such circuits generates
n−O(1) bits of entropy per sample, which makes them useful for random number generation.