Почему и как квантовый компьютер быстрее обычного?

37

В настоящее время я читаю книгу (и много википедии) о квантовой физике, и мне еще предстоит понять, как квантовый компьютер может быть быстрее, чем компьютеры, которые мы имеем сегодня.

Как квантовый компьютер может решить проблему в субэкспоненциальном времени, которую классический компьютер может решить только в экспоненциальном времени?

Том
источник
3
Я нашел это видео из Veritasium, с помощью A / Prof Андреа Морелло , чрезвычайно полезным для объяснения этого. После объяснения того, как работают квантовые вычисления, он дает хорошее объяснение того, почему квантовые вычисления никогда не заменят современные вычисления и в каких случаях квантовые вычисления медленнее / быстрее.
Гуннар
что за книга? Прошу процитировать это. см. также, как измерить вычислительную мощность процессора
QM

Ответы:

36

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

Я рекомендую прочитать «Пределы кванта » Скотта Ааронсона: это короткая популярная статья, объясняющая, чего можно ожидать от квантовых компьютеров.

Алексей романов
источник
3
Что вы подразумеваете под: « Квантовый компьютер сам по себе не быстрее », особенно перед тем, как сказать, что с правильными алгоритмами эта модель может решить некоторые проблемы асимптотически быстрее, чем классические модели (и, конечно, всегда, по крайней мере, так быстро )? Или вы просто говорите, что скорость вычислений является свойством алгоритма, а не вычислительной модели. Но тогда я думаю, что эта концепция может быть распространена на вычислительные модели. Или есть причина, почему это невозможно.
Babou
6

Это открытая проблема, которая требует передовых исследований, будут ли квантовые алгоритмы работать быстрее, чем «классические» алгоритмы как на теоретическом, так и на прикладном уровнях. в теории сложности это отражено в вопросе, например, BQP =? P т. Е. Эквивалентен ли класс «P» квантовых вычислений классическому классу P (полиномиальному времени), и есть много других связанных с этим открытых вопросов.

Существует один очень интригующий и значимый элемент данных: отмеченный наградами алгоритм Шорса учитывает числа в P-квантовом времени, но до сих пор неизвестно, существует ли P-time классический алгоритм факторинга.

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

единственный квантовый (ые) компьютер (ы), когда-либо созданный на сегодняшний день, - это системы Dwave, и в настоящее время он подвергается интенсивному научному анализу и спорам относительно его реальных квантовых эффектов и производительности; это очень дорого и в основном не превосходит настольный компьютер, когда классический код полностью (человек / рука) оптимизирован. однако, можно справедливо заявить, что никакие другие корпоративные, правительственные или университетские исследовательские организации, по-видимому, пока не достигли своего уровня прикладного / технического / технического прогресса.

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

ВЗН
источник
1

У меня есть доказательство того, что даже квантовая власть имеет свои пределы.

Квантовым компьютерам очень трудно даже получить килобит кубитов. Но даже если они только туда доберутся, это довольно сильно.

16384 кубита дадут 128 пространственных измерений за 128 временных шагов, полный исчерпывающий поиск, что удивительно, 100 временных шагов 100 вероятностных деревьев !!! но не ожидайте больше, чем это количество для кванта в ближайшем будущем.

Магнус Вуттон
источник
1
Это больше похоже на комментарий, чем на ответ.
xskxzr
Как это отвечает на поставленный вопрос? Это имеет пределы, хорошо, но вопрос был о показательном времени.
Зло
0

Квантовая система - это система, которая существует в квантовом (ых) состоянии (ях) с различной вероятностью, определяемой ограничениями окружающей среды. Предполагая, что квантовый компьютер содержит все состояния n-битной квантовой системы, извлечение одного из этих состояний приводит к коллапсу системы в одно из состояний. Это похоже на хеш-функцию, использующую O (1) для поиска сегмента без итерации. Необходимы две вещи: квантовое хранение n-битных систем и хеш-подобная функция для коллапса необходимого состояния. Ограничения играют роль различных хеш-функций для свертывания n-битной системы в требуемое состояние.

criollo14
источник
-1

Подумайте об этом следующим образом: есть проблемы, которые могут быть решены путем решения целого ряда отдельных под-случаев [пример: факторинг с помощью пробного деления]. Эти проблемы занимают много времени, если нужно решать под-дела один за другим. Их можно решить гораздо быстрее, если предоставить достаточно оборудования для параллельного решения всех подслучаев, но это непрактично, поскольку количество необходимого оборудования увеличивается с увеличением размера проблемы. Квантовые вычисления используют функцию суперпозиции состояний в квантовой механике для симуляции предоставления достаточного количества аппаратного обеспечения - т.е. каждое состояние в суперпозиции является «машиной» для одного из подслучаев. Обратите внимание, что это моделирование выполняется не программным обеспечением, а самой природой.

PMar
источник
3
Квантовые вычисления - это не то же самое, что параллельный исчерпывающий поиск. Это немного сложнее, чем это.
Юваль Фильмус