(joint work with Lars Schlieper and Jonathan Schwinger)

In the first part of the talk we show that quantum period finding algorithms like Simon and Shor (variants) are surprisingly robust under compression. This implies that in some cryptanalytic relevant cases we can significantly decrease the required number of qubits at the cost of only few more measurements.

In the second part we consider the error robustness of Simon period finding on noisy quantum devices, by running experiments on IBMQ-16. We show that our IBMQ-16 data can be tranformed into a problem that is equivalent to LPN. Nevertheless, we achieve quantum speedups for noisy quantum devices even for large error rates.