Paper 2022/1647

Quantum Algorithm for Oracle Subset Product

Trey Li
Abstract

In 1993 Bernstein and Vazirani proposed a quantum algorithm for the Bernstein-Vazirani problem, which is given oracle access to the function f(a1,,an)=a1x1++anxn(mod2) with respect to a secret string x=x1xn{0,1}n, where a1,,an{0,1}, find x. We give a quantum algorithm for a new problem called the oracle subset product problem, which is given oracle access to the function f(a1,,an)=a1x1anxn with respect to a secret string x=x1xn{0,1}n, where a1,,anZ, find x. Similar to the Bernstein-Vazirani algorithm, it is a quantum algorithm for a problem that is originally polynomial time solvable by classical algorithms; and that the advantage of the algorithm over classical algorithms is that it only makes one call to the function instead of n calls.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
Preprint.
Keywords
Quantum Algorithm Oracle Subset Product
Contact author(s)
treyquantum @ gmail com
History
2022-11-28: approved
2022-11-28: received
See all versions
Short URL
https://ia.cr/2022/1647
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2022/1647,
      author = {Trey Li},
      title = {Quantum Algorithm for Oracle Subset Product},
      howpublished = {Cryptology {ePrint} Archive, Paper 2022/1647},
      year = {2022},
      url = {https://eprint.iacr.org/2022/1647}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.