diff b1f9bc4..56bc728 exact_quantum_factoring_v2.txt
diff --git a/exact_quantum_factoring_v2.txt b/exact_quantum_factoring_v2.txt
index e7374ad..f91d137 100644
--- a/exact_quantum_factoring_v2.txt
+++ b/exact_quantum_factoring_v2.txt
@@ -1,6 +1,6 @@
-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$.
+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.
A quantum circuit operates on quantum bits (qubits) whose joint state is
a unit vector of complex amplitudes, acting by unitary matrices drawn
@@ -9,12 +9,12 @@ 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
- factorization of $N$ with probability 1.
+ - 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$.
- - Every circuit uses only the fixed finite gate set $G$: NOT, CNOT,
- Toffoli, Hadamard, $S = diag(1,i)$, their inverses, and
+ n = n(N), roughly the bit length of N.
+ - Every circuit uses only the fixed finite gate set G: NOT, CNOT,
+ Toffoli, Hadamard, S = diag(1,i), their inverses, and
their singly controlled versions.
"Polynomial-time uniform" means that some single deterministic classical
@@ -24,8 +24,8 @@ 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
+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
proved directly below.
./pdf/shor-1997-factoring-discrete-log.pdf
@@ -59,7 +59,7 @@ gives exact order finding that requires a supplied multiple of the
unknown order, which factoring does not provide; Harumichi Nishimura
and Masanao Ozawa (Phys. Rev. A 81 (2010) 012317) show why approximate
universality cannot replace an exact gate analysis. The construction
-below uses only the fixed gate set $G$, receives only $N$, and accepts
+below uses only the fixed gate set G, receives only N, and accepts
no advice.
./pdf/miller-1976-riemann-hypothesis-primality.pdf
@@ -92,13 +92,13 @@ arithmetic; the standard one-step reflection then makes it 1.
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
-candidate, or a positive multiple of $r$, and the probability of
-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(-2pi i z)$. Controlled modular shifts
+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
+candidate, or a positive multiple of r, and the probability of
+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(-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
@@ -123,8 +123,8 @@ factorization is required to run the trial.
./pdf/lev-2001-integral-shor.pdf
Second, a factoring run also generates the prime factorizations of
-$p-1$ for its prime factors $p > 2$, recursively. This auxiliary
-occurrence tree $D(N)$ has polynomial size. The recursive shape
+p-1 for its prime factors p > 2, recursively. This auxiliary
+occurrence tree D(N) has polynomial size. The recursive shape
resembles Vaughan R. Pratt's succinct primality certificates (SIAM J.
Comput. 4 (1975) 214-220), but the role differs: prime labels are
checked by a deterministic primality test proved in the appendix, and
@@ -161,12 +161,12 @@ success probability exactly 1/4.
./pdf/ozols-roetteler-roland-2012-quantum-rejection-sampling.pdf
-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$.
+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.
Every factoring run reduces to this. The remaining work is
-exact-probability engineering that makes $r$ (a multiple of the true
+exact-probability engineering that makes r (a multiple of the true
order) appear with a prescribed dyadic mass, using only a fixed finite
gate set.
@@ -178,16 +178,16 @@ primality test, needed to verify prime-factor lists, appears at the
end.
Exact probabilities require fixed computational conventions. Every
-polynomial takes its parameter $n$ as defined below unless indicated
+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, lfloorlog_2 Nrfloor + 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
+Then N < B. The cutoff at 128 is a fixed constant; it has no effect
on polynomial-time uniformity and simplifies every strict inequality
-below by avoiding small-$n$ edge cases. These $n$ and $B$ apply
+below by avoiding small-n edge cases. These n and B apply
throughout.
Definition 2. The fixed finite gate set G consists of: