Our construction

Approximation error

Because we are using oblivious carry runways and the coset representation of modular integers, the computations we perform are not exact. Rather, they are approximations. This is not a problem in practice, as we may bound the approximation error using concepts and results. 

The oblivious runways and the coset representation of modular integers are both examples of "approximate encoded permutations" which have a "deviation". When using a padding/runway length of c_{pad}, and a runway separation of csep, the deviation per addition is at most n/(c_{sep}2^{c_{pad}}) . Deviation is subadditive under composition, so the deviation of the entire modular exponentiation process is at most the number of lookup additions times the deviation per addition.

Figure 4

Figure 4: Space usage during the key lookup-add-unlookup inner loop of our construction. During lookup, the target register is spread out to make room for the temporary register that will hold the lookup's output. During addition the target register and lookup output register are squeezed through a moving operating area that sweeps up then down, applying the MAJ and UMA sweeps of Cuccaro's adder. Uncomputing the lookup is done with measurement-based uncomputation, which is overlapped slightly with the UMA sweep (this is why the yellow rows disappear early). "CCZ factory" space is being used to produce CCZ states. "CCZ fixup" space is being used to convert the CCZ states into AutoCCZ states. "MAJ/UMA" space is being used to perform a ripple carry addition, fueled by AutoCCZ states, of the temporary register (the result of the lookup) into the target register.

We can use this to check how much deviation results from using c_{pad} = 2 \; lg \; n + lg \; n_e + 10, which we so far have merely claimed would be sufficient: 

\text{TotalDeviation}(n, n_e) ≤ \text{LookupAdditionCount}(n, n_e) · \dfrac{n}{c_{sep} 2^{c_{pad}}}

≈ 0.1n_en \dfrac{n}{1024 · 2^{2 \; lg \; n+lg \; n_e+10}} 

≈ 0.1 \dfrac{n^2n_e}{1024 · n^2n_e · 2^{10}}

= 0.1 \dfrac{1}{1024 · 2^{10}}

≈ 10^{−7} (4) 

When an approximate encoded permutation has a deviation of {\epsilon} , the trace distance between its output and the ideal output is at most \sqrt[2]{\epsilon}. Therefore the approximation error (i.e. the trace distance due to approximations), using the parameter assignments we have described, is roughly 0.1%. This is significantly lower than other error rates we will calculate
Back to '10.3: Shor's Algorithm'