Pull to refresh

Comments 139

Интересно, по чем нынче квант для народа…
К сожалению информацию о ценах найти не удалось.
Если вы спрашиваете о цене — значит не можете себе это позволить (с)
С одной стороны вроде и да, но с другой, а не выйдет ли дешевле раз эдак в 10 просто эмулировать эти 20 кубитов на традиционных процессорах?

16MiB для представления состояния 20-ти кубитовой системы с 64-х битной точностью. Любая последовательность квантовых вентилей может быть представлена с помощью одной единственной матрицы комплексных чисел размером 2^20 на 2^20 (16 терабайт), но для небольшого количества вентилей это можно сильно оптимизировать. Так что да — наверно будет сильно дешевле.


Позапрошлогодний рекорд симуляции — 45 кубитов, использовалось 8192 процессора и 0.5 петабайт памяти.

А по скорости работы как оно?
Нормально. Мои домашний старенький ноут спокойно обрабатывает симуляции до 20 кубитов. На 26 даже инициализация занимает 15 минут. На 28 кубитах симуляция вылетает.
UFO just landed and posted this here
Более того, их компьютер подвержен ошибкам. И функциональность симулятора шире.

И весь шум поднят из-за единственного «но». Добавление кубита в симулятор означает удвоенный расход ОЗУ. Как я уже писал, мой ноут вылетает на 28 кубитах. Товарищ выше упоминал лимит в 45 кубитов на системе в тысячи процов.

Компьютер же от IBM — реален, и не зависит от ОЗУ. Ребята надеются, что смогут урезать ошибки, и удваивать количество кубитов каждые N лет.

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


Нельзя не заметить, что в статьях часто опускают слово "прототип".

А сколько этих амплитуд может быть при «честном» симулировании идеального квантового компьютера? Как понимаю 2n, где n число кубит квантового компьютера? А требования к объемам памяти для симуляции на классическом компьютере тогда 2n*w, где w — точность представления состояний (например 8 байт для FP64)?

Тогда текущий рекорд симуляций — 49 кубит поставленный в прошлом году на крупнейшем китайском суперкомпьютере (Sunway TaihuLight): arxiv.org/abs/1804.04797

Но вот если квантовый компьютер не сферический в вакууме идеал, а наподобие доступных в реальности сейчас, с ограниченной связанностью кубит, а не полной? Не понятно, насколько можно упростить модель и насколько снижаются требования к классическим компьютерам, чтобы условно «иметь возможность делать то же самое, что в принципе способен сделать такой реальный, а не идеальный квантовый компьютер»
Первые ламповые компы было проще эмулировать на счётах — но инженеры решили иначе
Эм вообще-то совсем не проще.
Эмулировать то конечно можно было, но даже первые ламповые компьютеры считали в сотни — несколько тысяч раз быстрее, чем люди на счетах или даже с механическими арифмометрами. Причем только в некоторых видах задач один такой компьютер было возможно заменить на «несколько тысяч человек со счетами» — в других адекватной замены вообще не получалось.

Т.е. преимущество сразу было явное и наглядное.
Но не для граждан *этой* страны, похоже: )
Да, там в списке регистрации отсутствует десятка два стран (иногда по не вполне понятным критериям).

AFAIK Тем что способен не только задачи оптимизации методом квантового отжига.

Как отметили выше — позволяет производить универсальные вычисления. Вкратце тема раскрыта здесь.

