Welcome to the resource topic for
**2022/1647**

**Title:**

Quantum Algorithm for Oracle Subset Product

**Authors:**
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(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.

**ePrint:**
https://eprint.iacr.org/2022/1647

See all topics related to this paper.

Feel free to post resources that are related to this paper below.

**Example resources include:**
implementations, explanation materials, talks, slides, links to previous discussions on other websites.

For more information, see the rules for Resource Topics .