Удачи, о которых идет обращение — демонстрация условий, в которых квантовый компьютер D-Wave стремительнее простого CPU в 100 миллионов раз. Новость об этом пролетала в этот самый момент, и по большому счету везде.

Что же это значит для простых смертных? Нужно ли вовсю переключаться на программирование на квантовых компьютерах? Что в том месте по большому счету за программирование?Мне стало любопытно, и я мало почитал про подробности (сама научная статья — тут).

Как неизменно, коротко говорю собственный познание.

Смотрите кроме этого: Гугл может перевести Android на язык программирования от Apple

Сейчас появились сведенья, в соответствии с которой Гугл разглядывает возможность перевода ОС Android с Java на объектно-ориентированный язык программирования Swift от компании Apple, представленный на конференции разработчиков WWDC 2014 и в конце прошлого года ставший открытым и общедоступным. Наряду с этим источники утверждают, что полное замещение Java пока не планируется. В полной мере быть может, что Гугл разглядывает такую возможность в связи с судебными слушаниями с компанией Oracle.

Disclaimer: пост написан на базе изрядно отредактированных логов чата closedcircles.com, из этого и стиль изложения, и наличие уточняющих вопросов.

Для начала, мало бэкграунда — что такое процессоры D-Wave.Делать универсальный квантовый компьютер — это весьма сложно и неясно как, исходя из этого D-Wave делают весьма узко-специальное железо, которое решает только задачу quantum annealing.

Что такое по большому счету annealing?

Это задача оптимизации вот для того чтобы выражения:

Имеется N двоичных переменных si, они принимают значения -1 либо +1. Возможно задавать вещественные коэффициенты hi и Jij.annealing — это минимизация E для всех вероятных значений двоичных переменных (при фиксированных коэффициентах).

а чем управляем в итоге? hi,Jij?Мы можем задавать их извне, да.что инпут, а что аутпут? в случае если мы задаем hi, Jij извне, то эта махина находит комплект si при котором E минимальна либо что?Да, как раз так.

Потом, нужно осознавать, что квантовый процесс не гарантирует нахождения глобального минимума, он с некой возможностью находит значение, которое какое количество-то близко к нему.

Какие конкретно практические задачи возможно решать так?

Пример в Гугловской статье — так называемый Number Partitioning Problem (NPP).Хорошая задача — имеется комплект из N положительных чисел, необходимо поделить их на две кучи, дабы суммы чисел в каждой куче были как возможно ближе друг к другу.

Кроме того такая несложная, казалось бы, задача — NP-hard и все эти дела, но ее достаточно как annealing.

Пускай двоичная переменная — это флаг принадлежности к какой-то куче.Тогда необходимо минимизировать:Минимизация модуля — это то же самое, что минимизация квадрата.

не осознаю связку между задачей разделения и первой формулой на кучиВот я расписал подробней:

Как решаются такие задачи на данный момент, на CPU?

Один из несложных и все еще довольно часто употребляющихся на практике способов — simulated annealing. Википедия пишет про него достаточно прилично — https://en.wikipedia.org/wiki/Simulated_annealing

Мысль в том, дабы начать с какого-либо случайного состояния двоичных переменных и на каждом шаге их случайно флипать.В случае если мы в следствии флипа взяли итог лучше — берем его. В случае если же нет, то берем либо нет с некой возможностью.Возможность зависит от отличия между старым значением и новым энергии и от так называемой температуры — еще одного параметра оптимизации, для того чтобы что в начале процесса температура громадная, а чем дальше, тем меньше.

За счет этого вероятностного процесса simulated annealing может вылезать из локальных минимумов. Очевидно, его возможно проводить пара раз, делать рестарты итд итп.В нем нет никаких эвристик и возможно руководить лишь температурным режимом.

Какие конкретно ограничения у D-Wave на практике?

В последней версии D-Wave около тысячи кубитов (это то самое количество двоичных переменных в задаче).Но имеется кое-какие подробности!

• Первая: вот эти Jij между двумя si и sj (они еще именуются couplings) требуют связи между отдельными кубитами, т.е. дабы между двумя параметрами был ненулевой коэффициент Jij — эти кубиты должны быть связаны.В NPP, к примеру, связан любой кубит с каждым, поскольку все Jij ненулевыеВ D-Wave любой кубит возможно связан (барабанная дробь) с ~10 вторыми, причем не с любыми, а заданными заблаговременно.

• Вторая: с какой точностью возможно задавать эти JijВ D-Wave эта точность (опять дробь) — 4 бита.Напомню, что в NPP Jij = ai*aj, т.е. для ai остается 2 бита, лол.

На всякий случай, русским языком — сложно придумать практическую задачу, которую возможно решать на этом всем добре.

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

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

В случае если у отечественного пространства большое количество громадных гор и впадин между ними…

То методу необходимо пройти через эти впадины в ходе оптимизации, и в отличие от simulated annealing, квантовый компьютер может на данный момент между достаточно узкими разломами.Т.е. simulated annealing обязан расширить энергию совокупности дабы выбраться наверх бугра, а квантовый копмьютер может на данный момент через стенке не увеличивая энергию совокупности. Отчего сойтись стремительнее — увеличивать энергию свидетельствует более продолжительный случайный поиск.Расстояние, на котором туннельный переход может случиться, определяется параметрами совокупности — температурой компьютера (эти все процессы становятся квантовыми при ~10K), конкретными подробностями физического лейаута итд итп.Посему, нужна задача где большое количество вот узких переходов таковой длины, дабы она преодолевалась D-Wave.

Ну прекрасно, как конструируется эта хорошая задача?

Главный элемент из которого они такую задачу собирают:Это 8 кубитов одного символа, и 8 кубитов другого символа. Любой в группе из 8 кубитов соединен с остальными связью с отрицательным весом (т.е. для минимизации энергии все в группе из 8 должны быть одного символа).Между некоторыми кубитами из первой и второй группы также имеется сообщение, также с отрицательным знаком (но более не сильный), и для нее то, что изначально группы различного символа — не хорошо.В совершенстве, в совокупности все кубиты должны быть одного символа, что ведет к минимуму энергии.

Но флипаньем одного либо двух битов в том направлении попасть запрещено — необходимо флипнуть все биты в группе из 8, для получения лучшего значения. Это и формирует такие высокие (но маленькие) преграды на ландшафте.

другими словами они создают вот такую успешную задачу посредством данной особой конфигурацией связи кубитов?Агаа какой настоящей задаче это соответствует?Никакой!Это все еще задача в рамках annealing (c hi и Jij), но практической ценности у нее нет никакой и быть не имеет возможности.

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

В работе сравнивается скорость D-Wave на данной задаче с simulated annealing и еще одним методом, Quantum Monte Carlo.Quantum Monte Carlo — это метод не для квантового компьютера, что, как я осознаю, пробует решить интеграл, обрисовывающий квантовое уравнение совокупности, способом Монте Карло.

Ну и вот они сравнивают SA и QMC на одном ядре CPU и quantum annealing на D-Wave с целью достижения той же точности результата (95% от оптимального, кажись). SA в их задаче для этого, к примеру, необходимо 109 запусков.

И вот сейчас наконец-то мы готовы осознать основной график из статьи:Это время исполнения задачи от количества двоичных переменных.

При большом размере задачи D-Wave вправду стремительнее simulated annelaling в 108 раз…Но! Ассимптотически D-Wave не лучше QMC (другими словами, и асимптотически лучше квантовый компьютер задачу не решает), но лучше SA.

у меня вот таковой необычный вопрос по этому графику, из-за чего числа сверху такие неровные? это настоящий размер неприятности? как-то не делится на 8По причине того, что в железе все несимметрично :)Имеется кубиты, у которых некоторых связей нет. На картине полного графа видно, что имеется кое-какие выпадающие кластеры — где-то несколько по 6, где-то 7.Пикантности додаёт то, что у каждого экземпляра D-Wave данный граф самую малость различный, по причине того, что он зависит от yield defects.

Свидетельствует ли это что хотя бы эту вырожденную задачу квантовый компьютер решает лучше, чем простой?

Нет! Лучше лишь в случае если сравнивать с методами без эвристик.Методы annealing с эвристиками (каковые наблюдают на связность графа итд) решают ее на одном CPU стремительнее, чем D-Wave. Что неудивительно: задача на самом высоком уровне весьма несложная, в случае если заметить что нужно флипать группами по 8.

Это подводит к нас к неопределённости и основной критике результата в ярком будущем.Оптимистично возможно сохранять надежду, что в новом железе будет большая точность и большая связность коэффициентов coupling, что разрешит записывать более жизненные и непростые задачи (каковые эвристиками решаться не будут).

Пессимистично возможно сомневаться, окажется ли по большому счету в скором времени выстроить что-то с этими параметрами, будет ли в том месте по большому счету квантовый эффект, и будет ли у жизненных задач таковой успешный ландшафт итд итп.

(больше подробностей, угара и ада тут — http://www.scottaaronson.com/blog/?p=2555)

О чем еще возможно сообщить также…

• Good news — итог помой-му обосновывает, что какой-то квантовый процесс по большому счету в DWave происходит (это был предмет ожесточенных холиворов вычисляй лет десять).
• Бороться за количество кубитов уже не требуется, необходимо бороться за связи и точность.

Подытожив — возможно расслабиться, неожиданного рывка нет, это следующий шажок в освоении квантовых компьютеров, использование на практике еще далеко.Возможно писать на PHP и javascript.

Случайная статья:

• The flir one: что умеет тепловизор для телефона?
• Как открыть командную строку?

Практические квантовые компьютеры/Practical quantum computing (Научпоп)

Похожие статьи:

• Квантовый компьютер google работает

  Поисковик уверен в том, что машина D-Wave подтвердила собственные правила работыКвантовые компьютеры — это счётные автомобили, каковые трудятся на базе…

• Почему google и ibm так активно работают над квантовыми компьютерами

  Когда-нибудь инженеры выстроят громадные квантовые компьютеры, каковые смогут решить громадные научные неприятности, взломать сложное шифрование и…

• Новые квантовые точки впервые удалось заставить излучать одиночные фотоны

  Японские физики сумели вынудить галлий-нитридные квантовые точки излучать одиночные фотоны при комнатной температуре, и это, быть может, очень важный шаг…