Шаблон:Use dmy dates
The hidden linear function problem, is a search problem that generalizes the Bernstein–Vazirani problem.[1] In the Bernstein–Vazirani problem, the hidden function is implicitly specified in an oracle; while in the 2D hidden linear function problem (2D HLF), the hidden function is explicitly specified by a matrix and a binary vector. 2D HLF can be solved exactly by a constant-depth quantum circuit restricted to a 2-dimensional grid of qubits using bounded fan-in gates but can't be solved by any sub-exponential size, constant-depth classical circuit using unbounded fan-in AND, OR, and NOT gates.[2]
While Bernstein–Vazirani's problem was designed to prove an oracle separation between complexity classes BQP and BPP, 2D HLF was designed to prove an explicit separation between the circuit classes <math>QNC^{0}</math> and <math>NC^{0}</math> (<math>QNC^{0} \nsubseteq NC^{0}</math>).[1]
2D HLF problem statement
Given <math>A \in \mathbb{F}_2^{n \times n}</math>(an upper- triangular binary matrix of size <math>n \times n</math>) and <math>b \in \mathbb{F}_2^n</math> (a binary vector of length <math>n</math>),
define a function <math>q : \mathbb{F}_2^n \to \mathbb{Z}_4</math>:
- <math>q(x) = (2 x^T A x + b^T x) \bmod 4 = \left(2 \sum_{i,j}A_{i,j} x_i x_j + \sum_i b_i x_i \right) \bmod 4 , </math>
and
- <math>\mathcal{L}_q = \Big\{x \in \mathbb{F}_2^n : q(x \oplus y) = (q(x) + q(y)) \bmod 4 ~~ \forall y \in \mathbb{F}_2^n \Big\}.</math>
There exists a <math>z \in \mathbb{F}_2^n</math> such that
- <math>q(x) = 2 z^T x ~~\forall x \in \mathcal{L}_q.</math>
Find <math>z</math>.[1]
2D HLF algorithm
With 3 registers; the first holding <math>A</math>, the second containing <math>b</math> and the third carrying an <math>n</math>-qubit state, the circuit has controlled gates which implement
<math>U_q = \prod_{1 < i < j < n} CZ_{ij}^{A_{ij}} \cdot \bigotimes_{j=1}^n S_j^{b_j}</math> from the first two registers to the third.
This problem can be solved by a quantum circuit, <math>H^{\otimes n} U_q H^{\otimes n} \mid 0^n \rangle</math>, where H is the Hadamard gate, S is the S gate and CZ is CZ gate. It is solved by this circuit because with <math>p(z) = \left| \langle z | H^{\otimes n} U_q H ^ {\otimes n} | 0^n \rangle \right|^2</math>, <math>p(z)>0</math> iff <math>z</math> is a solution.[1]
References
Шаблон:Reflist
External links
Шаблон:Quantum computing
Партнерские ресурсы |
---|
Криптовалюты |
|
---|
Магазины |
|
---|
Хостинг |
|
---|
Разное |
- Викиум - Онлайн-тренажер для мозга
- Like Центр - Центр поддержки и развития предпринимательства.
- Gamersbay - лучший магазин по бустингу для World of Warcraft.
- Ноотропы OmniMind N°1 - Усиливает мозговую активность. Повышает мотивацию. Улучшает память.
- Санкт-Петербургская школа телевидения - это федеральная сеть образовательных центров, которая имеет филиалы в 37 городах России.
- Lingualeo.com — интерактивный онлайн-сервис для изучения и практики английского языка в увлекательной игровой форме.
- Junyschool (Джунискул) – международная школа программирования и дизайна для детей и подростков от 5 до 17 лет, где ученики осваивают компьютерную грамотность, развивают алгоритмическое и креативное мышление, изучают основы программирования и компьютерной графики, создают собственные проекты: игры, сайты, программы, приложения, анимации, 3D-модели, монтируют видео.
- Умназия - Интерактивные онлайн-курсы и тренажеры для развития мышления детей 6-13 лет
- SkillBox - это один из лидеров российского рынка онлайн-образования. Среди партнеров Skillbox ведущий разработчик сервисного дизайна AIC, медиа-компания Yoola, первое и самое крупное русскоязычное аналитическое агентство Tagline, онлайн-школа дизайна и иллюстрации Bang! Bang! Education, оператор PR-рынка PACO, студия рисования Draw&Go, агентство performance-маркетинга Ingate, scrum-студия Sibirix, имидж-лаборатория Персона.
- «Нетология» — это университет по подготовке и дополнительному обучению специалистов в области интернет-маркетинга, управления проектами и продуктами, дизайна, Data Science и разработки. В рамках Нетологии студенты получают ценные теоретические знания от лучших экспертов Рунета, выполняют практические задания на отработку полученных навыков, общаются с экспертами и единомышленниками. Познакомиться со всеми продуктами подробнее можно на сайте https://netology.ru, линейка курсов и профессий постоянно обновляется.
- StudyBay Brazil – это онлайн биржа для португалоговорящих студентов и авторов! Студент получает уникальную работу любого уровня сложности и больше свободного времени, в то время как у автора появляется дополнительный заработок и бесценный опыт.
- Автор24 — самая большая в России площадка по написанию учебных работ: контрольные и курсовые работы, дипломы, рефераты, решение задач, отчеты по практике, а так же любой другой вид работы. Сервис сотрудничает с более 70 000 авторов. Более 1 000 000 работ уже выполнено.
- StudyBay – это онлайн биржа для англоязычных студентов и авторов! Студент получает уникальную работу любого уровня сложности и больше свободного времени, в то время как у автора появляется дополнительный заработок и бесценный опыт.
|
---|
- ↑ 1,0 1,1 1,2 1,3 Ошибка цитирования Неверный тег
<ref>
; для сносок Bravyi-Gosset-König_2018
не указан текст
- ↑ Ошибка цитирования Неверный тег
<ref>
; для сносок Watts-Kothari-Schaeffer-Tal_2019
не указан текст