UFO just landed and posted this here
Ниже пишут, что у IBM все далеко не так хорошо. В той же ветке пишут, что поддерживаются связи только с 6 соседями.
Кстати, пытался только что посчиать количество состояний для D-Wave — и мне не очевидно сколько их и как его сравнивать с «честным». Можете привести рассчеты?
В квантовом компьютере, скорее, важно, сколько кубитов и как долго находятся в когерентном состоянии (т.е. в связанном, или спутанном, состоянии). Непосредственная связность влияет только на то, как именно реализовать конкретные ключи. Например, если кубиты не связаны напрямую, то, чтобы применить к ним бинарный ключ, придётся делать несколько промежуточных операций обмена, чтобы «перетащить» состояние одного кубита на соседа второго. Это увеличивает время выполения алгоритма (которое фундаментально ограничено временем когерентности).
Это увеличивает не только время выполнения, но заодно и количество ошибок, которые накапливаются при каждом взаимодействии(операции). В предельных случаях до такого уровня, что конечный результат на выходе получается слабо отличим от случайного шума.
Именно так, уже доступен.
UFO just landed and posted this here
Ага. И судя по всему главная фишка всего устройства — огромная стеклянная дверь…
Не одного шуруповерта! Только ручная сборка.
Не совсем. Надо еще глянуть на связность кубитов, потом на уровень ошибок.
Да не, я про выдыхание с облегчением. Для продуктивного исполнения Шора и Гровера на реальныо опасных задачах (взлом ключей и реверс хеш-функций) 20 кубитов — это ни о чём.
Я о том же.
Это понятно. Но сейчас у квантовых компов какие проблемы?
1. Число кубитов (20).
2. Связи между кубитами. (один кубит связывается максимум с 6 соседями)
3. Удерживание состояния на кубите. Сейчас вроде микросекудны.
4. Ошибки (при запутывании, при удержании — весь спектр). Тут все плохо. 7% ошибок на мультикубитах на Q5 Tenerife.

Соответственно, вы вполне справедливо волнуетесь по поводу первой проблемы. Я вдобавок интересуюсь, какой прогресс на оставшихся трех.
Угу, поэтому еще очень-очень рано чтобы начинать «вдыхать» )
2. Связи между кубитами. (один кубит связывается максимум с 6 соседями)
То есть на самом деле это 7-кубитный компьютер?
Как я понимаю здесь имелось в виду, что гейты могут быть применены только к соседним кубитам. Т.е. представьте, что у вас в процессоре 20 регистров, но можно выполнять только операции вида op(reg[x], reg[x+1..5]). Вы по прежнему можете выполнить любой алгоритм, просто возможно его придется разложить на бОльшее число операций. Для квантовых компьютеров каждая операция (гейт) несет дополнительную вероятность ошибки, поэтому в сумме это просто выливается в более высокую вероятность ошибки, ограченность сложности алгоритма итд.
daiver19 прав.
В левом верхнем углу по ссылке есть схема процессора. Вы можете запутать нулевой кубит с первым и вторым, первый — с нулевым и вторым, второй — со всеми четырьмя, и т.д…

То есть, в этом процессоре 5 кубитов, но вы не можете запутать первый с пятым напрямую. Для этого придется использовать «грязные хаки».

Из тех процессоров, что я видел, самый лучший результат по связанности — один кубит с шестью соседями. Схему сабжа я пока не видал.
Почему «грязные хаки»? Скажем ИБМ использует специальные алгоритмы, готорые берут «программу» (то есть последовательность гейтов) написанную для связности все-со-всеми и переводит её в программу для конкретного процессора. У них даже конкурс был по оптимизации таких программ. Естествено, при этом программа удлиняется, а чем больше программа, тем больше ошибок. Там вверху это уже написали.
Да, обойти проблему можно, но цена достаточно велика. Для реализации CNOT с задействованием одного промежуточного кубита потребуется 4 контролируемых NOT. Для 2 промежуточных кубитов понадобятся уже 10 операций, и число служебных операций Op растет от числа промежуточных кубитов Nm как O(2^{Nm}).

Да, можно погонять маппинг кубитов в исходной программе, чтобы наиболее часто взаимодействующие кубиты располагались рядом друг с другом, но это требует усилий, совершенно не относящихся к решаемой задаче. Поэтому я называю это «грязными хаками». Полагаю, поэтому IBM и провела свой конкурс «компиляторов».
Даже без всяких хитрых алгоритмов можно через n обменов (SWAP) «пододвинуть» нужный кубит, потом «отодвинуть» его обратно. Так что затраты линейные получаются. SWAP получается из 3 CNOT. В бесплатных процессорах там ещё проблема, что CNOT однонаправленное, так что приходится ещё Адамара (H) использовать. Но всё равно это линейно. А они достаточно хитрые алгоритмы используют.
О, изящное решение, спасибо. На всякий случай, оставлю прямой линк на статью об оптимизациях.
Спасибо, эту я что-то пропустил, но судя по тому, что пишет победитель конкурса, всё это достаточно нетривиальная активность длительностью не один год.
Из тех процессоров, что я видел, самый лучший результат по связанности — один кубит с шестью соседями. Схему сабжа я пока не видал.

