Есть ли доказательства того, что квантовые компьютеры более эффективны, чем классические компьютеры?

11

Алгоритм Шора часто используется в качестве аргумента. Он может решить проблему факторизации быстрее, чем любой известный алгоритм для классических компьютеров. Тем не менее, у нас нет доказательств того, что классические компьютеры также не могут эффективно вычислять целые числа.

Есть ли какие-либо доказательства того, что квантовые компьютеры могут решить некоторые проблемы быстрее, чем классические компьютеры?

MaiaVictor
источник
часть этого формально фиксируется в разделении классов открытой сложности, таких как BPP =? BQP (1-я классическая, 2-я ориентированная на QM). Существует также проблема реализации , заключающаяся в том, что не известно (в отличие от классических машин), является ли QM действительно физически осуществимым. и т. д. ... может приготовить часть этого в ответ.
vzn
Близко связаны: почему и как квантовый компьютер быстрее, чем обычный компьютер?
Жиль "ТАК - перестань быть злым"

Ответы:

18

NO(N)Ω(N)

Ран Г.
источник
4
f:{0,1}n{0,1}02n1+1
12
«разработка базы данных» - я думаю, что вы, возможно, воспринимаете фразу «интеллектуальный анализ данных» слишком буквально. :-)
Дэвид Ричерби
1
@DavidRicherby, черт побери, автозамена? (;
Ран Г.
3
@ariel Я думаю, это заслуживает дополнительного ответа! почему бы тебе не добавить это? (Вы также можете упомянуть, что это дает идеи для алгоритма Симона, который, в свою очередь, относится к алгоритму Шора)
Ран Г.
«Любое классическое решение, которое успешно с высокой вероятностью требует Ω (N) запросов к базе данных» - верно ли это и для модели не черного ящика? Это доказано?
user976850
4

Это зависит от того, что вы считаете фактическим доказательством, и что вы подразумеваете под «быстрее». С точки зрения теории сложности ответ - нет - у нас нет такого доказательства. BQP (класс задач, которые могут быть эффективно решены квантовым компьютером) содержится в PSPACE. Возможность доказать разделение между BQP и PSPACE также подразумевает разделение между P и PSPACE, что неизвестно.

Обратите внимание, что алгоритм Гровера дает только ускорение квадратного корня, поэтому здесь нет противоречий.

Норберт Шух
источник
1
Добро пожаловать! К сожалению, ваш ответ, кажется, противоречит сам себе. Вы говорите, что «с точки зрения теории сложности ответ - нет», но затем вы приводите один теоретический аргумент сложности, что ответ «мы не знаем», а другой говорит, что ответ «да». Так как же ответ нет?
Дэвид Ричерби
Вопрос спрашивает, есть «реальные доказательства квантовые компьютеры могут решить некоторые проблемы быстрее , чем классические компьютеры». Алгоритм Гровера доказуемо быстрее, чем любой классический алгоритм, поэтому ответ однозначно «да».
Дэвид Richerby
1
Алгоритм @DavidRicherby Гровера основан на оракуле (это черный ящик), с которым вы не сталкиваетесь в реальных проблемах. Как только вы рассматриваете структуру проблемы в оракуле (например, проверяете решение для NP-полной задачи), становится непонятно, сохраняется ли ускорение.
Норберт Шух
1
Этот ответ немного сбивает с толку, чтобы прочитать. Я думаю, что это поможет отредактировать ответ, чтобы прояснить эти моменты и точно продумать, какие претензии вы пытаетесь сделать, и какие аргументы вы можете предложить для поддержки этих претензий. Я думаю, что есть два момента, которые помогут уточнить: (а) разницу между ускорением за полиномиальное время и большим ускорением, (б) разницу между алгоритмом с оракулом и обычным алгоритмом. Затем используйте их, чтобы объяснить, почему алгоритм Гровера имеет ускорение, но это не противоречит другим вашим утверждениям.
DW
-1

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

  • частично это отражено формально в вопросе открытого класса сложности BPP =? BQP вопрос. это аналогичные классические и квантовые классы, и разделение неизвестно и является активной областью исследований.

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

  • Относящиеся к этому вопросу / дебаты / затрагивающие его, продолжаются существенные / «горячие» (научные) попытки сравнить текущий «крупнейший» в мире квантовый компьютер от DWave. это большая тема с большим количеством связанных материалов, но для сравнительно недавнего обзора попробуйте исследование споров D-Wave, показывающее вялый квантовый компьютер / Регистр

ВЗН
источник