Книга: Программируя Вселенную. Квантовый компьютер и будущее науки

Поиск

Поиск

Разложение на множители – не единственная сложная проблема, которую в принципе могут эффективно решить квантовые компьютеры. В 1996 г. Лов Гроувер из Bell Laboratories показал, что квантовые компьютеры совершают операции поиска эффективнее, чем классические. Предположим, вы забыли, в какой из своих четырех карманов положили свой бумажник. Сначала вы проверяете один карман, потом другой. В худшем случае вам придется проверить все четыре кармана, а в среднем – два. Но предположим, что вы можете использовать квантовый параллелизм, то есть проверить все карманы сразу. Гроувер показал: чтобы найти бумажник, нужно произвести операцию квантового поиска всего два раза.

Конечно, алгоритм Гроувера работает и при количестве вариантов больше четырех. Если вы ищете нечто, что может находиться в 100 возможных местах, то чтобы найти его, достаточно выполнить квантовый поиск всего 10 раз. При классическом поиске вам придется выполнить в среднем 50 операций. Если вы ищете что-то в миллионе возможных мест, нужно будет выполнить квантовый поиск всего 1000 раз вместо полумиллиона классических поисковых операций. В общем, количество операций квантового поиска, необходимых для того, чтобы найти искомое, составляет квадратный корень из количества мест, в которых оно может находиться.

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

Оглавление книги