0
$\begingroup$

https://arxiv.org/abs/1905.10074

https://crypto.stanford.edu/~dabo/pubs/abstracts/quantum.html

Below are a few questions about May and Schlieper's paper "Quantum Period Finding is Compression Robust". The second link is to Boneh and Lipton's paper on quantum period finding algorithms, since citing papers is evidently not implemented. All notation not from May and Schlieper is from Boneh and Lipton.

Firstly, for Theorem 6.1 on page 16, the theorem establishes that for a universal hash function with collision probability $\frac{1}{m}$, the probability of measuring $y$ is reduced from $p(y)$ to $\frac{m-1}{m}p(y)$ if we hash the function register. If, instead, we substitute a universal hash function for a near universal hash function with collision probability $\le \frac{2}{m}$, is the probability of observing $y$ at least $\frac{m-2}{m}p(y)$? Theorem 6.1 shows that a hashed version of Shor's algorithms and related variants will still yield the correct answer with only a constant factor more measurements, even though hashing produces are large number of collisions.

Following the proof, $p_h(y) \le \sum_{z \in Im(f)} |w_{y,z}|^2 + \frac{2}{m}\sum_{z_1 \neq z_2} w_{y,z_1} \bar{w}_{y,z_2} $. Combining this inequality with $\sum_{z \in Im(f)} w_{y,z} = 0$ for $y=0$, $$ 0 = \frac{2}{m} |\sum_{z \in Im(f)} w_{y,z}|^2 = \frac{2}{m} \sum_{z \in Im(f)} |w_{y,z}|^2 + \frac{2}{m} \sum_{z_1 \neq z_2} w_{y,z_1} \bar{w}_{y,z_2} \le p_h(y) - \frac{m-2}{m}\sum_{z \in Im(f)} |w_{y,z}|^2 $$

so that

$$ p_h(y) \ge \frac{m-2}{m} p(y) $$


This second question concerns using a hashed Mosca-Ekert variant of Shor's algorithm to put integer factorization in BPP outlined in section 8. The Mosca-Ekert algorithm is a semi-classical version of Shor's algorithm with only a single qubit for the answer registers with hashing for the function register. In order for factoring to be shown to be in BPP, a homomorphic universal hash function is needed because the Mosca-Ekert algorithm uses intermediate measurements and isn't the QFT-function-QFT circuit which Theorem 6.1 uses. Could the need for a homomorphic hash function be bypassed if instead one started with a quantum circuit in the QFT-function-QFT template which outputted the discrete logarithm modulo some $O(\log p)$-sized primes and used the Chinese Remainder Theorem to reconstruct the full discrete logarithm?

We can't just take the modulus of the original circuit, because the modulus contains information on the entire period and not just the period modulo some prime $w$. Instead we replace the last QFTs with QFT based on $w$. To extract only $\alpha \mod w$, we'd like to change the basis of the QFT to $\exp(\frac{2\pi i}{w})$, so that $s_2 - \alpha s_1$ encodes $\alpha \mod w$ and minimize $\exp[\frac{2\pi i}{w} \frac{\alpha r_2}{q}\{s_1 q \}_{w}]$ so that interference from the last term doesn't destroy the answer.

Specifically, we need to minimize the argument of $$ \exp [ \frac{2\pi i}{w} r_2(s_2 - \alpha s_1 + \frac{\alpha}{q}\{s_1 q \}_{w})] $$

when $s_2 - \alpha s_1 = 0 \mod w$ so that summing over all $r_2$, the terms will not cancel. If $s_2 - \alpha s_1 \neq 0 \mod w$, large multiples or $r_2$ will ensure terms quickly cancel. Unlike the normal case to extract just the period modulo some prime $w$, $s_2 - \alpha s_1$ should be a multiple of $w$ so that exponent reduces to $$ \exp [ \frac{2\pi i}{w} r_2\frac{\alpha}{q}\{s_1 q \}_{w}] $$

$\frac{\{s_1 q \}_{w}}{w} < 1$ so for the exponent to have constructive interference we need $\frac{r_2 \alpha}{q} < 1$. This can't be achieved for the normal ranges of $r_2$ and the period $\alpha$. If we restrict $\alpha$ to be small, on the order of the square root of $q$ as naturally occurs in the case of factoring semiprimes by finding a discrete logarithm and restrict the range of $r_2$ to a little less than $\sqrt q$, but still a power of 2, then the circuit should produce $\alpha \mod w$ in roughly the same number of measurements as the full circuit which produces $\alpha$.

It seems that to find larger periods $\alpha$, the range of $r_2$ would have to be reduced and to find $\alpha$ on the order of $q$ the range of $r_2$ would have to be reduced to about $w$. This obviously wouldn't work as an actual quantum algorithm with noise, however could it work in a classical simulation of the quantum circuit with hashing? And, lastly, is the hashing of the final output of the function register really necessary?

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.