Реальные приложения квантовых вычислений (кроме безопасности)

17

Давайте предположим, что мы создали универсальный квантовый компьютер.

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

Я заинтересован в обоих:

  • проблемы, в настоящее время неразрешимые для практического входа,
  • проблемы, которые в настоящее время решаются, но значительное ускорение значительно улучшило бы их удобство использования.
Петр Мигдаль
источник
8
Может быть, это помогает.
aelguindy
Во IIRC возник вопрос о том, какие квантовые компьютеры можно использовать для эффективных вычислений. Вы можете посмотреть на это.
Каве
Является ли это полезно?
Каве
1
@ Кева: Не так много, если честно. Акцент в моем вопросе сделан на приложениях реального мира (не только там, где «ускорение для конкретного алгоритма», но когда ускорение решает конкретную практическую проблему).
Петр Мигдаль

Ответы:

17

Эффективно моделировать квантовую механику.

Тайсон Уильямс
источник
это стандартный ответ / фольклор / ирония / грабли / шутка, и мне интересно, кто его создал. У кого-нибудь есть реальная ссылка? Я подвергаю сомнению это как нетривиально следующее. Qm-вычисления в основном сосредоточены на парных кубит-взаимодействиях (гейтах). Чтобы доказать, что можно эффективно моделировать КМ в целом, кажется, что нужно показать, что вы можете эффективно моделировать все возможные n-мудрые взаимодействия с парными взаимодействиями. не видел это доказано в статье.
ВЗН
2
@vzn: в большинстве физических взаимодействий ограничение на двухчастичные взаимодействия является хорошим приближением, достаточным для моделирования, основанного только на локальных взаимодействиях двух тел, чтобы иметь смысл (взаимодействия, включающие большее количество членов, обычно затухают очень быстро). Таким образом, существование общих взаимодействий n-тела не отменяет идею симуляции.
Марчин Котовски
@vzn У меня нет ссылки на статью, но Скотт Ааронсон сказал это и упомянул об этом в своей недавней статье в Times .
Тайсон Уильямс
2
@vzn, это было оригинальное приложение, когда Ричард Фейнман задумал квантовые вычисления. Это ссылка на статью, где он предложил идею квантовых компьютеров ( springerlink.com/content/t2x8115127841630 ), и вы также можете проверить это ( wisdom.weizmann.ac.il/~naor/COURSE/feynman-simulation.pdf )
Маркос Вильягра
1
@vzn Ответ действителен, но литература по цифровому квантовому моделированию довольно обширна, чтобы просто обобщить ее в комментариях. Я бы порекомендовал открыть новую дискуссию, поскольку тема интересная.
Хуан Бермехо Вега
8

Брассард, Хойер, Моска и Тапп показали, что обобщенный поиск Гровера, называемый усилением амплитуды, может быть использован для получения квадратичного ускорения на большом классе классических эвристик. Интуиция, лежащая в основе их идеи, заключается в том, что классическая эвристика использует случайность для поиска решения данной проблемы, поэтому мы можем использовать амплитудное усиление для поиска в множестве случайных строк той, которая поможет эвристике найти хорошее решение. Это дает квадратичное ускорение во время выполнения алгоритма. См. Раздел 3 документа, указанного выше, для более подробной информации.

Филипп Ламонтань
источник
8

Имитация квантовых систем!

Я заметил, что в другом ответе, в котором упоминалось об этом, было несколько комментариев о том, было ли это правдой, поскольку это неочевидное утверждение. И люди просили ссылки. Вот несколько ссылок.

Оригинальное предложение Фейнмана:

Фейнман Р .: Моделирование физики с помощью компьютеров. Int. Дж. Теор. Phys. 21 (6) (1982) 467–488

Эффективные алгоритмы для всех квантовых систем, определенных «локальными» гамильтонианами. (Ллойд также объясняет, что любая система, соответствующая специальной и общей теории относительности, развивается в соответствии с локальными взаимодействиями.)

