Превосходный FAQ о квантовом превосходстве от Скотта Ааронсона

[quverty]

Что значит скучным? Вы уж тоже переведите, пожалуйста. И надо бы всё таки на вы его. Кстати, утёкшие фрагменты тут и тут (приложение).

[Shkaff]

Хорошо, если интересно — переведу завтра.

И надо бы всё таки на вы его.

Кажется, в стиле вопросов FAQ скорее дружеское обращение, поэтому я выбрал «ты».

Фрагменты я специально не постил, т.к. автор явно не хотел этого в своем посте, но спасибо за ссылки!

[quverty]

Хорошо, если интересно — переведу завтра.

Там этот кусок представляет достаточно естественную часть текста, так как текст скорее не про «квантовое превосходство» вообще, а про новость о проверке «превосходства» тем способом, которым сделал Google и в непереведённом куске есть полезная информация по истории вопроса.

[Shkaff]

Да, я его прочитал, конечно. Мне просто показалось, что он будет не особо интересен для большинства — слишком много персонального про Ааронсона. Но вы правы, конечно, надо сделать.

[Shkaff]

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

[inetstar]

Люди такие наивные. Естественно, ничего не «утекло». Информацию специально слили, а потом убрали. Скорее всего, чтобы вызвать PR-эффект и поднять цену акций.

[Shkaff]

Ну странно немного, а почему слили не в гугле, а в NASA? Да и потом, почему бы не дождаться публикации в крутом журнале, зачем сливать устаревшую версию с неполной информацией.
Как бы когда «сливают» дизайны нового айфона — там все ясно. Но тут ситуация, кажется, немного другая.

[ctc]

"… но очень интересно."

[Shkaff]

Ну вот Скотт пишет об этом же: единственный способ сделать это на классическом компьютере (насколько нам известно) это брутфорс. И гугл его сделал и показал, что это заняло на порядки больше времени. А строгого доказательства, что не существует другого алгоритма — нет, насколько я понял. Так что превосходство это скорее практическое, чем абсолютное.

[plus79501445397]

Насколько я понял, в статье от 2016г. приводится подробное обоснование (с вполне строгим док-вом многих моментов) в частности того, «что это очень сложная задача для классических машин», конечно в предположении, что P!=NP и т.п. (см. так же В8 в FAQ), более кратко в FAQ и презентации об этом (ссылки есть в FAQ). В статье (и презентации) так же есть список открытых проблем. Возможно не всех устроит такое обоснование, но как «рабочее» почему-бы и нет? Еще бы гугол наконец опубликовал, что именно у него там получилось (ну или опровержение;))

[Shkaff]

Я добавил перевод В13, где Скотт дает ссылки и поясняет, что алгоритм действительно классически сложный (как указал выше plus79501445397).