Quantum period reconstruction of approximate sequences

Igor E. Shparlinski; Arne Winterhof

doi:10.1016/j.ipl.2007.02.019

Quantum period reconstruction of approximate sequences

Igor E. Shparlinski^*, Arne Winterhof

^*Corresponding author for this work

School of Computing

Research output: Contribution to journal › Article › peer-review

1 Citation (Scopus)

Abstract

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 language	English
Pages (from-to)	211-215
Number of pages	5
Journal	Information Processing Letters
Volume	103
Issue number	6
DOIs	https://doi.org/10.1016/j.ipl.2007.02.019
Publication status	Published - 15 Sept 2007

Access to Document

10.1016/j.ipl.2007.02.019

Cite this

@article{2569b6eb0efe4060917a4d0bf8958e75,

title = "Quantum period reconstruction of approximate sequences",

abstract = "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.",

author = "Shparlinski, \{Igor E.\} and Arne Winterhof",

year = "2007",

month = sep,

day = "15",

doi = "10.1016/j.ipl.2007.02.019",

language = "English",

volume = "103",

pages = "211--215",

journal = "Information Processing Letters",

issn = "0020-0190",

publisher = "Elsevier",

number = "6",

}

TY - JOUR

T1 - Quantum period reconstruction of approximate sequences

AU - Shparlinski, Igor E.

AU - Winterhof, Arne

PY - 2007/9/15

Y1 - 2007/9/15

N2 - 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.

AB - 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.

UR - https://www.scopus.com/pages/publications/34250883844

U2 - 10.1016/j.ipl.2007.02.019

DO - 10.1016/j.ipl.2007.02.019

M3 - Article

AN - SCOPUS:34250883844

SN - 0020-0190

VL - 103

SP - 211

EP - 215

JO - Information Processing Letters

JF - Information Processing Letters

IS - 6

ER -

Quantum period reconstruction of approximate sequences

Abstract

Access to Document

Other files and links

Fingerprint

Cite this