Можем ли мы ускорить алгоритм Гровера, запустив параллельные процессы?

В классических вычислениях мы можем запустить поиск ключей (например, AES), запустив как можно больше параллельных вычислительных узлов.

Понятно, что мы можем запустить и многие алгоритмы Гровера.

Мой вопрос ; Можно ли ускорить использование более одного алгоритма Гровера, как в классических вычислениях?

classical-computing grovers-algorithm cryptography kelalaka
источник

Ответы:

Безусловно! Представьте, что у вас есть копий поискового оракула который вы можете использовать. Обычно вы выполняете поиск, повторяя действие начиная с начального состояния . Это занимает время . (Я использую для обозначения матрицы тождественности .) $K=2^k$ $U_S$

H^{\otimes n} (I_{n} - 2 | 0 ⟩ ⟨ 0 |^{\otimes n}) H^{\otimes n} U_{S},

$H^{\otimes n}(\mathbb{I}_n-2|0\rangle\langle 0|^{\otimes n})H^{\otimes n}U_S,$

(H | 0 ⟩)^{\otimes n}

$(H|0\rangle)^{\otimes n}$

Θ (\sqrt{N})

$\Theta(\sqrt{N})$

I_{n}

$\mathbb{I}_n$

2^{n} \times 2^{n}

$2^n\times 2^n$

Вы можете заменить это на параллельных копий, каждая из которых проиндексирована символом , используя и начиная с состояния Время, необходимое для их выполнения, будет сокращено до , за счет чего требуется в раз больше места. $2^k$ $x\in\{0,1\}^k$

(I_{k} \otimes H^{\otimes (n - k)}) I_{k} \otimes (I_{n - k} - 2 | 0 ⟩ ⟨ 0 |^{\otimes (n - k)}) (I_{k} \otimes H^{\otimes (n - k)}) U_{S}

$\left(\mathbb{I}_k\otimes H^{\otimes (n-k)}\right)\mathbb{I}_k\otimes(\mathbb{I}_{n-k}-2|0\rangle\langle 0|^{\otimes (n-k)})\left(\mathbb{I}_k\otimes H^{\otimes (n-k)}\right)U_S$

| x ⟩ (H | 0 ⟩)^{\otimes (n - k)}

$|x\rangle(H|0\rangle)^{\otimes(n-k)}$

O (\sqrt{N / K})

$O(\sqrt{N/K})$

K

$K$

В смысле масштабирования можно считать это неуместным результатом. Если у вас есть фиксированное число оракулов, , то вы получаете фиксированное ( ) улучшение (точно так же, как если у вас параллельных классических ядер, лучшее улучшение, которое вы можете получить, это коэффициент ), и это не меняет масштабирование. Но это меняет фундаментальное время работы. Мы знаем, что алгоритм Гровера является абсолютно оптимальным. Это занимает минимально возможное время с одним оракулом. Таким образом, зная , что вы получите улучшение времени полезно в отношении этого теста определенного времени работы при определенном значении . $K$ $\sqrt{K}$ $K$ $K$ $\sqrt{K}$ $N$

DaftWullie
источник

но если вы сделаете это, сравнение с классическим исполнением теряет смысл, не так ли? В конце концов, вы также можете ускорить классический поиск, запустив операцию, которая проверяет, является ли данный целевым объектом параллельно для всех входов. Это явно требует дополнительных предположений о доступных ресурсах, но таких же предположений, которые делаются в вашем аргументе

x

$x$

GLS 25.10-18

N

$N$ уходит в бесконечность, но

K

$K$ не. Ваша проблема становится больше, но ваших ресурсов остается мало.

Хусейн

Этот ответ правильный (хотя он может быть неоптимальным, как предупреждает DaftWullie). Это то же самое отношение к распараллеливанию, что и в классической сложности схемы. Если вы хотите ускорить процесс из-за распараллеливания, посмотрите на глубину контура (потому что координация нескольких процессов не приведет к сокращению общей работы). Даже не имеет значения , постоянна ли - либо вы заинтересованы в улучшении глубины от распараллеливания, либо нет. Как и в случае самих квантовых вычислений, простое использование большего количества компьютеров не может волшебным образом сделать все быстро!

K

$K$

Ниль де Бодрап,

В некотором смысле, если бы мы делали это параллельно на разных узлах, вы бы сэкономили время для работы. Но если мы говорим о сложности (это то, что мы обычно называем ускорением), нам нужно немного проанализировать.

Вы согласны с тем, что нам нужны операции для непараллельного случая. Скажем, у нас есть два узла, и мы разделяем список из N элементов на два списка размером . Поиск в подсписках занимает около . $\sqrt{N}$ $N_1,N_2$ $\sqrt{N_1},\sqrt{N_2}$

Однако у нас есть

\sqrt{N} = \sqrt{N_{1} + N_{2}} \leq \sqrt{N_{1}} + \sqrt{N_{2}}

$\sqrt{N} = \sqrt{N_1+N_2} \le \sqrt{N_1} + \sqrt{N_2}$

И вам все равно нужно будет проверить, какой выход из того, что возвращается параллельными процессами, является тем, который вы ищете. Это добавляет константу сложности, поэтому мы обычно скрываем ее в обозначении $O$

Тем не менее, это все равно будет интересно, особенно если нам придется кластеризовать аппаратное обеспечение, потому что мы ограничены в количестве кубитов или других ограничений.

Cnada
источник

Для N1 = N2 это все еще неравенство: sqrt (2) * sqrt (N1) <2 * sqrt (N1)

Мария Михайлова

О, действительно. В моей голове я подумал $ \ sqrt {a b} = \ sqrt {a} \ sqrt {b} $. Я должен перестать отвечать на ответы здесь в полночь и когда устал. Спасибо что подметил это.

cnada

@cnada: Есть по крайней мере два разных понятия сложности, оба из которых имеют отношение к ускорению. Один - это сложность размера, а второй - сложность глубины. Если не указано иное, мы часто предпочитаем учитывать сложность размеров, но сложность глубины по-прежнему представляет большой интерес для квантовых вычислительных сложностей, например, в MBQC [arXiv: quant-ph / 0301052 , arXiv: 0704.1736 ] и недавних результатах на безусловное разделение по глубине [arXiv: 1704.00690 ].

Ниль де Бодрап,

@ NieldeBeaudrap Я думал, что люди смотрят больше на глубину сложности. Но для Гровера размер и глубина сложности примерно одинаковы. Это квадратичный размер задачи (обычно рассматривается как размер списка из N элементов). Как вы думаете, мой подход здесь не так?

cnada

Вы не говорите ничего плохого , я просто указываю на то, что вы чрезмерно подчеркиваете сложность размера, а не реально извлекаете выгоду из глубины сложности. Не много интересного произойдет, если вы только делаете

k \in O (1)

$k \in O(1)$ параллельные процессы Гровера, но, как показывает ответ DaftWullie (и учитывая классическую постобработку), сложность глубины исходит из

\sqrt{N}

$\sqrt N$ в

\log (k) \sqrt{N / k}

$\log(k) \sqrt{N/k}$ за

k (N) \in Ω (1)

$k(N) \in \Omega(1)$ параллельные процессы Гровера, что является улучшением в

\sqrt{k} / \log (k)

$\sqrt{k}/\!\!\;\log(k)$ (логарифмический коэффициент определяется тем, что какой-либо процесс нашел решение).

Ниль де Боудрап,