### Quantum Algorithm for Oracle Subset Product

##### Abstract

In 1993 Bernstein and Vazirani proposed a quantum algorithm for the Bernstein-Vazirani problem, which is given oracle access to the function $f(a_1,\dots,a_n) = a_1x_1+\cdots + a_nx_n \pmod 2$ with respect to a secret string $x = x_1\dots x_n \in \{0,1\}^n$, where $a_1,\dots,a_n \in \{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(a_1,\dots,a_n) = a_1^{x_1}\cdots a_n^{x_n}$ with respect to a secret string $x = x_1\dots x_n\in\{0,1\}^n$, where $a_1,\dots,a_n\in \mathbb Z$, 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.

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

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},
note = {\url{https://eprint.iacr.org/2022/1647}},
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.