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

10

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

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

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

kelalaka
источник

Ответы:

6

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

Hn(In2|00|n)HnUS,
(H|0)nΘ(N)In2n×2n

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

(IkH(nk))Ik(Ink2|00|(nk))(IkH(nk))US
|x(H|0)(nk)O(N/K)K

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

DaftWullie
источник
но если вы сделаете это, сравнение с классическим исполнением теряет смысл, не так ли? В конце концов, вы также можете ускорить классический поиск, запустив операцию, которая проверяет, является ли данный целевым объектом параллельно для всех входов. Это явно требует дополнительных предположений о доступных ресурсах, но таких же предположений, которые делаются в вашем аргументеx
GLS 25.10-18
1
N уходит в бесконечность, но Kне. Ваша проблема становится больше, но ваших ресурсов остается мало.
Хусейн
1
Этот ответ правильный (хотя он может быть неоптимальным, как предупреждает DaftWullie). Это то же самое отношение к распараллеливанию, что и в классической сложности схемы. Если вы хотите ускорить процесс из-за распараллеливания, посмотрите на глубину контура (потому что координация нескольких процессов не приведет к сокращению общей работы). Даже не имеет значения , постоянна ли - либо вы заинтересованы в улучшении глубины от распараллеливания, либо нет. Как и в случае самих квантовых вычислений, простое использование большего количества компьютеров не может волшебным образом сделать все быстро! K
Ниль де Бодрап,
3

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

Вы согласны с тем, что нам нужны операции для непараллельного случая. Скажем, у нас есть два узла, и мы разделяем список из N элементов на два списка размером . Поиск в подсписках занимает около .NN1,N2N1,N2

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

N=N1+N2N1+N2

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

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

Cnada
источник
2
Для N1 = N2 это все еще неравенство: sqrt (2) * sqrt (N1) <2 * sqrt (N1)
Мария Михайлова
О, действительно. В моей голове я подумал $ \ sqrt {a b} = \ sqrt {a} \ sqrt {b} $. Я должен перестать отвечать на ответы здесь в полночь и когда устал. Спасибо что подметил это.
cnada
3
@cnada: Есть по крайней мере два разных понятия сложности, оба из которых имеют отношение к ускорению. Один - это сложность размера, а второй - сложность глубины. Если не указано иное, мы часто предпочитаем учитывать сложность размеров, но сложность глубины по-прежнему представляет большой интерес для квантовых вычислительных сложностей, например, в MBQC [arXiv: quant-ph / 0301052 , arXiv: 0704.1736 ] и недавних результатах на безусловное разделение по глубине [arXiv: 1704.00690 ].
Ниль де Бодрап,
@ NieldeBeaudrap Я думал, что люди смотрят больше на глубину сложности. Но для Гровера размер и глубина сложности примерно одинаковы. Это квадратичный размер задачи (обычно рассматривается как размер списка из N элементов). Как вы думаете, мой подход здесь не так?
cnada
2
Вы не говорите ничего плохого , я просто указываю на то, что вы чрезмерно подчеркиваете сложность размера, а не реально извлекаете выгоду из глубины сложности. Не много интересного произойдет, если вы только делаетеkO(1) параллельные процессы Гровера, но, как показывает ответ DaftWullie (и учитывая классическую постобработку), сложность глубины исходит из N в log(k)N/k за k(N)Ω(1) параллельные процессы Гровера, что является улучшением в k/log(k)(логарифмический коэффициент определяется тем, что какой-либо процесс нашел решение).
Ниль де Боудрап,