Нашёл схему на 20 кубит. И много другой инфы, включая кое-что по следующему квантовому компьютеру IBM (50 кубит). Буду готовить новый пост по теме в ближайший месяц-два. Если есть какие-то интересные вопросы — задавайте, постараюсь раскрыть по возможности.
image
А сколько кубитов понадобится для этих алгоритмов?
Говорят, что должны быть тысячи. Или десятки тысяч.
Хотя бы как длина ключа (в битах) соответствующего алгоритма.
КМК, вы не учитываете, что квантовые алгоритмы постоянно совершенствуются.
Например здесь пишут, что даже на 2 и 4 кубитах на реальном КК можно разлагать на сомножители достаточно большие числа:
we have experimentally factorized the integers 4088459 and 966887, using 2 and 4
qubits respectively

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

Так изначально здесь и спрашивали в т.ч. за Гровера, правда относительно «реверса хеш-функций» (см. по ветке выше) ;).

Разумеется GSA (в отличие от алгоритма Шора) не даст «экспоненциального ускорения» (и вообще вряд ли потянет), необходимого при факторизации (дискретном логарифмировании/соотв. EC-задачах) на размерностях порядка современных ключей. Речь не про это.
«Измененный алгоритм Гровера» из статьи (хотя повторяю, к нему есть вопросы например в части масштабируемости, универсализации, скорости и т.д.) на реальных примерах показывает, что требуемое число кубитов может быть существенно меньше, чем «длина ключа (в битах)». Хотя бы для некоторых (частных) задач определенной размерности.
Как мы можем быть уверены, что невозможны подобные (или иные) оптимизации алгоритмов Гровера и/или Шора (или их модификации или вообще новые квантовые алгоритмы) для эффективного решения «серьезных» полноразмерных задач, но с «пониженным потреблением» кубитов? Имеются ли принципиальные препятствия к этому?
UFO just landed and posted this here
Насколько я знаю, даже не доказано, что разложение на множители — это NP-полная задача, так что тут и P=NP не поможет.
Вы можете проверить умножение за O(n^2) операций, где n — разрядность ваших множителей. Взгяните на умножение столбиком: n строк, в каждой n цифр.
Разумеется, это NP-задача, это очевидно. Но вот NP-полна ли она — вопрос пока открытый.
Это своего рода «хак» для частного случая, а не решение задачи «честно» (в общем виде).

Насколько понял (особо не вчитывался в статью) для решения задачи
1 — используются априорные знания, например что у интересующего нас числа, которое мы планируем разложить точно имеется только 2 простых множителя конкретной длины равной друг другу. Получается своего рода как говорят школьники и студенты «проведем решение задачи методом подгонки решения под заранее известный результат» — решается задача не поиска собственно решения, а задача поиска схемы которая выдаст уже заранее известный результат, хотя и не будет иметь его в исходных данных или в самой себе в готовом виде
2 — алгоритм не чисто квантовый, а гибридный — часть (подготовка данных в нужной форме — расчет гамильтониана системы) выполняется на классическом компьютере

Что характерно для разложения числа 4088459 (22 бита в двоичной форме) оказалось достаточно всего 2 кубит, а для меньшего числа 966887 (20 бит) — потребовалось 4 кубита. Дело случая — множители во 2м числе лежат дальше друг от друга, чем в 1м большим числе, а в этом алгоритме ищется по сути разница между множителями (а не сами множителей) — отсюда кол-во нужных кубит зависит не от длины раскладываемого числа, и даже не от длины множителей входящих в него, а от длины разницы между его множителями.
Но если мы не знаем заранее какие они будут и сколько кубит понадобится — как «экономную» схему для вычислений строить?

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

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

