Factoring with qutrits: Shor's algorithm on ternary and metaplectic quantum architectures

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. We also highlight the fact that the cost of achieving universality through magic states in MTQC architecture is asymptotically lower than in generic ternary case.

Figure 1

Exact representation of the $P_9$ gate by state injection. $C_{\mu ,m}$ stands for a certain precompiled ternary Clifford gate, classically predicated by the measurement result $m$.

Figure 2

Markov chain for repeat-until-success implementation of the injection of the $R_{|2\rangle }$ gate [17]. Starting point is a general input $a|0\rangle +b|1\rangle +c|2\rangle$, where $a,b,c\in \mathbb{C}$. Arrows indicate transitions between single-qutrit states. Each arrow represents a single trial including measurement and consumption of the resource state $|\psi \rangle$, where each of the transitions is labeled with the measurement result. The absorbing state corresponds to successful implementation of the $R_{|2\rangle }$ gate and is denoted by double borders.

Figure 3

Ripple-carry adder from [32].

Figure 4

Top-level layout of modular additive shift for binary encoding.

Figure 5

Top-level layout of ternary modular additive shift. In case $2a<N$, the circuit is compiled with the additional $C_2(+N)$ shift controlled on $c=2$ and using the threshold $t=ca$. In case $2a>N$, the additional shift is not needed, but the threshold $t=c(a-N)+N$.

Figure 6

Exact representation of $C_1\left(Z\right)$ in terms of $P_9$ gates.

Figure 7

Exact representation of $C_0\left(Z\right)$ in $P_9$ depth 1.