Abstract
We consider the problem of determining the period of a binary sequence. 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. We apply this result to several concrete examples for which the autocorrelation can be estimated using known bounds on character sums.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Brandstätter, N., Winterhof, A.: Some notes on the two-prime generator of order 2. IEEE Trans. Inform. Theory 51, 3654–3657 (2005)
van Dam, W., Hallgren, S., Ip, L.: Quantum algorithms for some hidden shift problems. In: Proc. of the 14th Annual ACM-SIAM Symposium on Discrete Algorithms, Baltimore, pp. 489–498. ACM, New York (2003)
Ding, C.: Autocorrelation values of generalized cyclotomic sequences of order two. IEEE Trans. Inform. Theory 44, 1699–1702 (1998)
Hales, L., Hallgren, S.: An improved quantum Fourier transform algorithm and applications. In: Proc. 41st IEEE Symp. on Found. of Comp. Sci., pp. 515–525 (2000)
Kohel, D.R., Shparlinski, I.E.: Exponential sums and group generators for elliptic curves over finite fields. In: Bosma, W. (ed.) ANTS 2000. LNCS, vol. 1838, pp. 395–404. Springer, Heidelberg (2000)
Lidl, R., Niederreiter, H.: Finite Fields. Cambridge University Press, Cambridge (1997)
Meidl, W., Winterhof, A.: On the autocorrelation of cyclotomic generators. In: Mullen, G.L., Poli, A., Stichtenoth, H. (eds.) Fq7 2003. LNCS, vol. 2948, pp. 1–11. Springer, Heidelberg (2004)
Russell, A., Shparlinski, I.E.: Classical and quantum function reconstruction via character evaluation. J. Complexity 20, 404–422 (2004)
Shor, P.: Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM J. Comp. 26, 1484–1509 (1997)
Shparlinski, I., Winterhof, A.: Quantum period reconstruction of noisy sequences. In: Proc. ERATO Conf. on Quantum Inform. Sci., Tokyo, pp. 7–8 (2005)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2006 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Piroi, F., Winterhof, A. (2006). Quantum Period Reconstruction of Binary Sequences. In: Fossorier, M.P.C., Imai, H., Lin, S., Poli, A. (eds) Applied Algebra, Algebraic Algorithms and Error-Correcting Codes. AAECC 2006. Lecture Notes in Computer Science, vol 3857. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11617983_5
Download citation
DOI: https://doi.org/10.1007/11617983_5
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-31423-3
Online ISBN: 978-3-540-31424-0
eBook Packages: Computer ScienceComputer Science (R0)