А какой например смысл будет в «экономии кубит» и решении квантовой части задачи за микросекунды, если для подготовки данных для ввода в квантовый компьютер в случае длинных ключей скажем потребуются миллион лет вычислений суперкопьютера на стадии подготовки — так же как и для простого перебора в классических алгоритмах. Ну или может в целую тысячи раз меньше — тысячи лет вместо миллиона.
Модель вычислений, API, SDK,… — где это все?
А для каких вычислений его оптимально использовать?
UFO just landed and posted this here
Чет кажется намного проще использовать эмулятор для таких целей или облачные решения. Вроде кто-то предоставляет квантовые инстансы.
Но наверное прикольно покопаться с реально железкой ;-)

Те, кому "прикольно покопаться с железкой", сами заняты исследованиями по к.к. (а не сисадминством несуществующих коммерческих образцов).

есть сомнения в возможности эмуляции
В смысле? Эмулятор позволяет понять математическую модель квантовых вычислений, этого вполне достаточно, чтоб понять ее и писать программы на особом квантовом ассемблере. А потом, ее можно погонять на реальном железе. Так, например, в rigetti делают(https://www.rigetti.com/forest), уверен, что и у остальных похожий подход.
например абсолютная точность в процессе вычислений. и всё такое прочее
Вы про абсолютную точность смеетесь что-ли?

Это у самых квантовых компьютеров БОЛЬШИЕ проблемы с точностью.
Их как раз по эмуляциям на классических компьютерах проверяют — толи он вообще считает, что от него требуется.
поиск хитрый, работа с образами, математика некоторая.
розмером с комнату, как в старые добрые времена
Теперь я знаю, что ответить ребенку на «Где живет Дед Мороз?»
Если это квантовый Дед Мороз, то он одновременно и живёт и не живёт, пока не придёшь в гости.
Может быть, наступают старые добрые времена 2.0?

А потом он станет размером с кредитку.

Но только систему охлаждения все равно придется с собой в тележке возить для такой кредитки.
> Ералаш про японские наручные часы и батарейки к ним (с)
Начинаем закон мура для кубит?
Стоит отметить, что дизайн системы выполнен несколькими известными студиями и удивительно красив, для такого утилитарного устройства.

Класс, именно этого мы прежде всего от него хотели!
Ещё бы розовый и с яблочком. И под две симкарты.
Телевизор с антеннкой забыли

Забавно, как тихо и почти без фанфар происходит революция. Точнее революция зарождается. Особенно это заметно, если взглянуть на эти новости в контексте истории теоретических исследований в области квантовых вычислений. Первые серьёзные работы на эту тему, предлагающие конкретные алгоритмы, были опубликованы в середине 90-х, что вызвало волну эйфории и энтузиазма. Люди стали мечтать о "более лучших компьютерах", невиданных доселе вычислительных мощностях и поломанных криптографических алгоритмах. Но когда эксперименты вскрывали всё больше новых трудностей на пути физической реализации квантовых вычислений, энтузиазм поутих, а затем и вообще сменился скептицизмом в отношении реальности сколько-нибудь практичного квантового компьютера. А теперь уже видно, как доселе фундаментальные исследования постепенно переезжают в R&D-отделы компаний (пусть больших и богатых), и квантовые компьютеры начинают обретать конкретные черты (напоминающие об эпохе ЭНИАКов, МАРКов и иже с ними).


Правда, нужно понимать, что сравнивать напрямую типичный современный компьютер, основанный на двоичной архитектуре, и квантовый компьютер — занятие неблагодарное и, скорее, бесполезное. Квантовые компьютеры по сути гораздо ближе к аналоговым вычислителям, весьма распространённым в середине 20-го века. И поэтому вопрос, когда напишут "DOOM" на квантовом компьютере, довольно бессмысленен. Скорее всего, никогда, потому что они предназначены для других задач. В частности, масса задач физики и химии требует решения задачи полной диагонализации. Классический алгоритм решает подобную задачу за O(4^N), где N — это число степеней свободы. Это делает невозможным решение некоторых задач. Квантовым алгоритмом такая задача может быть решена за O(1) — O(N), в зависимости от задачи. Правда, алгоритм потребует когерентной работы O(N) кубитов, так что всё будет зависеть от пределов масштабируемости. Но тут ещё есть запас по температуре (у IBM сейчас используется температура порядка десятков мК, ещё есть куда понижать), и по новым физическим эффектам (а-ля топологически нетривиальные электронные состояния), которые теоретически смогут позволить масштабировать квантовые компьютеры, оставаясь в области разумных температур.

И поэтому вопрос, когда напишут «DOOM» на квантовом компьютере, довольно бессмысленен. Скорее всего, никогда, потому что они предназначены для других задач. В частности, масса задач физики и химии требует решения задачи полной диагонализации.
Первые компьютеры тоже не для игр создавались, а теперь на них в туалете в Angry Birds играют.

Ну DOOM — это святое. Запустят как-нибудь.

Хех. Сотни тысяч кубитов, миллионы гейтов, алгоритмы квантовой коррекции, чтобы на выходе получить следующий кадр и следующее состояние игры без ошибок с вероятностью, скажем, 70%.
Это вы зря.
Используют миллиарды кубитов, найдут все вероятные прохождения всех уровней, и отыщут все секреты.
Квантовые компьютеры работают не так — они не являются недетерминированной машиной Тьюринга, которая выполняет все ветки алгоритма параллельно. То есть параллельно проверить все пути прохождения дума не получится. Может быть есть возможность как-то приспособить алгоритм Гровера для поиска секретов, но ускорение у него квадратичное — вместо ста лет найдёт за десять (или, если учитывать константные факторы, то, что классический компьютер найдёт за месяц, квантовый может найти за год, но то, что классический найдёт за 1728 лет, квантовый найдёт за 144 года).
как сложно
что за константные факторы? почему ещё нет статьи на хабре?
То есть параллельно проверить все пути прохождения дума не получится.
Зачем все ветки алгоритма?

Храним любое значение как набор кубитов (Двоичное представление ситуации на уровне)_(история действий)_(число открытых секретов)_(служебные кубиты). Начальное значние: 100% вероятности состояние (старт уровня)_(000000000)_(0). Каждый тик «параллельно» меняем несколько битов энного шага в истории, изменяем состояние карты в соответствии с текущим состоянием, считываем число открытых секретов.

На выходе имеем 2^{N*100500} состояний. Амплифицируем те, где количество секретов равно максимальному. Муторно, требует много ресурсов, но реализуемо.
> На выходе имеем 2^{N*100500} состояний. Амплифицируем те, где количество секретов равно максимальному. Муторно, требует много ресурсов, но реализуемо.

O(sqrt(2^{N*100500})), чтобы найти максимум.
Муторно, требует много ресурсов, но реализуемо.
Но вы правы. Алгоритм надо оптимизировать.
  1. Скорее всего, мы получим n исходов с максимумом секретов. Соответственно, получим сложность корня из 100500/n.
  2. Можно поиграть с сокращением записи. Одни действия встречаются чаще, чем другие, так что можно попробовать использовать Код Шэннона для сокращения числа 100500.
  3. Записываем не все действия.
  4. Ищем по секрету за раз.

корня из 100500/n.

Нет, сложность всё-таки корень из {2^100500}/n. У нас есть функция преобразующая набор битов фиксированной длины (100500), в котором закодированы команды перемещения игрока, в количество открытых секретов. Квантовый алгоритм поиска глобального максимума функции на множестве S имеет сложность O(sqrt(N/n)), где N = |S| (см. [0]), то есть N = 2^100500 в нашем случае.


Это не "много ресурсов", а столько ресурсов, что в нашей вселенной их никогда не получить.


[0]: раздел 8 в https://research-management.mq.edu.au/ws/portalfiles/portal/62430609/Publisher+version+%28open+access%29.pdf

Очепятался, простите.
Получим сложность O(sqrt{2^{100500/n}}).
Будут играть в квантовые Angry Birds: птица летит по всем возможным траекториям одновременно, и тебе показывают, с какой вероятностью замок со свиньями разрушен, и каково среднее по распределению числа убитых свиней.
Да, Ландауэр, упомянутый в статье Дьяконова был одним из первых скептиков квантовых компьютеров. Кстати, и упомянутое мной сравнение с аналоговыми компьютерами — это тоже от Ландауэра.

Но, опять-таки, основной недостаток критики Дьяконова состоит в том, что он сначала задаёт некие очень сильные требования к квантовым компьютерам, а потом торжественно делает вывод, что эти требования невыполнимы. Действительно, оптимисты считали (и, возможно, кто-то продолжает так считать), что квантовые компьютеры чуть ли не заменят обычные везде, где только можно, но об этом речи не идёт. То, к чему сейчас стремятся — это гибридные схемы. По сути, классический компьютер с квантовым вычислительным модулем. Об этом, кстати, говорится в ответе на критику, ссылку на которую дал rstm-sf ниже.
>что он сначала задаёт некие очень сильные требования к квантовым компьютерам, а потом торжественно делает вывод, что эти требования невыполнимы

Справедливости ради, нужно сказать, что нечто похожее происходит и во всей теории QC и QM. Т.е. теорией задается нерушимость некоторых принципов ( как пример — принцип неопределённости Гейзенберга) и любые попытки натянуть результаты экспериментов полученных в рамках QM на принципы классической физики — отсекаются за счет упоминания этих принципов. Получается система замкнутая сама на себя.

Кроме того, само по себе признание того, что QC — это не совсем то, чего все ожидают — создает парадоксальную ситуацию. С одной стороны на исследования выделяются огромные деньги благодаря сильным ожиданиям от пользы QC. С другой стороны, если говорят что вы ожидаете от QC слишком многого, то появляется логичный вопрос: для чего тогда на QC выделяется такое огромное финансирование?
UFO just landed and posted this here
Может быть имеет смысл именовать такие устройства не «компьютер», а, скажем, «квантовый вычислительный модуль»?
Да, скорее всего, ближайшее будущее будет за гибридными архитекутрами, где обычный, классический, компьютер будет управлять и использовать квантовый модуль.
5 лет назад — в января 2014 года IBM продала Lenovo всю свою линейку x86-серверов. И тогда все бизнес-аналитики пытались понять: Почему IBM продает часть серверного бизнеса?
Ну а сегодня мы пожалуй получили простой ответ — в IBM считают эпоху x86-серверов подходящей к своему неизбежному концу (а вместе с этим предвещают конец славной корпорации Intel — которая сегодня большую часть прибыли получает именно за счёт продажи серверных x86-процессоров) и торжественно открывают новую эпоху квантовых серверов:)
Я думаю они перенаправили вложения в будущее, а не продолжать ковыряться в проработанной технологии.
Забавно, как тихо и почти без фанфар происходит революция
Это потому что даже обычные компьютеры не постигнуты большинством населения как следует.
Написать Hello, World и понять и объяснить другому как это происходит до сих пор могут далеко не все.
Суть подобных систем однойстрокой — «Я квантовый компьютер, но это не точно»
«Я Илон Маск, но это не точно...»

