Document Open Access Logo

On Learning Linear Functions from Subset and Its Applications in Quantum Computing

Authors Gábor Ivanyos, Anupam Prakash, Miklos Santha

PDF
Thumbnail PDF

File

LIPIcs.ESA.2018.66.pdf
  • Filesize: 434 kB
  • 14 pages

Document Identifiers

Author Details

Gábor Ivanyos
  • Institute for Computer Science and Control, Hungarian Academy of Sciences, Budapest, Hungary
Anupam Prakash
  • CNRS, IRIF, Université Paris Diderot 75205 Paris, France
Miklos Santha
  • CNRS, IRIF, Université Paris Diderot 75205 Paris, France
  • and , Centre for Quantum Technologies, National University of Singapore, Singapore 117543

Funding

A part of the research was accomplished while the first two authors were visiting the Centre for Quantum Technologies (CQT), National University of Singapore. The research at CQT was partially funded by the Singapore Ministry of Education and the National Research Foundation under grant R-710-000-012-135. This research was supported in part by the QuantERA ERA-NET Cofund project QuantAlgo and by the Hungarian National Research, Development and Innovation Office - NKFIH, Grant K115288.

Cite AsGet BibTex

Gábor Ivanyos, Anupam Prakash, and Miklos Santha. On Learning Linear Functions from Subset and Its Applications in Quantum Computing. In 26th Annual European Symposium on Algorithms (ESA 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 112, pp. 66:1-66:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
https://doi.org/10.4230/LIPIcs.ESA.2018.66

Abstract

Let F_{q} be the finite field of size q and let l: F_{q}^{n} -> F_{q} be a linear function. We introduce the Learning From Subset problem LFS(q,n,d) of learning l, given samples u in F_{q}^{n} from a special distribution depending on l: the probability of sampling u is a function of l(u) and is non zero for at most d values of l(u). We provide a randomized algorithm for LFS(q,n,d) with sample complexity (n+d)^{O(d)} and running time polynomial in log q and (n+d)^{O(d)}. Our algorithm generalizes and improves upon previous results [Friedl et al., 2014; Gábor Ivanyos, 2008] that had provided algorithms for LFS(q,n,q-1) with running time (n+q)^{O(q)}. We further present applications of our result to the Hidden Multiple Shift problem HMS(q,n,r) in quantum computation where the goal is to determine the hidden shift s given oracle access to r shifted copies of an injective function f: Z_{q}^{n} -> {0, 1}^{l}, that is we can make queries of the form f_{s}(x,h) = f(x-hs) where h can assume r possible values. We reduce HMS(q,n,r) to LFS(q,n, q-r+1) to obtain a polynomial time algorithm for HMS(q,n,r) when q=n^{O(1)} is prime and q-r=O(1). The best known algorithms [Andrew M. Childs and Wim van Dam, 2007; Friedl et al., 2014] for HMS(q,n,r) with these parameters require exponential time.

Subject Classification

ACM Subject Classification
  • Theory of computation → Quantum computation theory
Keywords
  • Learning from subset
  • hidden shift problem
  • quantum algorithms
  • linearization

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. Vincenzo Acciaro. The probability of generating some common families of finite groups. Utilitas Math., 49:243-254, 1996. Google Scholar
  2. Sanjeev Arora and Rong Ge. New algorithms for learning in presence of errors. In Proceedings of the 38th International Colloquium on Automata, Languages and Programming ICALP, Zurich, Switzerland, pages 403-415. Springer, 2011. Google Scholar
  3. Avrim Blum, Adam Kalai, and Hal Wasserman. Noise-tolerant learning, the parity problem, and the statistical query model. Journal of the ACM (JACM), 50(4):506-519, 2003. Google Scholar
  4. Andrew M. Childs, Robin Kothari, Maris Ozols, and Martin Roetteler. Easy and hard functions for the boolean hidden shift problem. In Simone Severini and Fernando G. S. L. Brandão, editors, 8th Conference on the Theory of Quantum Computation, Communication and Cryptography, TQC 2013, May 21-23, 2013, Guelph, Canada, volume 22 of LIPIcs, pages 50-79. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2013. URL: http://dx.doi.org/10.4230/LIPIcs.TQC.2013.50.
  5. Andrew M. Childs and Wim van Dam. Quantum algorithm for a generalized hidden shift problem. In Nikhil Bansal, Kirk Pruhs, and Clifford Stein, editors, Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2007, New Orleans, Louisiana, USA, January 7-9, 2007, pages 1225-1232. SIAM, 2007. URL: http://dl.acm.org/citation.cfm?id=1283383.1283515.
  6. Thomas Decker, Gábor Ivanyos, Raghav Kulkarni, Youming Qiao, and Miklos Santha. An efficient quantum algorithm for finding hidden parabolic subgroups in the general linear group. In International Symposium on Mathematical Foundations of Computer Science, pages 226-238. Springer, 2014. Google Scholar
  7. Mark Ettinger and Peter Høyer. On quantum algorithms for noncommutative hidden subgroups. Advances in Applied Mathematics, 25:239-251, 2000. URL: http://arxiv.org/abs/arXiv:quant-ph/9807029.
  8. Katalin Friedl, Gábor Ivanyos, Frédéric Magniez, Miklos Santha, and Pranab Sen. Hidden translation and translating coset in quantum computing. SIAM Journal on Computing, 43(1):1-24, 2014. preliminary version in STOC 2003. Google Scholar
  9. Dmitry Gavinsky, Martin Roetteler, and Jérémie Roland. Quantum algorithm for the boolean hidden shift problem. In Bin Fu and Ding-Zhu Du, editors, Computing and Combinatorics - 17th Annual International Conference, COCOON 2011, Dallas, TX, USA, August 14-16, 2011. Proceedings, volume 6842 of Lecture Notes in Computer Science, pages 158-167. Springer, 2011. URL: http://dx.doi.org/10.1007/978-3-642-22685-4_14.
  10. Gábor Ivanyos. On solving systems of random linear disequations. Quantum Information & Computation, 8(6):579-594, 2008. URL: http://www.rintonpress.com/xxqic8/qic-8-67/0579-0594.pdf.
  11. Gábor Ivanyos, Anupam Prakash, and Miklos Santha. On learning linear functions from subset and its applications in quantum computing. arXiv, 2018. URL: http://arxiv.org/abs/1710.02581.
  12. Erich Kaltofen. Polynomial-time reductions from multivariate to bi- and univariate integral polynomial factorization. SIAM J. Comput., 14(2):469-489, 1985. URL: http://dx.doi.org/10.1137/0214035.
  13. Greg Kuperberg. A subexponential-time quantum algorithm for the dihedral hidden subgroup problem. SIAM Journal on Computing, 35(1):170-188, 2005. URL: http://arxiv.org/abs/quant-ph/0302112.
  14. Michael A Nielsen and Isaac Chuang. Quantum computation and quantum information, 2002. Google Scholar
  15. Chris Peikert. Public-key cryptosystems from the worst-case shortest vector problem. In Proceedings of the forty-first annual ACM symposium on Theory of computing, pages 333-342. ACM, 2009. Google Scholar
  16. Carl Pomerance. The expected number of random elements to generate a finite abelian group. Periodica Mathematica Hungarica, 43(1):191-198, Aug 2002. URL: http://dx.doi.org/10.1023/A:1015250102792.
  17. Oded Regev. On lattices, learning with errors, random linear codes, and cryptography. Journal of the ACM (JACM), 56(6):34, 2009. Google Scholar
  18. Martin Roetteler. Quantum algorithms for abelian difference sets and applications to dihedral hidden subgroups. In Anne Broadbent, editor, 11th Conference on the Theory of Quantum Computation, Communication and Cryptography, TQC, September 27-29, 2016, Berlin, Germany, volume 61 of LIPIcs, pages 8:1-8:16. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2016. URL: http://dx.doi.org/10.4230/LIPIcs.TQC.2016.8.
  19. Jacob T Schwartz. Fast probabilistic algorithms for verification of polynomial identities. Journal of the ACM (JACM), 27(4):701-717, 1980. Google Scholar
  20. Joachim von zur Gathen and Erich Kaltofen. Polynomial-time factorization of multivariate polynomials over finite fields. In International Colloquium on Automata, Languages, and Programming, pages 250-263. Springer, 1983. Google Scholar
  21. Richard Zippel. Probabilistic algorithms for sparse polynomials. Symbolic and algebraic computation, pages 216-226, 1979. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact