Задача о скрытой линейной функции

---

Проблема скрытой линейной функции — это задача поиска , которая обобщает проблему Бернштейна — Вазирани . ^[1] В задаче Бернштейна–Вазирани скрытая функция неявно указана в оракуле ; в то время как в задаче двумерной скрытой линейной функции (2D HLF) скрытая функция явно задается матрицей и двоичным вектором. 2D HLF может быть точно решена квантовой схемой постоянной глубины, ограниченной двумерной сеткой кубитов с использованием ограниченных веерных вентилей, но не может быть решена любой субэкспоненциальной классической схемой постоянной глубины с использованием неограниченного веера. в И , ИЛИ, а НЕ ворота. ^[2] В то время как проблема Бернштейна-Вазирани была разработана для доказательства разделения оракулов между классами сложности BQP и BPP , 2D HLF была разработана для доказательства явного разделения между классами схем и ( ). ^[1]${\ Displaystyle QNC ^ {0}}$ ${\ Displaystyle NC ^ {0}}$${\ displaystyle QNC ^ {0} \ nsubseteq NC ^ {0}}$

Даны ( верхнетреугольная бинарная матрица размера ) и ( бинарный вектор длины ),${\ Displaystyle А \ в \ mathbb {F} _ {2} ^ {п \ раз п}}$ ${\ Displaystyle п \ раз п}$${\ Displaystyle б \ в \ mathbb {F} _ {2} ^ {п}}$${\ Displaystyle п}$

определить функцию :${\ Displaystyle д: \ mathbb {F} _ {2} ^ {п} \ к \ mathbb {Z} _ {4}}$

Существует такое , что${\ Displaystyle г \ в \ mathbb {F} _ {2} ^ {п}}$

С 3 регистрами; первый удерживает , второй содержит и третий несет состояние -кубита, схема имеет управляемые вентили , которые реализуют переход от первых двух регистров к третьему.${\ Displaystyle А}$${\ Displaystyle б}$${\ Displaystyle п}$${\ displaystyle U_ {q} = \ prod _ {1 <i <j <n} CZ_ {ij} ^ {A_ {ij}} \ cdot \ bigotimes _ {j = 1} ^ {n} S_ {j} ^ {б_{к}}}$

---