P.S. Вывод, «это не точно» имеет квантовую природу. ;)
Эффективный менеджмент, PR, слабоумие и отвага :)
О! Криогенное охлаждение! Теперь в серверную надо не в ватнике заходить, а в костюме из «Назад в будущее», чтоб эстетично смотреться на фоне компьютера. :)
Интересно, криптовалюту на нем майнить уже начали?:) По идее майнинг (а также взлом основанных на RSA шифров) — самые очевидные области применения. Причем уже и алгоритм готовый имеется.
Или кубитов пока маловато для этих целей?
Не начали. И начнут нескоро. К нужному для RSA-2048 количеству кубитов приблизятся лет через 12 (в лучшем случае).
ЕМНИП, DWave обещали удвоение кубитов каждый год. Предполагаем, что Intel может это воплотить.
Ныне 20 кубитов. Надо 2000. Это лет 7.
Проскакивала инфа, что 100.000 физических кубитов хватит для одного «эффективного» кубита. Это еще лет 17.
Скинем лет 5 на параллельные улучшения, добавим лет 10 в резерв — получается 30 лет.

Дальше считать не могу: вода закончилась, и вилы затупились.

D-Wave умеет только "квантовый отжиг", но не алгоритм Шора.


Ну то есть "на самом" деле "квантовый отжиг" (который работает и более-менее масштабируется) — это принципиально проще (до примитивизма) в сравнении с "универсальным квантовым вычислителем".


А для создания практически ценного "универсального квантового вычислителя" необходимо решить "проблему масштабирования", в отношении которой уместно процитировать wiki:


Чем больше кубитов находятся в связанном состоянии, тем менее стабильной является система. Для достижения «квантового превосходства» требуется компьютер со многими десятками связанных кубитов, работающими стабильно и с малым числом ошибок. Вопрос о том, до какой степени возможно масштабирование такого устройства (так называемая «Проблема масштабирования»), является предметом новой интенсивно развивающейся области — многочастичной квантовой механики. Центральным здесь является вопрос о природе декогерентности (точнее, о коллапсе волновой функции), который пока остаётся открытым.

На чем (IMHO) все и остановится примерно на 10^12 лет ;)

А что через 10^12 лет будет?

Вся вселенная остынет достаточно близко к абсолютному нулю, чтобы большие квантовые схемы могли работать с большим временем сохранения когерентности и малой вероятность ошибок? И квантовые компьютеры наконец-то смогут нормально работать?
Интересная ситуация с этими вашими квантовыми компьютерами.
Впервые о них я узнал еще в начале 00-х. Прошло 18 лет, а воз и ныне там. Более того, со скрипом въехав в теорию, заложенную как теоретическую базу для них, стало понятно, что в их случае нет гарантированной точности результата.
в их случае нет гарантированной точности результата.
Матожидание времени поиска решения на QC сильно меньше классики (на идеальных QC). Грубо говоря, вы заранее знаете, что на квантовом чипе вы решаете задачу с вероятностью в 1/2, и на каждую попытку уходит минута. На классическом вы решите задачу за 10 минут с первой попытки. Дальше — выбор за вами.
Вроде системы коррекции ошибок разработаны, просто нужно много кубитов. Но даже на всего компьютере с несколькими сотнями кубитов можно достаточно эффективно решать некоторые практические задачи.
Это «вроде» я бы назвал одним из популярных заблуждений.

Ошибки можно корректировать ТОЛЬКО когда состояние зафиксировано, но не во время «расчетов». Любая проверка во время расчета означает что вы теряете суперпозицию, т.е. выходите из «квантового сумрака».

Поэтому «корректировка ошибок» возможно только как часть самого процесса/алгоритма вычислений. И вроде-бы «всё просто» — нужно только примерно удвоить кол-во кубит и связность между ними, а также быть готовым к тому, что результат отличный от незнаю/может_быть будет получаться в одном запуске из N^K^M, где N — кол-во кубитов, K-связи между ними, а M — кол-во «шагов» алгоритма…

Но это не точно :)
Естественно, проверок никто не делает и корректировка ошибок является частью алгоритма на низком уровне. Но это не значит, что в принципе нельзя корректировать ошибки. На викиописана куча подходов, которые исправляют ошибки не нарушая суперпозиции. Вроде бы можно обойтись кодом в 5 физических кубит на один логический, при достаточно низком уровне ошибок.
Кубиты — это, конечно, хорошо, но гораздо интереснее было бы сделать это на основе троичной логики. Скрестить квантовый компьютер и старую «Сетунь».
Чтобы что? При чем тут троичная логика к квантовым вычислениям?
В отличие от традиционных полупроводников квант может находиться больше, чем в двух состояниях. Это позволяет и считать быстрее, и места меньше занимать.
Я знаю на чем основаны квантовые вычисления, именно поэтому мне неясно при чем здесь троичная логика.
Видимо, вместо кубитов предлагается использовать кутриты, элементы с трёхмерным пространством состояний (|0>, |1>, |2>) вместо двумерного.
Хоть топик-стартера и минуснули, но в ру-википедии говорится, что это вполне жизнеспособная конструкция, позволяющая упростить некоторые вещи.
Спасибо за информацию, интересно. По вики правда я так и не понял, чему это может соотвествовать физически.
Ну, примеров-то полно, взять хоть те же нейтрино, у которых ароматы составляют трёхмерный базис (а массы — другой трёхмерный базис). Понятно, что на нейтрино квантовый компьютер построить будет затруднительно, но что-нибудь более реализуемое должно найтись. Просто я с практической стороной слабо знаком, даже описание уже воплощённых «в железе» кубитов обычно повергает меня в ступор.
Я тоже это с трудом осознаю, но на вики в статье про кубит порядочно видов описано. Спин, заряд, поляризация — всё бинарные базисы. Но самые многообещающие на данный момент — это сверхпроводниковые кубиты, и я понятия не имею, возможно ли трехуровневое состояние для них.
Ну, для трёх состояний можно, например, взять частицу в ловушке с тремя энергетическими уровнями. Или, я как-то читал, можно сделать резонатор, в котором будет поймано несколько фотонов, причём их количество будет суперпозицией из нескольких значений. Вопрос в том, насколько реально это реализовать в железе с большим числом таких объектов, причём взаимосвязанных. Плюс в той же викистатье говорится, что ещё и не каждые тройные состояния подойдут на роль кутрита, но каким свойством они должны для этого обладать, не уточняется, а научные статьи на эту тему я не искал, да и если бы нашёл, вряд ли понял бы (есть ссылка на вопрос на Stack Exchange, но там в ответе недостаточно информации, нет примера «настоящего кутрита», плюс комментарий к ответу утверждает, что в терминологии ошибка и описанное на самом деле всё-таки кутрит; в общем, вопросик явно не на пару минут).
Именно, поверхностный поиск не дал никаких внятных ответов, поэтому мне и неясно, что это может быть физически.
С помощью одниночного фотона создают высокоразмерное состояние (кудит).

А сколько нужно кубитов чтобы взламывать биткойны?

Берем размер хеша битка (вроде, 256 бит). Увеличиваем в 16 раз (ЕМНИП, этого достаточно для генерации оператора, высчитывающего хэш). Добавляем еще вспомогательный бит для алгоритма Гровера. Получаем 4.097 «идеальных» кубитов.
Грубая оценка числа «железных» кубитов, необходимых для реализации «идеального» — 100.000.
Итого: 409.700.000 кубитов.
Итого: 409.700.000 кубитов.

Взаимосвязанных?! оо()
А что вдруг так много? По 100 000 физических кубит на 1 логический. Предлагаемые схемы контроля и коррекции ошибок обычно максимум на несколько десятков физических на один логический предлагаются и в теории могут позволить КК работать без ошибок, при том что на уровне физических кубит они как раньше будут происходить достаточно часто (скажем раз на несколько сотен квантовых операций).

В некоторых подходах пытаются «схалтурить» и обойтись всего 3-5 кубитами, но тут пока ничего не получается.
100.000 — аргумент из разряда «за что купил». Вот источник (ищите комментарии от Strilanc).
В данный момент издательством Питер заканчивается перевод двух книг о разработке с использованием квантовых компьютеров (одна из них — непосредственно от разработчика из IBM и ориентирована на их экосистему, включая Q System One из поста). Этим книгам очень требуется вычитка (в нашей терминологии — научная редактура) т.к. переводчики не айтишники и не изучали квантовую физику на необходимом уровне. Из-за новизны темы у нас просто нет специалистов для такой работы, нам нужна помощь сообщества в их поиске.
Если вы владеете темой, или кто-то из ваших знакомых обладает нужными знаниями, отзовитесь здесь в ЛС или на почту david@piter.com
Sign up to leave a comment.

Articles