Комментарии 85
Вы так написали, как будто они его уже построили, а это просто концепт:
The goal of the Google Quantum AI lab is to build a quantum computer...
Я не имел ввиду количество кубитов, если там будет реально 72 кубитный компьютер — очень круто. Но пока я вижу набор проводков, громкие слова и никаких экспериментальных данных.
Ну я не знаю, я читаю их блог:
We are looking to achieve similar performance to the best error rates of the 9-qubit device, but now across all 72 qubits of Bristlecone. We believe Bristlecone would then be a compelling proof-of-principle for building larger scale quantum computers.
Из этого я не вижу иной интерпретации, кроме как что компьютер еще не в работе. Пока нет никаких экспериментальных данных, говорить о том, что "построили", смысла нет, так как с момента фабрикации платы до момента работы могут пройти годы.
Нет, ну в целом нормально — они могли представить на конференции концептуальный дизайн и первые идеи, как это должно работать. Это если основываться только на их источнике — блоге, а не заниматься гаданием. Они же не пишут: "мы построили новый компьютер", они пишут: "мы представили прототип и концепт, как он будет когда-нибудь хорошо работать для error correction".
Из всех алгоритмов пока в работе со многими кубитами особо ничего не показывали, все эти тысячи — только на бумаге. Кроме того, каждый тип кубитов требует разного подхода к коррекции ошибок. Если гугл работает со сверхпроводящими гейтами, им на них и коррекцию надо делать. Они хотят квантового превосходства от компьютера, т.е. 49 кубитов должны быть в работе, а остальные на коррекцию ошибок. Ну вот и будут тестировать, сколько им нужно понадобится.
— The goal of the Google Quantum AI lab is to build a quantum computer
— Today we presented Bristlecone, our new quantum processor
Представили процессор, а построить хотят компьютер. Или Вы системный блок процессором называете?))
Моя единственная претензия была не к источнику, там все написано аккуратно, без упоминаний о работоспособности железа, а к переводу, который у меня создал впечатление, что гугл построил работающий компьютер (ну или процессор). Пока этот девайс еще должен пройти тестирование и показать, что он вообще работает, и насколько хорошо. Так что все написанное — не более чем проект.
а Гугл и остальные хотят создать наподобие универсального процессора в обычных компьютерахИнтересно, какие физические принципы они планируют использовать?
Во всяких популярных публикациях по квантовым вычислениям нарисованы гейты, соединённые так, как требуется для решения задачи. А как физически планируется достигать таких конфигураций — никто почему-то не пишет.
IBM немного описывал для своих систем (доступных в "облаке" "IBM Quantum Experience"), также построенных на сверхпроводящих кубитах — Superconducting quantum computing
IBM QX5: Albatross — 16 кубитов, 22 соединения (соединены далеко не все пары кубитов)
https://github.com/QISKit/ibmqx-backend-information/tree/master/backends/ibmqx5
Можно также поискать среди публикаций Martinis Group — Josephson Junction Quantum Computing at UCSB, т.к. они активно участвуют (руководят) в квантовых проектах Google https://web.physics.ucsb.edu/~martinisgroup/publications.shtml
https://web.physics.ucsb.edu/~martinisgroup/papers/Neill2017.pdf — 9 кубитов
https://web.physics.ucsb.edu/~martinisgroup/papers/Foxen2017.pdf — о проблемах связи в массивах более чем 2xN
Компьютеры D-Wave работают на принципе квантовой релаксации и решают крайне узкий спектр задач, в отличии от Google аналогов.
Вы совершенно правильно ставите вопрос: сколько из этих купит реально запутаны. Гугл скромно молчит, т.к. похвастаться, скорее всего, нечем.
Похоже, это просто массив 36 пар кубитов, которые работают одинаково, и коррекция ошибок достигается сравнением работы большого количества дублируются пар кубитов. А это, мягко говоря, совсем не одно и то же, что процессор из 72 связанных кубитов.
Убеждает меня в этом их график, что ошибки снижаются при росте числа "ихних" кубитов. В настоящем квантовой компьютере ошибки будут только нарастать с ростом количества кубитов, что очевидно.
Могу ошибаться, но перед нами 36 процессоров, каждый на двух кубитов, что является вчерашним днём квантовых компьютеров.
Ещё один мой аргумент против Гугл: компьютер, это видно, не криогенный. А большое количество настоящих кубитов сегодня достигается только вблизи нуля кельвинов.
Они используют корректировку ошибок с помощью кубитов, поэтому, чем больше кубитов, тем легче им корректировать ошибки
Разумеется. Вот только они добавляют кубиты, которые многократно дублируют базовую ячейку. Грубо говоря, если из 36 ячеек 19 посчитали 2х2=4, а 17 ячеек посчитали 2х2=5, то стало быть, правильный ответ 4. В таком случае действительно, если наращивать число ячеек, вероятность ошибки будет падать. О чём они и говорят.
Это ни то же самое, что добавлять кубиты в запутанный набор. Их реально считающий квантовый компьютер состоит, по-видимому, всего из двух кубит. Остальное многократное резервирование для исправления ошибок.
То, что вы описываете это стандартная схема утроения, она может либо фазовые ошибки исправлять либо bit flip, но не обе вместе, для больших нужно либо shor code либо два уровня [7,1,3].
Проблема даже не в этом, например если они используют shor code для QEC то у них в лучшем случае 8 лог кубитов(полезных для вычислений), а не 72. Но проблема в том, что для shor code нужно 72 запутанных кубита, а у них их нет, т.е если смотреть что у них реально может быть дай бог 6-8 запутанных кубит, то получим что error correction только на bit flip или только на фазу и 2-3 логических
но ведь и взять на борт современного CPU ПЛИСу, то точно так же это позволит решать NP-трудные задачи за вменяемое время.
Не позволит. Возьмем задачу коммивояжера. Ее можно решать точно для размерности N=1000. А вот уже для N=1001 она не решается — время решения уже неприемлемо долгое. И даже если вы при помощи ПЛИСов поднимете размерность до N=1001, то уже N=1002 будет недоступно даже для ПЛИСов. Я уж не говорю про энергозатраты такого мероприятия. В том-то и проблема экспоненциального взрыва, что на классических архитектурах вы упретесь в масштабирование.
вот вспомнить пресловутых майнеров. У них NP-трудная задача, а денег им хочется. Что они делают? берут ПЛИС, решают на ней эту NP-трудную задачу, затем оформляют ПЛИС как относительно недорогую микросхему и начинают копать.
Но никто из майнеров еще не решил проблему таким образом, чтобы для произвольной сложности сети быстро находилось решение.
Квантовые компьютеры, если они будут созданы (в чем есть сомнения), решат проблему экспоненциального роста сложности задач на корню. Не нужно будет для новой задачи строить АЭС и фермы для майнинга решения.
у Вас ошибка: при размерности 1000 точно ее решать невозможно
Возможно, методом ветвей и границ. Хотя, конечно, конкретная размерность, какую осилит метод ветвей и границ, сильно зависит от свойств самой задачи. Но N=1000 точно решается.
Уже при размерности 10 ее решать точно нельзя
Метод ветвей и границ а) точный, б) позволяет поднять размерность до 1000.
так вот, мы решаем ее следующим образом. Используем метод градиентного спуска с вероятностями выбора пути.
Есть, кстати, асимптотически точный алгоритм решения задачи коммивояжера. Т.е. вы сами задаете требуемую точность решения, и на выходе получаете соответствующую вычислительную сложность. Хотите точно — получите полный перебор, довольствуетесь 50% погрешности — решите за линейное время.
так я и прошу помочь мне понять как квантовый компьютер мне поможет с той же задачей комивояжера?
Квантовый алгоритм я Вам не напишу. Если не ошибаюсь, для гипотетического квантового компьютера разработали алгоритм, решающий задачу за линейное время. Идея в том, что экспоненциальная сложность не исчезает сама по себе. Просто квантовая природа прячет в себе экспоненту.
я пока вижу что квантовый комп дает возможность относительно несложно программить нейроные слои.
Да на фиг не нужен квантовый компьютер для нейросетей! Там нет вычислительно сложных задач. Нейросети — это как раз та штука, которая или на ПЛИС ложится, или на GPU.
Да на фиг не нужен квантовый компьютер для нейросетей! Там нет вычислительно сложных задач. Нейросети — это как раз та штука, которая или на ПЛИС ложится, или на GPU.Нет, если рассматривать процесс обучения в комплексе, он ложится на квантовый компьютер отлично, но к сожалению размерность сети потребует аналогичный порядок количества связных кубит.
Буквально на днях тут была статья-перевод какраз о попытках использования квантовых компьютеров именно для ускорения нейросетей и их обучения.
Нет, если рассматривать процесс обучения в комплексе, он ложится на квантовый компьютер отлично, но к сожалению размерность сети потребует аналогичный порядок количества связных кубит.
Еще раз: в нейросети нет экспоненциальной вычислительной сложности. алгоритм обучения — линейный (или квадратичный? не спец. Факт, что не экспоненциальный). На хрена использовать квантовые компы для обычных линейных алгоритмов?
Вам никто не запретит умножение двух чисел реализовать полным перебором, но это ведь попахивает идиотизмом? Тоже и с нейросетями.
Ошибаетесь. Квантовые алгоритмы, решающие NP-полные задачи, неизвестны.
Общий случай TSP не BQP так что в общем случае будет вместо факториала, корень из него. Если известно, что веса рёбер имеют нормальное распределение, вот тогда только BQP
Во вторых вы ошибаетесь что на КК можно решать NPC задачи, ни одного алгоритма ускоряющиеся NPC задачи мне не известно. Задача факторизации не является NPC.
так я и прошу помочь мне понять как квантовый компьютер мне поможет с той же задачей комивояжера?Если совсем грубо, перебирая варианты классическим компьютером, мы за 1 шаг можем из пункта A пойти в B, а за другой шаг — из A в C.
Используя квантовые вычисления, можно создать состояние суперпозиции, когда за один шаг мы пошли одновременно во все точки, достижимые из A (т.е. сразу в B, C, E, H, ...). За второй шаг — суперпозиция всех возможных маршрутов длины 2 (ABA, ABC, ACD, ADE, AEC, ...). Затем через N шагов происходит редукция и из всех состояний суперпозиции выживает то, которое оптимально. Его считываем как решение.
у Вас ошибка: при размерности 1000 точно ее решать невозможно
Возможно, методом ветвей и границ. Хотя, конечно, конкретная размерность, какую осилит метод ветвей и границ, сильно зависит от свойств самой задачи. Но N=1000 точно решается.
Прошу пардону! Я Вас ввел в заблуждение. N=1000 действительно точно не решается. Метод ветвей и границ для точных решений осиливает N=100, т.е. в 10 раз меньше.
Когда-то давно еще читал, что для них и программирование отдельное, несовместимое с обычными ПК. Т.е. интерпретатор написать конечно же можно, но это будет тормозное чудовище как эмулятор PS4 например.
Поидее ни один квантовый комп не порвет современные на современных же программах.
Мгновенно порвет на специфических задачах. NP-трудные задачи не имеют эффективных алгоритмов, а неэффективные алгоритмы могут искать решение дольше, чем существует Вселенная. Квантовые же компьютеры способны выдавать решение таких задач (для которых может потребоваться в миллиарды раз большее время, чем существует Вселенная), за несколько секунд.
Но все это при условии, что квантовые компьютеры будут созданы. Там тоже проблема масштабирования присутствует. Преодолеют — майнинг в прошлое уйдет. Как и вся цифровая экономика и приватность в интернете. Зато задача фолдинга белков будет решена, что круто :)
уже сейчас разрабатываются алгоритмы шифрования, защищенные от этого.
… Для которых как раз и требуются квантовые компьютеры, которые поломают классическую криптографию.
Полагаю вот от таких недо-квантовых квомпьютеров можно разрабатывать специализированную защиту, т.е. в этом смысле сначала должен быть создан такой компьютер.
Я же имею в виду что достаточно разработать защиту от универсального квантового компьютера.
Я же имею в виду что достаточно разработать защиту от универсального квантового компьютера.
Видимо, вы плохо представляете себе, на каких принципах работает современная криптография, раз употребляете слова «достаточно разработать».
Есть огромный класс задач, который называется «NP-трудные задачи». Особенность этого класса следующая:
1. На существующих архитектурах не найден эффективный алгоритм решения таких задач. Это не значит, что его не существует, но предполагают, что все же не существует. Иными словами, для таких задач есть один единственный алгоритм решения: полный перебор всех вариантов (подгонка под ответ). Сложность в том, что с ростом размерности задачи (самый важный параметр), количество вариантов для перебора растет очень быстро (экспоненциально быстро). И время решения задачи становится неприемлемо большим. Неприемлемо большим — это в число с тысячами нулями (я не знаю обозначений для таких числел) больше раз, чем существует вселенная.
2. Все задачи из класса NPC сводятся друг к другу за полиномиальное время (часто — за линейное). Это означает, что если хотя бы одна задача из этого класса будет решена (т.е. будет найден эффективный алгоритм, который будет выполняться за приемлемое время, вроде часов или лет, а не сроков существования Вселенной), то это автоматически будет означать, что решены ВСЕ задачи из класса NPC.
3. У вас есть задача и кто-то вам предлагает ответ. Вы можете быстро проверить, является ли ответ решением задачи или нет. Иными словами, для проверки вам не нужно создавать новых Вселенных, проверить вы можете за считанные секунды на обычных компьютерах.
Так вот, ВСЯ современная криптография основана на задачах из класса NPC: вы быстро можете перемножить пару случайно сгенерированных чисел. А вот разложить полученное число на множители вы уже быстро не можете: NP-трудная задача.
… И тут появляются квантовые компьютеры, которые умеют решать NP-трудные задачи за линейное время. Это означает, что ВСЕ АБСОЛЮТНО ЗАДАЧИ из класса NPC решаются за линейное время. Например, взлом 4096-битного шифра будет занимать не кучу времени, а всего-лишь 4096 тактов квантового компьютера.
И никакую защиту на КЛАССИЧЕСКИХ компьютерах вы не сможете придумать даже теоретически. И вот в этот момент и вся криптография и вся экономика, построенная на криптографии — рухнут. Поскольку все подписи, надежно идентифицирующие владельца, можно будет подделывать на здрасьте.
Можно ли разработать криптографию, устойчивую к взлому квантовыми компьютерами? Можно. Но для ее создания нужны квантовые компьютеры.
Ну т.е. представьте себя на месте ракового больного, которому осталось считанные дни жить. И он тут узнает, что появилось новое уникальное лекарство от рака, которое его вылечит. Одна беда. Получить такое лекарство он сможет минимум через 10 лет.
Алгоритм Шора решает две задачи: разложение на множители и дискретный логарифм (сама статья Шора так и называется Algorithms for Quantum Computation: Discrete Log and Factoring, 1994, doi:10.1109/SFCS.1994.365700). При этом он работает "для любой коммутативной группы работает, нужно только умножать уметь", см http://logic.pdmi.ras.ru/~sergey/teaching/crypto10/12-quantum.pdf "Алгоритм Шора" — Сергей Николенко, Криптография — АФТУ РАН, 2010
В результате получается квантовое решение задачи дискретного логарифма. Эллиптические кривые не спасают — для любой коммутативной группы работает, нужно только умножать уметь.
Мы взломали всю коммутативную криптографию. Что делать? Один ответ — строить квантовую криптографию. Другой ответ — строить некоммутативную криптографию.
(для создания некоммутативной криптографии не нужны квантовые компьютеры, а "квантовая криптография" = Quantum Key Distribution — это всего лишь линии связи на одиночных квантах и никаких кв.комп. также не требуют: http://sqi.cs.msu.su/store/storage/ss8dw5n_quantum_cryptography.pdf "квантовой криптографии… возможность генерации ключей, секретность которых гарантируется фундаментальными законами квантовой механики", http://book.itep.ru/6/q_crypt.htm)
почему на квантовом компе задача будет решена за линейное время?
Потому что квантовый мир «прячет в себя» экспоненту. Суперпозиции, квантовая запутанность — это про то самое.
давайте мы эмуляцию кубита запрограммим на обычном компе и будем решать за линейное время? почему нельзя?
Когда вы будете эмулировать квантовую систему на классическом компьютере, ваша физическая «квантовая экспонента» развернется в вычислительную экспоненту. И эмулировать вы будете эту систему ровно столько же, сколько будете решать NP-трудную задачу на классическом компьютере.
плюс если бы кто-то написал эмулятор кубита, то во первых широкие массы получили бы доступ к возможности его (кубит) изучать, ну и заодно оптимизировать этот самый эмулятор.
Есть все эти эмуляторы. Поищите по "open source quantum computer emulator". Проблема в том, что требуемый объем памяти и время расчетов растет экспоненциально с ростом количества кубитов. Самая большая эмуляция — 51 кубит, кажется.
вот этого «прячет в себя» я и не понимаю.
Подозреваю, что полноценно никто не понимает. Квантовое состояние описывается суперпозицией квантовых состояний отдельных частиц. Ну т.е. про кота Шредингера будет описание вида «кот жив с вероятностью 0.5 и одновременно кот мертв с вероятностью 0.5». Когда количество запутанных частиц растет, описание квантовой системы растет с экспоненциальной сложностью. И при этом продолжает работать в реальном времени. :) Наша Вселенная не тормозит и не подвисает :)
А решая ОДНУ задачу на обычном компе мы можем поискать способы оптимизации ее решения и выбрать какой-то который будет приемлем для эмуляции.
И любой из этих способов будет сильно тормознее физической вселенной. Сильно — это в экспоненту раз.
а потом на кубитах мы сможем решать множество NP-трудных задач.
Исходя из неверной предыдущей посылки, неверны и все последующие рассуждения. Эмулировать Вселенную с достаточной скоростью не получится. Почему и придем к тому, что эмулятор даст только проигрыш по сравнению с классикой.
если условно говоря на кубитах у нас имеется алгоритм решения, а на обычном такового нет, то эмуляция кубита дает алгоритм для обычного компа.
Не так. на кубитах у нас имеется быстрый алгоритм (решает задачу за несколько тактов квантового процессора — времена меньше секунды), то на обычном компе у нас есть медленный алгоритм (для которого требуется в миллиард миллиард миллиард… (и т.д. миллиард раз)… миллиард раз больше времени, чем существует вселенная).
вот ту же задачу комивояжера на современных компах решают же 100500 способами.
И среди этих 100500 способов нет ни одного, который был бы а) быстрым и одновременно б) точным. Есть или точный, но для которого нужно стотыщмильярдов тысячелетий времени или есть быстрый, который даст решение вот прям щас, зато с погрешностью в два раза (что, кстати, круто, потому как ГАРАНТИРУЕТСЯ, что погрешность не хуже).
Иными словами: задача коммивояжера не решена.
На квантовом компьютере можно придумать алгоритм (вроде еще не придуман, но, кажется, что придумать его гораздо проще, чем решить проблему P<>NP). И тогда задача будет решаться за линейное время. (несколько секунд против стотыщмилярдов тысячелетий).
плюс если бы кто-то написал эмулятор кубита, то во первых широкие массы получили бы доступ к возможности его (кубит) изучать, ну и заодно оптимизировать этот самый эмулятор.
Вы правда хотите исследовать ФИЗИЧЕСКИЙ мир по эмуляции? :) Так-то кубиты и иже с ними изучают на ускорителях. Если вы про теорию, то эмуляцию написать нет проблем. На пару-тройку кубит вы эмулировать сможете. На большее у вас мощностей не хватит.
ну и заодно оптимизировать этот самый эмулятор.
Не думайте, что у вас получится оптимизировать эмулятор хоть сколько-нибудь значимо. Хотя бы потому что вы никак не избавитесь от экспоненциальной сложности описания состояния квантового компьютера.
почему в этом направлении работы не ведутся?
В какой именно? Эмуляция кубитов? Потому что тут нечего исследовать. Эмуляция вопросов не вызывает.
А как же шифр Вернама от 1917 года и широко используемые во Второй Мировой одноразовые шифроблокноты?
В лучшем случае квантовый компьютер выдаст столь неудобоваримое количество расшифровок, что явно потребуется неудобное количество времени на анализ. Есть поговорка — гора родила мышь. В нашем случае с точностью до наоборот — мышь наложила кучу с Эверест.
Естественно, для непрерывных потоков данных сложно извратиться с подобным методом, но на то пусть голова болит у гуру. Криптостойкость метода заставит им воспользоваться в своё время.
В современной жизни, когда наблюдается засилие вычислительной техники, все стремятся к упрощению своей жизни и во главу угла поставлено пресловутое «баланс цены и качества».
С лёгкой руки математиков (им только дай волю порезвиться, разведут малину) были разработаны симметричные и не очень шифровальные методики, суть которых мы прекрасно знаем — невозможность современными средствами раскрыть зашифрованное в сроки, когда информация является актуальной. И теперь мы подходим к тому, что это изначально неправильное в глобальном масштабе направление подошло к грани теоретического провала.
С шифроблокнотами крайне сложно решить задачу передачи самого блокнота с гарантированным непопаданием его в чужие руки.
Второй неприятный момент — ёмкость блокнота. При современных потоках информации любой шифроблокнот весьма быстро истощится.
Третий момент связан со вторым. При необходимости генерации одноразового кода есть далеко ненулевая опасность повторения последовательности произвольной длины, а это абсолютно недопустимо. В той же Второй Мировой был зафиксирован факт вскрытия сообщения из-за ошибочного повторного использования старого кода. И это в условиях, когда про цифродробилки ни ухом, ни слухом.
> Заключают, что он неудобен до полной невозможности им пользоваться на практике, используйте замечательный AES.
Вот этот хвалёный AES и вкупе с ним и находятся сейчас на последнем издыхании. И современные методы шифрования имеют неустранимый критический недостаток. Провал шифровального механизма, ключей означает, что буквально вся перехваченная за многие лета информация будет прочитана, в отличии от попадания в чужие руки «странички блокнота». Да, одно сообщение будет раскрыто, но не более того. Разница налицо.
Если разобраться, то каждый метод имеет свою область применения.
Пока ещё неизвестно могут ли квантовые компьютеры ускорить решение NP-полных задач, так что про NP-трудные задачи говорить рановато.
Насколько я помню, есть квантовый алгоритм для факторизации чисел. Рассчитан такой алгоритм на идеальный квантовый компьютер, который выдает достоверные решения, а не с какой-то заданной вероятностью.
Другое дело, что пока что даже реальных квантовых компьютеров нет, не то, что идеальных. И да, есть большие сомнения, что таковые вообще будут созданы. Так что, да, есть подозрения, что классическая криптография еще поживет, вместе с насущными нерешенными проблемами вроде фолдинга белков.
Оригинальный алгоритм Шора выдает правильный результат с вероятностью 1/2 (см. arxiv.org/abs/quant-ph/0208183 ) на идеальном квантовом компьютере и это не имеет отношения к классу сложности. Реальные квантовые компьютеры вполне себе есть, например www.nature.com/articles/nature18648
Если очень в общем виде объяснять (как дилетант дилетанту), то фишка в том, что из-за суперпозиции квантовый комьютер может осуществлять перебор различных вариантов одновременно. Надеюсь, более понимающие люди объяснять более корректно.
Но. Кто мешает выполнять нейроны на околопроцессорной периферии?
Так уже делают.
- GPU
- NVidia Volta с аппаратными "тензор-блоками"
- и не только, тысячи их
А ПЛИС… ПЛИС хорошо работают при конвейеризации вычислений, например, потоковой обработке сигналов. У сферического плиса в вакууме частоты существенно ниже, чем у современных ЦПУ
Традиционный комментарий, лучшее объяснение работы квантового компьютера (то, о чем комментарий Alex_Q выше, чуть более подробно):
If you don't talk to your kids about quantum computing, someone else will.
Заодно категорически советую блог Скота Ааронсона про квантовые вычисления и иже с ним, он один из лучших объяснятелей, что там к чему.
If you take just one piece of information from this blog:
Quantum computers would not solve hard search problems
instantaneously by simply trying all the possible solutions at once.
Google представила новый квантовый процессор