Quantum Period is Compression Robust

[Botsina]

TL;DR Summary

https://arxiv.org/abs/1905.10074
Has anyone read the above prepint by Alexander May and Lars Schlieper? What do you think about the prospect of Integer Factorization the Discrete Logarithm problem being in P if an appropriate homomorphic universal hash function can be found?

https://arxiv.org/abs/1905.10074

The paper finds that one can reduce the number of qubits to a constant (just one works) used in the last, modular exponential register of the variants of Shor's algorithm, used to factor integers and find discrete logarithms, by applying a universal hash function to the modular exponential.
(A universal hash function (https://en.wikipedia.org/wiki/Universal_hashing) maps a large number states to a handful of states, where the probability of two states colliding (i.e. producing the same output) is equal over members of the hash function family. A simple example of a family of hash functions is h_{a,b}(x) = (ax + b) mod p mod m, where p is prime.) Despite causing a huge number of collisions in the last register, the period can still be recovered in only constantly more runs of the circuit and this constant is at most two (if one qubit is used) and drops quickly to near one if more qubits are used.

Hashing reduces the number of qubits needed for modular exponentiation to a constant, so if we could reduce the number of period-containing qubits (the first one or two registers) down to polynomial size, presumably one could get period-finding into BPP (in polynomial time). Using a semi-classical version of Shor's algorithm due to Mosca and Ekert in the 1990s, the number of period qubits can be reduced to a constant, but at the price of introducing intermediate measurements. Since the results for compression robustness rely on the standard QFT-function-QFT circuit, the don't apply directly to the Mosca-Ekert algorithm and to recover the result the universal hash function needs to be homomorphic (so that the hashed result can be computed from the composition of already hashed components) in order for the qubit savings to work. If there is a universal homomorphic hash function which uses few enough qubits, then integer factorization and the discrete logarithm problem is in polynomial time.

Can anyone vouch for the accuracy of this paper?

 

[Strilanc]

I think the paper is accurate, but it's unlikely there exists a workable function f that can be composed with g(x) = b^x mod N to form an h(x) = f(g(x)) that can be computed using only constant workspace.