Factoring with Qutrits: Shor's Algorithm on Ternary and Metaplectic Quantum Architectures

Understand

We determine the cost of performing Shor's algorithm for integer factorization on a ternary quantum computer, using two natural models of universal fault-tolerant computing: (i) a model based on magic state distillation that assumes the availability of the ternary Clifford gates, projective measurements, classical control as its natural instrumentation set; (ii) a model based on a metaplectic topological quantum computer (MTQC).

• A natural choice to implement Shor's algorithm on a ternary quantum computer is to translate the entire arithmetic into a ternary form.
• However, it is also possible to emulate the standard binary version of the algorithm by encoding each qubit in a three-level system.
• We compare the two approaches and analyze the complexity of implementing Shor's period finding function in the two models.