Вопросы с тегом «grovers-algorithm»

Алгоритм поиска Гровера - это алгоритм, который может выполнять поиск в порядке извлечения квадратного корня из входного размера. Это доказуемое ускорение по сравнению с лучшим классическим алгоритмом, для выполнения поиска которого требуется время порядка N.

27
Есть ли объяснение непрофессионала, почему работает алгоритм Гровера?

Этот пост от Скотта Ааронсона - очень полезное и простое объяснение алгоритма Шора . Мне интересно, есть ли такое объяснение для второго наиболее известного квантового алгоритма: алгоритм Гровера для поиска в неупорядоченной базе данных размера в O ( √O ( n )O(n)O(n)времяO ( n--√)O(n)O(\sqrt{n}) В...

25
Был ли действительно прорыв в квантовых алгоритмах со времен Гровера и Шора?

(Извините за несколько дилетантский вопрос) Я изучал квантовые вычисления с 2004 по 2007 год, но с тех пор я потерял поле зрения. В то время было много ажиотажа и разговоров о том, что КК потенциально может решить все виды проблем, превосходя классические компьютеры, но на практике было только два...

19
Могут ли адиабатические квантовые вычисления быть быстрее, чем алгоритм Гровера?

Было доказано, что адиабатические квантовые вычисления эквивалентны «стандартным» или квантовым вычислениям модели затвора. Адиабатические вычисления, однако, показывают перспективы для задач оптимизации, где цель состоит в том, чтобы минимизировать (или максимизировать) функцию, которая каким-то...

15
Как работает диффузионный оператор Гровера и почему он оптимален?

В этом ответе объясняется алгоритм Гровера. Объяснение указывает, что алгоритм в значительной степени опирается на оператор диффузии Гровера , но не дает подробных сведений о внутренней работе этого оператора. Вкратце, оператор диффузии Гровера создает «инверсию относительно среднего», чтобы...

15
Алгоритм Гровера: где список?

Используется алгоритм Гровера, среди прочего, искать нужный пункт yy\mathbf{y} в неупорядоченном списке элементов [x0,x1,...,xn−1][x0,x1,...,xn−1][\mathbf{x}_0, \mathbf{x}_1, ..., \mathbf{x}_{n-1}] длины nnn . Несмотря на то, что здесь есть много вопросов по этой теме, я все еще упускаю суть. Поиск...

14
Какие приложения есть в алгоритме поиска Grover?

Об алгоритме поиска Гровера обычно говорят в терминах поиска помеченной записи в несортированной базе данных. Это естественный формализм, который позволяет применять его непосредственно к поиску решений проблем NP (где хорошее решение легко распознается). Мне было интересно узнать о других...

13
Алгоритм Гровера: пример из реальной жизни?

Я довольно озадачен тем, как алгоритм Гровера может быть использован на практике, и я хотел бы попросить помощи в разъяснении на примере. Давайте предположим, что база данных N=8N=8N=8 элементов содержит цвета Красный, Оранжевый, Желтый, Зеленый, Голубой, Синий, Индиго и Фиолетовый, и не...

12
Алгоритм Гровера и его связь с классами сложности?

Я запутался в алгоритме Гровера и его связи с классами сложности. Алгоритм Гровера находит и элемент в базе данных с (таким, что ) элементов с обращениями к оракулу.kkkN=2nN=2nN=2^nf(k)=1f(k)=1f(k)=1∼N−−√=2n/2∼N=2n/2\sim \sqrt{N}=2^{n/2} Итак, у нас есть следующая проблема: Проблема: Найти в базе...

12
Как алгоритм Гровера применяется к базе данных?

Вопрос Я хочу использовать алгоритм Гровера для поиска в несортированной базе данных элемента . Теперь возникает вопрос, как я могу инициализировать индекс и значение базы данных с кубитами?Иксxx пример Допустим, у меня есть кубита. Таким образом, классических значений могут быть...

10
Как алгоритм Гровера используется для оценки среднего и медианы набора чисел?

На странице Википедии об алгоритме Гровера упоминается, что: «Алгоритм Гровера также можно использовать для оценки среднего и медианы набора чисел» До сих пор я знал только, как это можно использовать для поиска в базе данных. Но не уверен, как реализовать эту технику для оценки среднего и медианы...

10
Почему оракуловый кубит необходим в алгоритме Гровера?

Меня немного смущает необходимость оракула в алгоритме Гровера. Мой вопрос: зависит ли от того, как вы реализуете свой оракул, нужен ли вам оракул-кубит или нет? Или это какая-то причина для оракула? (например, существуют некоторые проблемы, которые невозможно решить без оракула-кубита, или проще...

10
Реализация алгоритма Гровера в Oracle Q с использованием трех кубитов

Я пытаюсь привыкнуть к IBM Q путем реализации алгоритма Гровера с тремя кубитами, но с трудом реализую оракула. Не могли бы вы показать, как это сделать, или предложить хорошие ресурсы, чтобы привыкнуть к схемотехнике IBM Q? Я хочу пометить одно произвольное состояние, щелкнув его знак, как и...

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

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

9
Алгоритм Гровера: что вводить в Oracle?

Я запутался в том, что вводить в Oracle в алгоритме Гровера. Разве нам не нужно вводить то, что мы ищем, и где найти то, что мы ищем в Oracle, в дополнение к суперпозиционным квантовым состояниям? Например, предположим, что у нас есть список имен людей {"Алиса", "Боб", "Кори", "Дио"}, и мы хотим...