diff b34550f..b1f9bc4 exact_quantum_factoring_v2.txt
diff --git a/exact_quantum_factoring_v2.txt b/exact_quantum_factoring_v2.txt
index e6997fc..e7374ad 100644
--- a/exact_quantum_factoring_v2.txt
+++ b/exact_quantum_factoring_v2.txt
@@ -1,4 +1,4 @@
-The integer factoring problem asks: on input a binary integer $N \ge 2$,
+The integer factoring problem asks: on input a binary integer $N ge 2$,
for the nondecreasing list of primes whose product is $N$, including
multiplicities. For $N = 360$ the answer is $2, 2, 2, 3, 3, 5$.
@@ -9,7 +9,7 @@ from a fixed finite set.
Theorem 1. There is a polynomial-time uniform family of polynomial-size
quantum circuits with the following properties.
- - On input $N \ge 2$, the circuit outputs the complete prime
+ - On input $N ge 2$, the circuit outputs the complete prime
factorization of $N$ with probability 1.
- Gate count and qubit count are bounded by a fixed polynomial in
$n = n(N)$, roughly the bit length of $N$.
@@ -25,7 +25,7 @@ means no failure. Both are worst case.
Shor's algorithm (P. W. Shor, SIAM J. Comput. 26 (1997) 1484-1509) gave
polynomial-time quantum factoring with bounded error. The reduction
uses multiplicative orders: if $a$ has order $r$ modulo $m$ and $r$ is
-even, then $\gcd(a^{r/2}-1, m)$ can split $m$. The splitting argument is
+even, then $gcd(a^{r/2}-1, m)$ can split $m$. The splitting argument is
proved directly below.
./pdf/shor-1997-factoring-discrete-log.pdf
@@ -93,12 +93,12 @@ The proof has two main ingredients, beyond the order-to-gcd reduction.
First, an order trial whose mass on the true order is a prescribed
dyadic rational. For a unit $a$ modulo $m$, its order $r$ is the least
-positive integer with $a^r = 1 \pmod m$. The trial returns no
+positive integer with $a^r = 1 pmod m$. The trial returns no
candidate, or a positive multiple of $r$, and the probability of
-returning $r$ is exactly $\varphi(r)\lambda(r)$, where
-$\lambda(d) = 2^{-\lceil\log_2 d\rceil - 10}$. The construction uses a
+returning $r$ is exactly $varphi(r)lambda(r)$, where
+$lambda(d) = 2^{-lceillog_2 drceil - 10}$. The construction uses a
phase register that realizes a piecewise-linear interpolant $g$ of the
-complex exponential $e(z) = \exp(-2\pi i z)$. Controlled modular shifts
+complex exponential $e(z) = exp(-2pi i z)$. Controlled modular shifts
give a phase-kickback construction in the style of Richard Cleve, Artur
Ekert, Chiara Macchiavello, and Michele Mosca (Proc. R. Soc. Lond. A
454 (1998) 339-354), but the auxiliary state is a four-phase step
@@ -164,7 +164,7 @@ success probability exactly 1/4.
As a first computation, take $N = 15$ and $a = 2$, a unit mod 15. The
powers of 2 mod 15 are $2, 4, 8, 1, 2, ...$, so
$ord_{15}(2) = 4$. Since $r = 4$ is even,
-$\gcd(2^{r/2} - 1, 15) = \gcd(3, 15) = 3$, splitting $15 = 3 \times 5$.
+$gcd(2^{r/2} - 1, 15) = gcd(3, 15) = 3$, splitting $15 = 3 times 5$.
Every factoring run reduces to this. The remaining work is
exact-probability engineering that makes $r$ (a multiple of the true
order) appear with a prescribed dyadic mass, using only a fixed finite
@@ -181,9 +181,9 @@ Exact probabilities require fixed computational conventions. Every
polynomial takes its parameter $n$ as defined below unless indicated
otherwise; every logarithm in a bit bound is base two.
-Definition 1. For an input integer $N \ge 2$, set
+Definition 1. For an input integer $N ge 2$, set
- $n = \max\{128, \lfloor\log_2 N\rfloor + 1\}$, $B = 2^n$.
+ $n = max{128, lfloorlog_2 Nrfloor + 1}$, $B = 2^n$.
Then $N < B$. The cutoff at 128 is a fixed constant; it has no effect
on polynomial-time uniformity and simplifies every strict inequality