Quantum period reconstruction of approximate sequences

Igor E. Shparlinski*, Arne Winterhof

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

1 Citation (Scopus)


We consider the problem of determining the period of a sequence over an unknown finite field, given a black-box which returns only a few most significant bits of the sequence elements. For sequences with small autocorrelation we prove the existence of a polynomial time quantum algorithm for the above problem based on an algorithm of Hales and Hallgren.

Original languageEnglish
Pages (from-to)211-215
Number of pages5
JournalInformation Processing Letters
Issue number6
Publication statusPublished - 15 Sep 2007


Dive into the research topics of 'Quantum period reconstruction of approximate sequences'. Together they form a unique fingerprint.

Cite this