Quantum signal processing (QSP) studies quantum circuits interleaving known unitaries (the phases) and unknown unitaries encoding a hidden scalar (the signal). For a wide class of functions one can quickly compute the phases applying a desired function to the signal; surprisingly, this ability can be shown to unify many quantum algorithms. A separate, basic subfield in quantum computing is gate approximation: among its results, the Solovay-Kitaev theorem (SKT) establishes an equivalence between the universality of a gate set and its ability to efficiently approximate other gates. In this work we prove an 'SKT for QSP,' showing that the density of parameterized circuit ansätze in classes of functions implies the existence of short circuits approximating desired functions. This is quite distinct from a pointwise application of the usual SKT, and yields a suite of independently interesting 'lifted' variants of standard SKT proof techniques. Our method furnishes alternative, flexible proofs for results in QSP, extends simply to ansätze for which standard QSP proof methods fail, and establishes a formal intersection between QSP and gate approximation.
Quantum signal processing (QSP) studies quantum circuits interleaving known unitaries (the phases) and unknown unitaries encoding a hidden scalar (the signal). For a wide class of functions one can quickly compute the phases applying a desired function to the signal; surprisingly, this ability can be shown to unify many quantum algorithms. A separate, basic subfield in quantum computing is gate approximation: among its results, the Solovay-Kitaev theorem (SKT) establishes an equivalence between the universality of a gate set and its ability to efficiently approximate other gates. In this work we prove an 'SKT for QSP,' showing that the density of parameterized circuit ansätze in classes of functions implies the existence of short circuits approximating desired functions. This is quite distinct from a pointwise application of the usual SKT, and yields a suite of independently interesting 'lifted' variants of standard SKT proof techniques. Our method furnishes alternative, flexible proofs for results in QSP, extends simply to ansätze for which standard QSP proof methods fail, and establishes a formal intersection between QSP and gate approximation.
The circuit-gate framework of quantum computing relies on the fact that an arbitrary quantum gate in the form of a unitary matrix of unit determinant can be approximated to a desired accuracy by a fairly short sequence of basic gates, of which the exact bounds are provided by the Solovay–Kitaev theorem. In this work, we show that a version of this theorem is applicable to orthogonal matrices with unit determinant as well, indicating the possibility of using orthogonal matrices for efficient computation. We further develop a version of the Solovay–Kitaev algorithm and discuss the computational experience.
Quantum computation is of current ubiquitous interest in physics, computer science, and the public interest. In the not-so-distant future, quantum computers will be relatively common pieces of research equipment. Eventually, one can expect an actively quantum computer to be a common feature of life. In this work, I study the approximation efficiency of several common universal quantum gate sets at short sequence lengths using an implementation of the Solovay-Kitaev algorithm. I begin by developing from almost nothing the relevant formal mathematics to rigorously describe what one means by the terms universal gate set and covering efficiency. I then describe some interesting results on the asymptotic covering properties of certain classes of universal gate sets and discuss the theorem which the Solovay-Kitaev algorithm is based on. Moving from mathematical introduction to experimental method, I then describe how sets will be compared. I use the commonly studied sets H+T, Pauli+V, V, and Clifford+T to determine which is the most efficient at approximating randomly generated unitaries. By doing so, we get an understanding of how well each set would perform in the context of a general quantum computer processor. This was accomplished by using the same implementation of the Solovay-Kitaev algorithm throughout, with roughly equal-sized preprocessed libraries formed from each gate set, over approximations for 10,000 randomly generated unitary matrices at algorithm depth n=5. Ultimately, the Pauli+V and V sets were the most efficient and had similar performance qualities. On average the Pauli+V set produced approximations of length 15,491 and accuracy 0.0002686. The V basis produced approximations of average sequence length 16,403 and accuracy 0.0001465. This performance is about equal given this particular implementation of the Solovay-Kitaev algorithm. We conclude that this result is somewhat surprising as the general behavior and efficiency of these particular choices of gate set are expected to be similar. It is possible though that the asymptotic efficiencies of these gate sets vary by a relatively wide margin and this has effected the experiment. It is also possible that some aspect of a naive implementation of the Solovay-Kitaev algorithm resulted in the Hadamard gate based sets performing more poorly than the V basis sets overall. Due to constraints on computational power, this result could also be limited to this particular accuracy regime and could even out as tolerance 𝜀 is taken to be arbitrarily small. Further possibilities of this result as well as further work are then discussed.
The Solovay-Kitaev algorithm is a fundamental result in quantum computation. It gives an algorithm for efficiently compiling arbitrary unitaries using universal gate sets: any unitary can be approximated by short gates sequences, whose length scales merely poly-logarithmically with accuracy. As a consequence, the choice of gate set is typically unimportant in quantum computing. However, the Solovay-Kitaev algorithm requires the gate set to be inverse-closed. It has been a longstanding open question if efficient algorithmic compilation is possible without this condition. In this work, we provide the first inverse-free Solovay-Kitaev algorithm, which makes no assumption on the structure within a gate set beyond universality, answering this problem in the affirmative, and providing an efficient compilation algorithm in the absence of inverses for both SU(d) and SL(d,C). The algorithm works by showing that approximate gate implementations of the generalized Pauli group can self-correct their errors.
Quantum signal processing (QSP) is a template for designing algorithms in the quantum circuit model. We consider three facets of this template. First, how to compute the exact circuit for a given algorithm and problem parameters. QSP requires two interrelated pre-processing steps. We give an algorithm for the first step, and compare its performance to recent alternatives. We find that our algorithm, using the Wilson method, is competitive for sparse polynomials away from the near-coherent regime. Next, we give an algorithm for quantum phase or energy estimation (QPE and QEE), designed with QSP. QEE replaces the common oracle access model in QPE with a block-encoding. We use von Neumann's measurement protocol and Hamiltonian simulation with QSP to show that QEE can be solved efficiently. We then show that when the standard QPE oracle is block-encoded, QPE algorithm with logarithmic overhead. We also show that whenever the system of interest is described by a linear combination of Pauli terms, the gate complexity of the entire algorithm is efficient in Clifford and T gates. We then consider how QSP relates to time-evolution. We show that QSP circuits can be understood as the circuits generated by a piecewise continuous time-evolution. Specifically, this evolution fits the bilinear control model, a common model in quantum control theory. Finally, we engineer a continuous time-dependent system for which the quantum adiabatic theorem will hold, which syntactically resembles QSP. We show that in the high-degree and small-signal limit, when the adiabatic schedule is Lipschitz continuous, the quantum adiabatic evolution of an eigenstate of H(0) is close to a QSP circuit applied to the same eigenstate. Crucially, our formalism establishes a direct functional relationship between the adiabatic schedule and the set of phase factors that determine the QSP circuit.
Arbitrarily accurate fault-tolerant (FT) universal quantum computation can be carried out using the Clifford gates Z, S, CNOT plus the non-Clifford T gate. Moreover, a recent improvement of the Solovay-Kitaev theorem by Kuperberg implies that to approximate any single-qubit gate to an accuracy of ε>0 requires O(logc[1/ε]) quantum gates with c>1.44042. Can one do better? That was the question asked by Nielsen and Chuang in their quantum computation textbook. Specifically, they posted a challenge to efficiently approximate single-qubit gate, fault-tolerantly or otherwise, using Ω(log[1/ε]) gates chosen from a finite set. Here I give a partial answer to this question by showing that this is possible using O(log[1/ε]loglog[1/ε]logloglog[1/ε]⋯) FT gates chosen from a finite set depending on the value of ε. The key idea is to construct an approximation of any phase gate in a FT way by recursion to any given accuracy ε>0. This method is straightforward to implement, easy to understand, and interestingly does not involve the Solovay-Kitaev theorem.
The efficient compiling of arbitrary single-qubit gates into a sequence of gates from a finite gate set is of fundamental importance in quantum computation. The exact bounds of this compilation are given by the Solovay–Kitaev theorem, which serves as a powerful tool in compiling quantum algorithms that require many qubits. However, the inverse closure condition it imposes on the gate set adds a certain complexity to the experimental compilation, making the process less efficient. This was recently resolved by a version of the Solovay–Kitaev theorem for inverse-free gate sets, yielding a significant gain. Considering the recent progress in the field of three-level quantum systems, in which qubits are replaced by qutrits, it is possible to achieve the quantum speedup guaranteed by the Solovay–Kitaev theorem simply from orthogonal gates. Nevertheless, it has not been investigated previously whether the condition of inverse closure can be relaxed for these qutrit-based orthogonal compilations as well. In this work, we answer this positively, by obtaining improved Solovay–Kitaev approximations to an arbitrary orthogonal qutrit gate, with an accuracy ε from a sequence of O(log8.62(1/ε)) orthogonal gates taken from an inverse-free set.