{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,8]],"date-time":"2026-05-08T04:49:19Z","timestamp":1778215759910,"version":"3.51.4"},"reference-count":0,"publisher":"Universitatsbibliothek der Ruhr-Universitat Bochum","license":[{"start":{"date-parts":[[2022,3,11]],"date-time":"2022-03-11T00:00:00Z","timestamp":1646956800000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["ToSC"],"abstract":"<jats:p>We study quantum period finding algorithms such as Simon and Shor (and its variant Eker\u00e5-H\u00e5stad). For a periodic function f these algorithms produce \u2013 via some quantum embedding of f \u2013 a quantum superposition \u2211x |x\u232a |f(x)\u232a, which requires a certain amount of output qubits that represent |f(x)\u232a. We show that one can lower this amount to a single output qubit by hashing f down to a single bit in an oracle setting.Namely, we replace the embedding of f in quantum period finding circuits by oracle access to several embeddings of hashed versions of f. We show that on expectation this modification only doubles the required amount of quantum measurements, while significantly reducing the total number of qubits. For example, for Simon\u2019s algorithm that finds periods in f : Fn2 \u2192 Fn2 our hashing technique reduces the required output qubits from n down to 1, and therefore the total amount of qubits from 2n to n + 1. We also show that Simon\u2019s algorithm admits real world applications with only n + 1 qubits by giving a concrete realization of a hashed version of the cryptographic Even-Mansour construction. Moreover, for a variant of Simon\u2019s algorithm on Even-Mansour that requires only classical queries to Even-Mansour we save a factor of (roughly) 4 in the qubits.Our oracle-based hashed version of the Eker\u00e5-H\u00e5stad algorithm for factoring n-bit RSA reduces the required qubits from (3\/2 + o(1))n down to (1\/2+ o(1))n.<\/jats:p>","DOI":"10.46586\/tosc.v2022.i1.183-211","type":"journal-article","created":{"date-parts":[[2022,3,11]],"date-time":"2022-03-11T08:06:45Z","timestamp":1646986005000},"page":"183-211","source":"Crossref","is-referenced-by-count":4,"title":["Quantum Period Finding is Compression Robust"],"prefix":"10.46586","author":[{"given":"Alexander","family":"May","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Lars","family":"Schlieper","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"25480","published-online":{"date-parts":[[2022,3,11]]},"container-title":["IACR Transactions on Symmetric Cryptology"],"original-title":[],"link":[{"URL":"https:\/\/ojs.ub.ruhr-uni-bochum.de\/index.php\/ToSC\/article\/download\/9533\/9070","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/ojs.ub.ruhr-uni-bochum.de\/index.php\/ToSC\/article\/download\/9533\/11591","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/ojs.ub.ruhr-uni-bochum.de\/index.php\/ToSC\/article\/download\/9533\/9070","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,12,10]],"date-time":"2024-12-10T14:11:22Z","timestamp":1733839882000},"score":1,"resource":{"primary":{"URL":"https:\/\/ojs.ub.ruhr-uni-bochum.de\/index.php\/ToSC\/article\/view\/9533"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,3,11]]},"references-count":0,"URL":"https:\/\/doi.org\/10.46586\/tosc.v2022.i1.183-211","relation":{},"ISSN":["2519-173X"],"issn-type":[{"value":"2519-173X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,3,11]]}}}