Comments 57
Ух, наконец можно будет стабильно играть на 144 Hz во все новинки…
Какое число людей поняло прочитанное? Дай Бог памяти, на Поп_механике научно популярным статьям присваивается уровень сложности. Пора Вам перенять их опыт.
Тут не в уровне сложности проблема, а в том, что в статье (как это всегда бывает у SLY_G) просто не содержится никакой информации. Например, не дается ни определения «фурреляции», ни границ ее сложности, ни того, на кой черт для ее вычисления вообще нужен оракул. За этим вам придется лезть в оригинальные статьи. Определения даются здесь: arxiv.org/abs/1411.5729
Да автор умеет рассказать ничего обо всем.
Ну это как обычно — если статья сложная начинают кричать «что ты тут себе вообразил? никто ничего не понял. Тут не доктора наук собрались». А если простая, то: «что разлил на 20 страниц воды? Хватило бы и двух абзацев. И вообще новость 'неочем' »
Это неминуемо и нормально. Все люди разные. Хотите больше информации — читайте первоисточник. Главное, что он указан и статья не сделана в форме «Ученые открыли, что квантовые компьютеры угрожают человечеству». Там ниже в коментарии есть ссылка на объяснгения на языке оригинала. Неплохо бы конечно и ее перевести но понятно что нельзя все засунуть в одну статью.
Это неминуемо и нормально. Все люди разные. Хотите больше информации — читайте первоисточник. Главное, что он указан и статья не сделана в форме «Ученые открыли, что квантовые компьютеры угрожают человечеству». Там ниже в коментарии есть ссылка на объяснгения на языке оригинала. Неплохо бы конечно и ее перевести но понятно что нельзя все засунуть в одну статью.
Пора просто переводить втупую статьи, в которых переводчик/редактор ничего не понимает. И начать переводить те, в теме которых переводчик понимает хоть что-то (а лучше всё).
Это как бы совершенно очевидная вещь, но она упорно игнорируется поколением современных «переводчиков» от гугл транслейт.
P.S. Я тоже почти ничего не понял в статье, хотя читал внимательно. Ну да, классы задач. Ну, новый класс задач. Но это все самыми общими словами.
Это в общем не статья и даже не анонс. Это заметка ниачом.
Это как бы совершенно очевидная вещь, но она упорно игнорируется поколением современных «переводчиков» от гугл транслейт.
P.S. Я тоже почти ничего не понял в статье, хотя читал внимательно. Ну да, классы задач. Ну, новый класс задач. Но это все самыми общими словами.
Это в общем не статья и даже не анонс. Это заметка ниачом.
Забавно, некоторые возмущается, нет объяснения в статье того, или этого, не замечая, что это просто перевод научно-популярной статьи. В ней, что исходно есть, то и есть. Можно апеллировать к качеству перевода, но переводчик не обязан суда ничего добавлять.
Так же забавны возмущения, что настолько просто все изложено, что ничего не понятно) Просто удивительны такие феномены, не могут понять в простом изложении, подайте им в виде оригинальной статьи, часто со специализированной математикой, кот. действительно понимают может несколько человек в мире)
Все же тут не специализированный математический форум, и важно быть в курсе новостей связанных с компьютерными технологиями и связанными областями. А тонкости, если возник проф. интерес, всегда можно посмотреть в источниках. Ссылки обычно приводятся в темах.
Так же забавны возмущения, что настолько просто все изложено, что ничего не понятно) Просто удивительны такие феномены, не могут понять в простом изложении, подайте им в виде оригинальной статьи, часто со специализированной математикой, кот. действительно понимают может несколько человек в мире)
Все же тут не специализированный математический форум, и важно быть в курсе новостей связанных с компьютерными технологиями и связанными областями. А тонкости, если возник проф. интерес, всегда можно посмотреть в источниках. Ссылки обычно приводятся в темах.
Понимаете, все что сказано в статье, можно было уместить в один абзац.
А переливание из пустого в порожнее очень общими словами о каких-то научных вещах — что выдается за «научно-популярное» — это совершенно не то, чего ожидаешь от статьи на хабре.
Особенно от редактора хабра. Ничего личного, просто от редактора хабра ждешь более ответственного подхода к формированию контента, к выбору материала для перевода или к самому качеству перевода.
А переливание из пустого в порожнее очень общими словами о каких-то научных вещах — что выдается за «научно-популярное» — это совершенно не то, чего ожидаешь от статьи на хабре.
Особенно от редактора хабра. Ничего личного, просто от редактора хабра ждешь более ответственного подхода к формированию контента, к выбору материала для перевода или к самому качеству перевода.
Статья (или перевод) вводит в заблуждение. Классический компьютер, т.е. (детерминированная) машина Тьюринга, может решить любую задачу решаемую квантовым компьютером. В cтатье (или опять же, в переводе) утеряна разница между «решаемо» и «эффективно решаемо», и между «computability» и «complexity».
Для интересующихся, Скотт Ааронсон (о нем в посте) недавно написал интересный пост про BQP vs PH, где детальнее рассказал, что там к чему. Ну и просто интересная история про то, как идеи развиваются в науке.
Эм, сначала изобрели «такие» компьютеры и только потом изобрели «то» для чего изобрели «такие» компьютеры. Я правильно понял?)
Не до конца изобрели такие компьютеры, но уже стали задумываться для чего же они нужны.
Как известно, компьютер (обычный) позволяет решать проблемы, которых до появления компьютера не существовало, так что тут ничего нового :)
Ну да, начала построили интересную модель, потом начали смотреть куда ее можно приложить. Как только это «куда» нашлось (или хотя бы признаки существования этого «куда») — модель стала интересной не только ее создателю. Математики часто именно так работают, это просто альтернатива варианту «взять задачу и начать ее решать», оба пути могут дать что-то полезное, а могут и не дать.
Ну а когда появились достаточно интересные задачи для квантового компьютера — тогда уже подключились инженеры, которые пытаются его собрать.
Но вообще ответ на ваш вопрос зависит от того, что вы подразумеваете под «изобрели». Если модель — то да, сначала была модель, потом задачи (если я ничего не путаю). Если сам компьютер как устройство — то нет, перед ним была модель и задачи которые с ее помощью можно решить.
Ну а когда появились достаточно интересные задачи для квантового компьютера — тогда уже подключились инженеры, которые пытаются его собрать.
Но вообще ответ на ваш вопрос зависит от того, что вы подразумеваете под «изобрели». Если модель — то да, сначала была модель, потом задачи (если я ничего не путаю). Если сам компьютер как устройство — то нет, перед ним была модель и задачи которые с ее помощью можно решить.
Задача коммивояжёра спрашивает, существует ли путь, проходящий через определённые города, более короткий, чем заданное расстояние. Такая задача находится в NP. Более сложная задача спрашивает, является ли это расстояние наикратчайшим путём через эти города. Такая задача находится в PH.
Что-то не так с переводом? Если путь существует, то расстояние не кратчайшее. Если не существует — то кратчайшее. Это эквивалентные вопросы.
Кажется, что все нормально: по сути, NP просит найти любой путь короче некоторого расстояния. PH спрашивает, является ли найденный путь кратчайшим.
Оригинал
The “traveling salesman problem” asks whether there’s a path through some number of cities that’s shorter than some given distance. It’s in NP. A more complex problem asks if the shortest path through those cities is exactly that distance. That problem is in PH.
Найденный? Не данный? Ну если NP — найти любой, короче данного, а PH — найти самый короткий — то да, разные задачи. Но в оригинале тоже не ясно — "exactly that distance" — that — это та, которая "given" или та, которая "shorter".
В любом случае, спасибо за такой вариант прочтения.
На самом деле, мне кажется, тут пример про коммивояжера — это именно пример задачи в PH, а не ее полное описание. PH — это обобщение NP, где может быть больше одного условия, и может быть связь между условиями (напр. найти только те пути, которые меньше данного расстояния и проходят через город N три раза). Нахождение кратчайшего расстояния — пример такого дополнительно условия.
Оригинал
PH is a generalization of NP. This means it contains all problems you get if you start with a problem in NP and make it more complex by layering qualifying statements like “there exists” and “for all.”
И из статьи Ааронсона:
PH, or the Polynomial Hierarchy, is a generalization of NP to allow multiple quantifiers (e.g., does there exist a setting of these variables such that for every setting of those variables, this Boolean formula is satisfied?).
а мне показалось всё логичным: «путь, проходящий через определённые города, более короткий, чем заданное расстояние» означает любой путь из подмножества
а «является ли это расстояние наикратчайшим путём через эти города» ответ: Да / Нет без допущений
а «является ли это расстояние наикратчайшим путём через эти города» ответ: Да / Нет без допущений
Только не показывайте эту задачу Ювину Тану, а то получится как тогда.
По сути дела, это больше теоретическое достижение, чем практическое, которое, к тому же кажется чем-то очевидным. Практическая проблема, что квантовому алгоритму можно дать одну подсказку или 1000, разница будет в том, что он найдет решение с большей или с меньшей вероятностью.
С теоретической точки зрения, было бы даже интереснее получить решение задачи «исчисления предикатов». Общая задача состоит в том, что если у теорема верна (т.е. ее отрицание противоречит аксиомам), то у нее существует конечный вывод. К сожалению, почти очевидно, что разумного «алгоритма» не существует, дерева исчисления растет слишком быстро. В то же время очевидно, что квантовый компьютер может перебирать по всему пространству сразу и, возможно, он может дать ответ за конечное время. Опять же обычный компьютер не сможет проверить это, если не знает самого вывода. Эта задача будет общей для большого количества задач, так как практически все записывается в предикатах.
С теоретической точки зрения, было бы даже интереснее получить решение задачи «исчисления предикатов». Общая задача состоит в том, что если у теорема верна (т.е. ее отрицание противоречит аксиомам), то у нее существует конечный вывод. К сожалению, почти очевидно, что разумного «алгоритма» не существует, дерева исчисления растет слишком быстро. В то же время очевидно, что квантовый компьютер может перебирать по всему пространству сразу и, возможно, он может дать ответ за конечное время. Опять же обычный компьютер не сможет проверить это, если не знает самого вывода. Эта задача будет общей для большого количества задач, так как практически все записывается в предикатах.
Кажется, что практической пользы совсем нет: эти форелляции требуют оракула, а мы даже не представляем, как оракул мог бы реализовываться в реальности.
Кстати, а откуда вам кажется очевидным это достижение?
Кстати, а откуда вам кажется очевидным это достижение?
мы даже не представляем, как оракул мог бы реализовываться в реальности.Это не может быть измерение, или некий опыт в общем случае? Если речь о ГСЧ, о которых речь в статье, и требуется подсказка «каким будет шестое число у каждого генератора?», то можно прочесть сгенерированное значение и передать в процедуру сравнения, кот. устанавливает зависимость/независимость генераторов. Исхожу из более общих соображений, как действует человек, когда возникают проблемы с доказательством достоверности теоретических построений — решается постановкой эксперимента.
********
С квантовыми алгоритмами определись, получается отдельный класс. А как насчет класса сложности задач, который может решить встроенный «компьютер» человека — мозг? Можно действовать по аналогии, найти задачу, кот. мозг, даже коллективные мозги, не могут решить. Далеко ходить не надо, такая задача имеется — квантовая гравитация, точнее создание общепринятой, многократно независимо подтвержденной и практически применимой теории. Скоро уже, как век над ней бьются лучшие умы человечества, а решения пока не видно, не хватает мощности мозгов, выдаются многочисленные промежуточные результаты. Ждем подсказок «оракулов» — решающих экспериментов и прямых наблюдений)
Насколько я понимаю, оракул «знает» решение задачи, и дает подсказки нашему компьютеру. Реализовать его, видимо, нельзя в принципе — т.к. он по определению «мощнее» нашего компьютера. Мне кажется, это чисто теоретическая конструкция, введенная как критерий сравнения алгоритмов. Поэтому алгоритмы, для которых необходим оракул, не получится реализовать на практике. Это чисто математика.
Ааронсон об этом же пишет:
Мне кажется, мозг использует много разных алгоритмов. Но пока мы не знаем, как работает мозг, гадать бесполезно.
Не думаю, что ваше рассуждение имеет отношение к классам сложности выше NP. Подозреваю, что эта задача вполне себе лежит в классе Р, т.е. вполне может быть решена классическим компьютером за конечное время.
Ааронсон об этом же пишет:
Тут
a journalist already emailed to ask me about the practical implications of the BQP vs. PH breakthrough—for example, for the ~70-qubit quantum computers that Google and others hope to build in the near future—let me take the opportunity to say that, as far as I can see, there aren’t any. This is partly because Forrelation is an oracle problem, one that we don’t really know how to instantiate explicitly (in the sense, for example, that factoring and discrete logarithm instantiate Shor’s period-finding algorithm). And it’s partly because, even if you did want to run the quantum algorithm for Forrelation (or for Raz and Tal’s noisy Forrelation) on a near-term quantum computer, you could easily do that sans the knowledge that the problem sits outside the polynomial hierarchy.
А как насчет класса сложности задач, который может решить встроенный «компьютер» человека — мозг?
Мне кажется, мозг использует много разных алгоритмов. Но пока мы не знаем, как работает мозг, гадать бесполезно.
Далеко ходить не надо, такая задача имеется — квантовая гравитация, точнее создание общепринятой, многократно независимо подтвержденной и практически применимой теории.
Не думаю, что ваше рассуждение имеет отношение к классам сложности выше NP. Подозреваю, что эта задача вполне себе лежит в классе Р, т.е. вполне может быть решена классическим компьютером за конечное время.
Насколько я понимаю, оракул «знает» решение задачиЗнаю про такое определение. Но все же странно, как использовать выводы этих теорем на практике, когда речь дойдет о действительном сравнении тех же реализаций ГСЧ. Похоже классическим способом в классе PH), простым сбором статистики, и сравнением результатов.
Не думаю, что ваше рассуждение имеет отношение к классам сложности выше NP. Подозреваю, что эта задача вполне себе лежит в классе Р, т.е. вполне может быть решена классическим компьютером за конечное время.Это вы о результате в виде готовой теории?) Я о процессе построения. Это другой уровень, аналога кот. в самых сложных алгоритмах пока нет. Все классы алгоритмов вычислительной сложности лишь некоторый аспект некоей интеллектуальной сложности деятельности мозга. Аспект абстрагированный, и реализованный с помощью технических средств. Абстрагирование имеет отношение к построению любых теоретических конструкций. Но абстрагирование имеет свои ограничения, кот. ограничивают и классы решаемых задач, по крайней мере, могут сильно затруднить их решение. Квантовая гравитация относится к этому классу.
Но все же странно, как использовать выводы этих теорем на практике, когда речь дойдет о действительном сравнении тех же реализаций ГСЧ.
Ну а никак не использовать:) Эти алгоритмы неприменимы на практике. Тем не менее, сам факт их существования важен для разработки новых, уже рабочих, алгоритмов.
Я о процессе построения. Это другой уровень, аналога кот. в самых сложных алгоритмах пока нет.
Во-первых, как я понимаю, процесс построения не имеет отношения к классам сложности. Если вы к тому, что сам процесс тоже является задачей, и должен относиться к какому-то классу, то он относится, думаю, как максимум к NP — компьютер может проверить, что этот алгоритм выполняет задачу, если мы ему дадим готовый алгоритм.
Во-вторых, я не очень понял, в чем разница между «абстрактным» мышлением и компьютером. Я могу дать задачу своему компьютеру построить теоретическую модель или сделать симуляцию ровно так же, как я это делаю со своим мозгом. Мозг работает сильно параллельно, компьютеру далеко до этого, но суть в общем та же.
Сейчас есть нейронные сетки, которые строят эксперименты в квантовой оптике, оптимальность которых очевидна на практике, но совершенно недоступна нашему пониманию. Не очень вижу разницу между такой сетью и студентом, если вход и выход одинаков.
Ну а никак не использовать:)Похоже на то) Единственное замечание, что ''оракул", или «черный ящик» знает решение задачи, но ведь реальная реализация ГСЧ, например, аппаратная реализация, использующая некоторый физич. эффект для генерации чисел, является фактически таким «черным ящиком», кот. знает решение, то есть он подходит под определение «оракула» в этих теоремах.
Сейчас есть нейронные сетки, которые строят эксперименты в квантовой оптике, оптимальность которых очевидна на практике, но совершенно недоступна нашему пониманию. Не очень вижу разницу между такой сетью и студентом..Можете ссылку привести, было бы любопытно глянуть. Если интересно, посмотрите эту дискуссию с пользователем, кот. пытался используя теоремы Гёделя опровергнуть возможность создания ИИ, позволяющего создавать формальные системы, на уровне с человеком.
Можете ссылку привести, было бы любопытно глянуть.
Например вот или вот. Вот про эту статью как раз автор говорила, что им выдает оптимальный алгоритм, логику за которым проследить не получается (а аналитического решения нет).
Спасибо за ссылку, я почитаю на досуге:)
Насколько я понял, под оракулом в статье подразумевается не общий термин, а конкретная сущность из теории квантовых вычислений. Там оракулом зовётся квантовая функция, реализующая вычисление некой исходной классической функции (обычно, являющейся ключевой для решения задачи).
Судя по статье Ааронсона и вики, это черный ящик, к которому может обратиться компьютер с вопросом о задаче, и оракул даст всегда правильный ответ за один шаг:
For example, if the problem is a decision problem for a set A of natural numbers, the oracle machine supplies the oracle with a natural number, and the oracle responds with «yes» or «no» stating whether that number is an element of A.
если у теорема верна (т.е. ее отрицание противоречит аксиомам),
"Т.е." у вас сомнительное. Есть верные теоремы, про которые мы никогда не сможем сказать, что они верные (и методом от противного — тоже, а значит не можем сказать, что отрицание противоречит аксиомам).
Берём классический компьютер, запускаем на нём симуляцию квантового.
@
Работает чуть помедленнее, зато требует всего одну подсказку.
@
Шах и мат, академики.
@
Работает чуть помедленнее, зато требует всего одну подсказку.
@
Шах и мат, академики.
Есть нюанс. В статье говорится о преимуществе квантового компьютера над «boolean circuit», т.е. цифровым компьютером, но ничего не говорится об аналоговых компьютерах, не использующих квантовые эффекты. А ведь для некоторых квантовых алгоритмов придумали реализации и в виде классической аналоговой системы, имеющие такое же преимущество в скорости над цифровыми компьютерами.
Какая-то SEO-шная статья. 2/3 пересказывают одно и то же разными словами, почти никакой конкретики.
Кажется, Либо в статье опечатка, либо я совсем запутался:
3P = NP?
Самый лучший способ разделить классы сложности BQP и ЗР – измерить вычислительное время,
3P = NP?
Я так и не увидел ответ на главный вопрос: Дум на нем уже запустили или еще нет?
Про Crysis уже спрашивали.
На квантовом компьютере Crysis на максималках будет летать?
За исключением некоторого подмножества задач, которые квантовая модель вычислений способна ускорить, остальные могут быть решены лишь эмуляцией классического компьютера. Что, как вы понимаете, очень медленно. Crysis, скорее всего, будет лагать.
И да, и нет.
Это как Crysis. Игра была, а железо, которое потянет его топовую графику – нет.
за последние дни — вторая статья в этом стиле… хрен найдешь, где ответ на заголовок! Рекомендую переводчикам вставлять ответ до хабраката, думаю, многие скажут спасибо. Мне абсолютно неинтересно, как кто-то там искал и как он там это нашёл до того, как эта вещь покажется мне интересной. Далее, либо в топку, либо действительно стоит углубиться…
Из прочитанного так и не понял — это та самая машина, которая сможет дать «Ответ на главный вопрос жизни, вселенной и всего такого»?
Sign up to leave a comment.
Наконец появилась задача, которую смогут решить только квантовые компьютеры