Алгоритм Шора часто используется в качестве аргумента. Он может решить проблему факторизации быстрее, чем любой известный алгоритм для классических компьютеров. Тем не менее, у нас нет доказательств того, что классические компьютеры также не могут эффективно вычислять целые числа.
Есть ли какие-либо доказательства того, что квантовые компьютеры могут решить некоторые проблемы быстрее, чем классические компьютеры?
algorithms
efficiency
quantum-computing
MaiaVictor
источник
источник
Ответы:
источник
Это зависит от того, что вы считаете фактическим доказательством, и что вы подразумеваете под «быстрее». С точки зрения теории сложности ответ - нет - у нас нет такого доказательства. BQP (класс задач, которые могут быть эффективно решены квантовым компьютером) содержится в PSPACE. Возможность доказать разделение между BQP и PSPACE также подразумевает разделение между P и PSPACE, что неизвестно.
Обратите внимание, что алгоритм Гровера дает только ускорение квадратного корня, поэтому здесь нет противоречий.
источник
Вы спрашиваете об «доказательстве», которое может быть ограничено математическим уровнем, но основной вопрос гораздо глубже этого. Теоретики признают, что в основном все еще остается открытым вопрос об относительной производительности квантовых и классических алгоритмов, и, вероятно, нет простого / общего ответа, но с некоторым экспертным согласием, что алгоритм Шорса кажется «необычайно быстрым по сравнению с ожидаемой лучшей классической скоростью». «. быстрый факторинг в классическом компьютере нарушит широко распространенные предположения о криптографической безопасности, такие как система RSA .
частично это отражено формально в вопросе открытого класса сложности BPP =? BQP вопрос. это аналогичные классические и квантовые классы, и разделение неизвестно и является активной областью исследований.
тесно связанный с этим вопрос заключается в том, можно ли создавать физически компьютеры QM, которые соответствуют теоретическим спецификациям, и некоторые / меньшинство ученых (так называемые «скептики») утверждают, что могут существовать законы шума или масштабирования, которые препятствуют масштабированию QM, как предусмотрено в теории. в некотором смысле окончательным «доказательством» скорости компьютера QM должна быть физическая реализация. (Это похоже на то, как тезис Черча-Тьюринга является теоретическим, но, похоже, в конечном итоге связано с утверждением о физических реализациях.) Некоторые исследователи говорят об аналогах Черч-Тьюринга в вычислениях QM. см., например, тезис Черч Тьюринга в квантовом мире Монтанаро.
Относящиеся к этому вопросу / дебаты / затрагивающие его, продолжаются существенные / «горячие» (научные) попытки сравнить текущий «крупнейший» в мире квантовый компьютер от DWave. это большая тема с большим количеством связанных материалов, но для сравнительно недавнего обзора попробуйте исследование споров D-Wave, показывающее вялый квантовый компьютер / Регистр
источник