Алгоритм Гровера для Квантового компьютера

[Curious]

Помогите разобраться, что же это за алгоритм. Прочитал, что он позволяет производить поиск среди неструктурированных данных, например, наити имя владельца по телефонному справочнику, составленному в алфавитном порядке по именам. Постановка задачи понятна, а дальше - одни вопросы. Во первых, в описании алгоритма ничего не сказано (ну или я не увидел), как же, собственно говоря, эта база туда вводится. Если мы решаем задачу однократно, то уже в процессе ввода мы легко получим имя, значит, идёт речь о многократных запросах, то есть всё же надо сначала ввести базу (справочник), а потом подпихивать на вход телефоны (числа) и получать порядковые номера записей в базе (тоже числа). Но тогда нужно описать два процесса: ввод базы и обработка запроса. Но при вводе базу можно полностью или частично структурировать, чтобы облегчить поиск, ну и выбрать оптимальное решение с учётом этих действий. Ведь даже на обычном компьютере можно решить эту задачу за один цикл, если, например, при длине телефонного номера в 7 цифр предусмотреть память в 10 Мслов (это мелочь) и использовать её, адресую по номерам телефонов, записывая туда ссылки на имена (или порядковые номера владельцев). Нетрудно представить себе , что вместо телефона имеем признак, например в 100 бит, и тогда такую память уже не взять. Вот тут-то и напрашивается квантовый компьютер, который, как декларируется, на 100 кубитах будет иметь 2^100 состояний, то есть, можно надеяться, что это и будет аналог той самой памяти, как рассмотрено выше. И тут в полный рост встаёт как раз две задачи (алгоритма): ввод базы и обработка запроса. А что-же делает Гровер, какую задачу решает? Ничего не ясно, одно шаманство с матрицами, и только. А, казалось бы, тут широкое поле для целого семейства алгоритмов на эту тему: удаление записи из базы, выбор по наибольшему(наименьшему) номеру (телефона), имеющемуся в динамической (добавляем, удаляем) базе, поиск множественных ответов по маскированным признакам (отдельным цифрам телефона), то есть создание ассоциативной памяти. Всё это можно делать и на обычном компьютере, но ограниченно, а чего бы дал, в этом случае, квантовый?
Удалось найти и скачать модель алгоритма Гровера для Mapple, только вот Mapple рабочего не скачать. А нельзя ли продемонстрировать этот алгоритм на доступном и понятном Маткаде, например, хотя бы для 4-ёх битовых номеров телефонов и, скажем, 10 клиентов? Кстати, а какой ответ даст Гровер, если запрашиваемого телефона в базе нет? И хотелось бы, чтобы с особой тщательностью и наглядностью было показано, что же всё-таки делает Гровер, ну а заодно, и как.
Ну а потом и Шором можно заняться.
С уважением, Сurious.

[AlexDem]

Есть книга: Китаев, Шень, Вялый "Классические и квантовые вычисления" - попробуйте разобраться, возможно, что-то станет понятней. Вроде хорошо написано, хотя я не во всём разобрался (но не очень много с ней сидел).

[Curious]

Спасибо за совет. Скачал и смотрел я эту книгу, всё-таки книга эта не популярная, требует глубокого погружения в тему, что для неспециалиста, вроде меня, вряд-ли приемлемо. Есть там и про Гровера. Вообще, про этого Гровера то больше всего информации в инете и есть (я много чего посмотрел), вроде как самый простой из квантовых алгоритмов, и задача то вроде понятная - поиск данных. Но все как сговорились, пишут как-бы с середины, не объяснив (на мой взгляд) самое начало. Видимо, оно для всех является очевидным, но, увы, не для меня. Я задал, казалось бы, самые простые и очевидные вопросы, но не могу найти ответы. Ну например, сколько надо кубит для работы с базой заданного объёма, а главное, как туда эта база попадает (то есть, как я понимаю, должна происходить соответствующая настройка кубитов. Может, это и есть Гровер? Но тогда как обрабатываются запросы?). Исходно, вроде как, считается, что база и запросы формируются на обычном компьютере, а обработка запросов происходит в специализированной квантовой среде, в общем вроде как всё понятно, но чуть подробнее - и тупик. Про линейную алгебру и квантовую механику имею представления, но в скромном объёме (стандартные курсы физики и математики обычного тех. вуза).
И про ассоциативную память бы добавил: целое направление когда-то было - ассоциативные компьютеры на основе ассоциативной памяти, да загнило, потому-что реализовать эту память на обыных элементах в нужном объёме вряд-ли возможно. А тут вроде как всё для этого есть..
Был бы признателен за любые комментарии.

[Dandan]

Curious писал(а):

...Но все как сговорились, пишут как-бы с середины, не объяснив (на мой взгляд) самое начало...

В самом начале нужно чётко знать принцип действия квантового компьютера. Без этого разбираться с алгоритмами не имеет смысла.

[AlexDem]

Curious в сообщении #192124 писал(а):

Но все как сговорились, пишут как-бы с середины, не объяснив (на мой взгляд) самое начало.

Для начала я бы рекомендовал статью Менского "Квантовая механика. Новые эксперименты, новые приложения и новые формулировки старых вопросов", только про мультимиры у него, по-моему, читать не стоит. Там в п. 2.2.3 есть и про квантовый компьютер - очень кратко, но зато Вы сможете убедиться, что ошибаетесь (если я Вас верно понял), например, вот здесь:

Curious в сообщении #191912 писал(а):

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

Классический компьютер на 100 битах тоже имеет $2^{100}$ возможных состояний, но в квантовом компьютере все они реализуются одновременно. Судя по тому, что в той моей книге пишется $|0^n>$ (то есть $|0>|0>|0>.....|0>$ $n$ раз), база для хранения требует столько же кубит, сколько и бит в обычном компьютере. Это в обозримом будущем вряд ли осуществимо.

Curious в сообщении #192124 писал(а):

Исходно, вроде как, считается, что база и запросы формируются на обычном компьютере, а обработка запросов происходит в специализированной квантовой среде, в общем вроде как всё понятно, но чуть подробнее - и тупик.

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

Добавлено спустя 28 минут 58 секунд:

AlexDem в сообщении #192138 писал(а):

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

А, пожалуй, наврал . Ведь там скорее всего вся база кодируется суперпозицией состояний - если есть номера $|1234567>$ и $|2345678>$, то эту базу можно закодировать как $1/\sqrt 2 * (|1234567> + |2345678>)$. Наверное, так - я не разбирался с этим просто.

[ha]

Алгоритм Гровера делает следующее. На вход подается классический алгоритм вычисления функции f (который затем преобразуется в квантовый), на выходе алгоритм выдает набор аргументов, на котором функция равна единице. При этом для функции от n битов нужно лишь O(2^{n/2}) вызовов функции.

[AlexNew]

Dandan писал(а):

В самом начале нужно чётко знать принцип действия квантового компьютера. Без этого разбираться с алгоритмами не имеет смысла.

и в чем же принцип?