Solovay-Kitaev algorithm and randomized compilation
Oliver G. Maupin, Ashlyn D. Burch, Christopher G. Yale, Matthew N. H. Chow, Colvin, Terra, TJ, Brandon Ruzic, Melissa Revelle, Brian McFarland, Eduardo Ibarra-García-Padilla, Alejandro Rascon, Andrew J. Landahl, Susan Clark, Peter J. Love
We analyze the use of the Solovay Kitaev (SK) algorithm to generate an ensemble of one qubit rotations over which to perform randomized compilation. We perform simulations to compare the trace distance between the quantum state resulting from an ideal one qubit $R_{Z}$ rotation and discrete SK decompositions. We find that this simple randomized gate synthesis algorithm can reduce the approximation error of these rotations in the absence of gate errors in simulation by at least a factor of two compared to a naive gate synthesis algorithm. We test the technique under the effects of a simple coherent noise model and find that it can mitigate coherent noise. We also run our algorithm on Sandia National Laboratories' QSCOUT trapped-ion device and find that randomization is able to help in the presence of realistic noise sources.
We analyze the use of the Solovay Kitaev (SK) algorithm to generate an ensemble of one qubit rotations over which to perform randomized compilation. We perform simulations to compare the trace distance between the quantum state resulting from an ideal one qubit RZ rotation and discrete SK decompositions. We find that this simple randomized gate synthesis algorithm can reduce the approximation error of these rotations in the absence of gate errors in simulation by at least a factor of two compared to a naive gate synthesis algorithm. We test the technique under the effects of a simple coherent noise model and find that it can mitigate coherent noise. We also run our algorithm on Sandia National Laboratories' QSCOUT trapped-ion device and find that randomization is able to help in the presence of realistic noise sources.
We present Stochastic Commutator Synthesis, a hybrid quantum gate compilation framework that integrates Kuperberg's sub-cubic Solovay-Kitaev exponent c near 1.44042 with the error-tailoring machinery of randomized compilation. Classical Solovay-Kitaev implementations produce known word lengths and accumulate coherent approximation errors that degrade fault-tolerant threshold estimates. Kuperberg's 2023-2025 result reduces this via doubly exponential convergence and higher-order commutator decompositions. SCS augments this geometric backbone with a Gibbs-sampled stochastic choice of commutator factors at each recursion level, converting coherent synthesis residuals into incoherent, Pauli-twirl-compatible noise -- a property exploited by RC. Combined with RL-guided pre-synthesis, SCS achieves consistent T-count reductions of 10-25 percent and demonstrates fidelity gains of up to 35 percent on multi-fold Forrelation circuits on trapped-ion hardware such as Sandia QSCOUT. We situate SCS within the complexity-theoretic landscape established by the Raz-Tal oracle separation, arguing that low-error, noise-robust compilation of Forrelation-type circuits constitutes a practical pathway toward demonstrating this separation on physical hardware.
Quantum circuit synthesis is one of the major areas of current research in the field of quantum computing.Analogous to its Boolean counterpart, the task involves constructing arbitrary quantum gates using only those available within a small set of universal gates that can be realized physically.However, unlike the latter, there are an infinite number of single qubit quantum gates, all of which constitute the special unitary group SU(2).Realizing any given single qubit gate using a given universal gate family is a complex task.Although gates can be synthesized to arbitrary degree of precision as long as the set of finite strings of the gate family is a dense subset of SU(2), it is desirable to accomplish the highest level of precision using only the minimum number of universal gates within the string approximation.Almost all algorithms that have been proposed for this purpose are based on the Solovay-Kitaev algorithm.The crux of the Solovay-Kitaev algorithm is the use of a procedure to decompose a given quantum gate into a pair of group commutators with the pair being synthesized separately.The Solovay-Kitaev algorithm involves group commutator decomposition in a recursive manner, with a direct approximation of a gate into a string of universal gates being performed only at the last level, i.e. in the leaf nodes of the search tree representing the execution of the Solovay-Kitaev algorithm.The main contribution of this research is in integrating conventional optimization procedures within the Solovay-Kitaev algorithm.Two specific directions of research have been studied.Firstly, optimization is incorporated within the group commutator decomposition, so that a more optimal pair of group commutators are obtained.As the degree of precision of the synthesized gate is explicitly minimized by means of this optimization procedure, the enhanced algorithm allows for more accurate quantum gates to be synthesized than what the original Solovay-Kitaev algorithm achieves.Simulation results with random gates indicate that the obtained accuracy is an order of magnitude better than before.Two versions of the new algorithm are examined, with the optimization in the first version being invoked only at the bottom level of Solovay-Kitaev algorithm and when carried out across all levels of the search tree in the next.Extensive simulations show that the second version yields better results despite equivalent computation times.Theoretical analysis of the proposed algorithm is able to provide a more formal, quantitative explanation underlying the experimentally observed phenomena.The other direction of investigation of this research involves formulating the group commutator decomposition in the form of bi-criteria optimization.This phase of research relaxed the equality constraint in the previous approach and with relaxation, a bi-criteria optimization is proposed.This optimization algorithm is new and has been devised primarily when the objective needs to be relaxed in different stages.This bi-criteria approach is able to provide comparably accurate synthesis as the previous approach.
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 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.
Error mitigation is essential for near-term quantum devices, and two promising techniques are universal frame randomization and Randomized Compilation. These methods insert random twirling gates into a circuit to reduce errors while preserving unitarity and depth. We apply universal frame randomization and Randomized Compilation to the quantum approximate optimization algorithm (QAOA) with p=1 on a superconducting quantum circuit system, demonstrating its potential to improve energy calculations. Specifically, we investigate the use of QAOA to calculate the lowest energy state of a frustrated Ising ring system and compare the results of randomized circuits generated using both techniques. Our results show that both methods can mitigate errors, with expected extremal energy values of 5.25±0.145 and 4.08±0.36, for Randomized Compilation and universal frame randomization respectively, compared to 2.63±0.068 without randomization and 5.676±0.006 with a noiseless simulator.
Fault-tolerant architectures implement non-Clifford T gates through magic-state distillation, so the T-count of a synthesized circuit dominates its physical cost. The Solovay-Kitaev algorithm approximates any single-qubit unitary from a finite gate set with a sequence length that grows only polylogarithmically in the inverse target error, but it optimizes for numerical convergence rather than circuit economy, and its output carries structural redundancy that a gate-level compiler cannot see. We report a measurement of what diagrammatic post-processing recovers from that redundancy. Twelve hundred random single-qubit targets, spanning the three Pauli rotation families and the general gate U(theta, phi, lambda), are synthesized over Clifford+T at three recursion depths, translated into graph-like ZX-diagrams, simplified by automated rewriting, and extracted back to circuits. Post-processing removes 26.6-30.1% of the total gate count and 18.5-22.2% of the T-count. The absolute saving grows with recursion depth, from about 60 to about 1600 gates, while the fractional saving does not: it rises slightly from the shallowest setting and is then flat across a twenty-five-fold change in circuit length, and by the deepest setting the four target families are no longer distinguishable from one another. Because the rewrite rules preserve the implemented linear map, the approximation error is unchanged. The compile-time cost of the rewriting layer, by contrast, grows sharply with depth and comes to dominate the synthesis itself.