Trading inverses for an irrep in the Solovay-Kitaev theorem

Abstract

The Solovay-Kitaev theorem states that universal quantum gate sets can be exchanged with low overhead. More specifically, any gate on a fixed number of qudits can be simulated with error $\epsilon$ using merely $\mathrm{polylog}(1/\epsilon )$ gates from any finite universal quantum gate set $\mathcal{G}$. One drawback to the theorem is that it requires the gate set $\mathcal{G}$ to be closed under inversion. Here we show that this restriction can be traded for the assumption that $\mathcal{G}$ contains an irreducible representation of any finite group $G$. This extends recent work of Sardharwalla et al. [arXiv:1602.07963], and applies also to gates from the special linear group. Our work can be seen as partial progress towards the long-standing open problem of proving an inverse-free Solovay-Kitaev theorem [arXiv:quant-ph/0505030, arXiv:0908.0512].

16 pages, TQC 2018 proceedings version

References in corpus (2)

• The quantum FFT can be classically simulated
• Quantum automata, braid group and link polynomials

Cited by in corpus (19)

• Graph isomorphism and Gaussian boson sampling
• Energy-constrained discrimination of unitaries, quantum speed limits and a Gaussian Solovay-Kitaev theorem
• On the Exact Evaluation of Certain Instances of the Potts Partition Function by Quantum Computers
• Quantum Computation Beyond the Circuit Model
• Verifying commuting quantum computations via fidelity estimation of weighted graph states
• Entanglement Theory and the Quantum Simulation of Many-Body Physics
• Belief Propagation and Loop Series on Planar Graphs
• Measurement-based quantum simulation of Abelian lattice gauge theories
• Fast quantum algorithms for approximating some irreducible representations of groups
• A BQP-complete problem related to the Ising model partition function via a new connection between quantum circuits and graphs
• Shaded Tangles for the Design and Verification of Quantum Programs (Extended Abstract)
• Shaded tangles for the design and verification of quantum circuits
• Quantum computational universality of hypergraph states with Pauli-X and Z basis measurements
• A theorem on the quantum evaluation of Weight Enumerators for a certain class of Cyclic Codes with a note on Cyclotomic cosets
• A PromiseBQP-complete String Rewriting Problem
• Density and unitarity of the Burau representation from a non-semisimple TQFT
• Two remarks on the local Hamiltonian problem
• New Planar P-time Computable Six-Vertex Models and a Complete Complexity Classification
• Extremal jumps of circuit complexity of unitary evolutions generated by random Hamiltonians