Ллойд С .: Универсальные квантовые симуляторы. Science 273 (5278) (1996) 1073–1078

Дальнейшее обобщение на разреженные гамильтонианы, которые являются более общими, чем локальные гамильтонианы:

Ааронов Д., Та-Шма А. Адиабатическая генерация квантового состояния и статистический ноль знаний. В кн .: Учеб. 35th STOC, ACM (2003) 20–29

Дальнейшее чтение:

Берри Д., Ахокас Г., Клеве Р., Сандерс, Б .: Эффективные квантовые алгоритмы для моделирования разреженных гамильтонианов. Commun. Математика Phys. 270 (2) (2007) 359–371

Чайлдс А.М. Квантовая обработка информации в непрерывном времени. Докторская диссертация, Массачусетский технологический институт (2004)

Робин Котари
источник
2

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

Известно, что поиск Гровера может быть использован для полиномиального поиска решения NP-полных задач [1] . Это доказано для 3-SAT в [2] . Некоторые приложения SAT, заимствованные из [3] : проверка эквивалентности схем , автоматическая генерация тестовых шаблонов , проверка моделей с использованием линейной логики времени , планирование в искусственном интеллекте и гаплотипирование в биоинформатике . Хотя я не очень разбираюсь в этих темах, для меня это направление исследований выглядит довольно практичным.

Также существует квантовый алгоритм для оценки NAND-деревьев с полиномиальным ускорением по сравнению с классическими вычислениями [ 8 , 10 , 11 ]. Дерево NAND является примером игрового дерева, более общей структуры данных, используемой для изучения матчей настольных игр, таких как Шахматы и Го. Звучит правдоподобно, что такого рода ускорения могут быть использованы для разработки более мощных программных игроков. Может ли это заинтересовать некоторых разработчиков квантовых видеоигр?

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

Хуан Бермехо Вега
источник
1
Пожалуйста, примите мое приглашение присоединиться к: Quantcomputing.stackexchange.com .
Роб
-6

Я думаю, что вы подняли отличный вопрос на передовых рубежах исследования QM (частично на это указывает отсутствие у вас ответов), но он не был полностью формально определен или воспринят как проблема. вопрос заключается в том, «что именно алгоритмы QM могут эффективно вычислять в любом случае?» и полный ответ не известен и активно преследуется. отчасти это связано с (открытыми вопросами) сложностью классов, связанных с QM.

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

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

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

более сильная идея может состоять в том, что в конечном итоге, когда теория сложности QM будет более детально проработана, NP-полнота каким-то образом будет «аккуратно» в нее вписываться.

мне кажется, что наиболее общее ускорение QM или широко применяемая стратегия, которую я когда-либо видел, это алгоритм Гроверса, потому что так много практического программного обеспечения связано с запросами БД. и в некоторых отношениях все более и более "неструктурированные":

О(N)Ω(N)

ВЗН
источник
3
«Теория сложности QM проработана лучше, полнота NP каким-то образом« вписывается »в нее». Существует хорошо разработанная теория квантовых интерактивных систем доказательства (классы сложности, такие как QMA и т. Д.), Которые обобщают классические классы сложности, такие как NP, PSPACE и т. Д. В этом смысле NP-полнота хорошо вписывается в квантовую теорию сложности. (с другой стороны, я согласен, что в области квантовых алгоритмов отсутствует когезия, но квантовые алгоритмы и квантовая сложность - это разные подполя).
Марчин Котовски
согласились, что есть хорошо определенные классы и иерархии QM, которые отражают классы, не относящиеся к QM, но их отношение к (классическим) «классическим» классам, не относящимся к QM, и, в частности, к NP, в значительной степени является открытым вопросом, как указано.
ВЗН
1
Что вы подразумеваете под "все более неструктурированными базами данных"? База данных выглядит как нечто довольно упорядоченное по определению.
Хуан Бермехо Вега