Max Home IndustryУчитывая всю эту суету, вы могли бы подумать, что квантовые компьютеры — это очень желанная вещь. Возможно, вы не знаете, что нет теоретических оснований полагать, что квантовый компьютер может делать что-то большее, чем классический. Однако некоторые новые результаты, кажется, доказывают, что квантовый компьютер действительно стоит иметь.
Есть серьезные предположения, что квантовые компьютеры могут делать больше, чем классические. Наиболее известен алгоритм Шора для разложения целых чисел на множители, который выполняет работу, требующую классического компьютерного экспоненциального времени за полиномиальное время. Это могло бы показаться доказательством того, что квантовые компьютеры лучше, но это не доказательство, потому что мы не можем продемонстрировать, что классический факторинг не имеет алгоритма полиномиального времени.
Вы можете подумать, что разложение на множители явно не в P, классе алгоритмов полиномиального времени, но явно в NP, классе недетерминированных алгоритмов полиномиального времени — что означает, что если вы дадите мне потенциальное решение, то есть факторы, я можно проверить, является ли это решением за полиномиальное время.
Если кто-нибудь когда-нибудь докажет, что NP = P, то разложение будет классически полиномиальным, а также квантовым полиномом. На данный момент лучшее, что мы можем сделать, — это субэкспоненциальная, которая находится между полиномиальной и экспоненциальной, то есть медленнее, чем любой полином, но все же быстрее, чем экспоненциальная. Алгоритм Шора O (b3) и, следовательно, явно полиномиален.
Таким образом, мы не можем на самом деле решить, является ли существование алгоритма Шора доказательством того, что квантовый компьютер лучше, если мы не сможем доказать, что классическое разложение на множители не может быть выполнено за полиномиальное время.
Новая статья делает больше, но не с помощью алгоритма Шора. Роберт Кениг из Технического университета Мюнхена (TUM), Дэвид Госсет из Университета Ватерлоо и Сергей Бравий из IBM берут версию известной проблемы и создают квантовую схему, которая ее решает.
Квантовые схемы эквивалентны классическим программам. Эта конкретная квантовая схема решает проблему, используя схему постоянной глубины, независимо от размера задачи n. Это все равно, что сказать, что она решается за постоянное время. Затем исследователи доказывают, что аналогичная классическая установка должна иметь логарифмическую глубину по n. Они также продолжают доказывать, что это преимущество связано с нелокальностью, присущей квантовой физике, то есть действительно имеет значение «жуткое действие на расстоянии».
Сейчас вы найдете заголовки, утверждающие, что для классического компьютера все кончено, но вам нужно внимательно следить за тем, что именно было доказано. Квантовый компьютер, ограниченный определенным режимом, превосходит классический компьютер, ограниченный аналогичным образом. Если снять ограничения, мы так и не узнаем, превосходит ли квант классический.
Так что это еще не повод для празднования, и, в частности, алгоритм Шора не является примером того типа квантового алгоритма, который только что оказался лучше, чем аналогичные ограниченные классические алгоритмы. В лучшем случае это еще одно указание на то, что квантовые компьютеры могут предложить что-то такое, чего мы не можем получить никаким другим путем, и это доказательство того, что в этой ситуации, подобной v, они действительно и доказуемо это делают.
Также нужно учитывать, что это теория. Трудности создания квантовых компьютеров, которые не становятся бесполезными из-за шума, до сих пор не решены. Это настолько сложная проблема, что некоторые даже предполагают, что Вселенная может быть построена таким образом, чтобы запретить существование квантового компьютера, а шум — это способ, которым он обеспечивает соблюдение этого запрета.
Чтобы доказать это, вам нужно будет показать некоторые нефизические последствия успешного построения квантового компьютера, а до сих пор никто не придумал такого парадокса.